이번 주는 STACK 에 대해 반복적으로 공부했다.
먼저 백준 문제 중에 '에디터' 문제를 풀어보았다.
1406번: 에디터 (acmicpc.net)
1차 시도는 기존에 매일 하던 for 문으로 구현을 했는데, 제출하자마자 시간 초과 뜸..!!
1차 시도 - 시간 초과 - for 문 구현
N = list(input())
M = int(input())
current = len(N) + 1
for i in range(M) :
x = input().split()
if x[0] == 'L' :
if current != 1 :
current -= 1
elif x[0] == 'D' :
if current != len(N) + 1 :
current += 1
elif x[0] == 'B' :
if current != 1 :
current -= 1
N.pop(current-1)
else :
current += 1
N.insert(current-2, x[1])
print(''.join(N))
for 문은 시간 복잡도가 O(N^2) 으로, 매ㅐㅐ우 오래 걸린다..!
이 때, STACK 이라는 방식을 활용하면 시간 복잡도를 줄일 수 있다.
'STACK' 이란, 파이썬에서 리스트 형식으로 하나씩 쌓아 올리면서, input을 받는 방식이다.
STACK을 활용할 시, 시간 복잡도가 O(N) 으로 for 문으로 구현할 때 보다 매우 빠르다는 것을 볼 수 있음!
2차 시도 - 스택 구현, 런타임 에러 (인덱스 에러)
N = list(input())
M = int(input())
left = N
right = []
for i in range(M) :
x = input().split()
if x[0] == 'L' and left: # 'L'이면서 left에 문자가 있을 경우
right.append(left.pop())
elif x[0] == 'D' and right : # 'D'이면서 right에 문자가 있을 경우
left.append(right.pop(0))
elif x[0] == 'B' and left : # 'B'이면서 left에 문자가 있을 경우
left.pop()
else :
left.append(x[1])
print(''.join(left+right))
이번에는 stack을 활용했지만, 마지막 부분에 'else' 로 인해 인덱스 에러가 났다.
백준은 내가 왜 틀렸는지 제대로 알려주지 않아서,,, 예측해 보자면, else 에 "x[0] == 'L' and left == False" 나
"x[0] == 'D' and right == False" 가 추가되어 에러가 난것 같다.
3차 시도에서는 elif 로 바꿨다.
또한, 시간 단축을 위해 'input' 대신에 'sys' 라는 패키지를 이용했다.
'sys'를 활용하면 input에 비해 시간 단축이 된다.
sys 활용
- strip : 입력받은 값에 대해 양쪽 공백을 제거하여 저장
- rstrip : 입력받은 값에 대해 오른쪽 공백을 제거하여 저장
- split : 입력받은 값 중 " " 공백을 기준으로 나눠서 저장
# 3차 시도 - 시간 초과
# sys.stdin.readline() 이용
import sys
left = list(sys.stdin.readline().strip())
right = []
for i in range(int(input())) :
x = list(sys.stdin.readline().split())
if x[0] == 'L' and left: # 'L'이면서 left에 문자가 있을 경우
right.insert(0,left.pop())
elif x[0] == 'D' and right : # 'D'이면서 right에 문자가 있을 경우
left.append(right.pop(0))
elif x[0] == 'B' and left : # 'B'이면서 left에 문자가 있을 경우
left.pop()
elif x[0] == 'P' :
left.append(x[1])
print(''.join(left+right))
sys를 활용했음에도 불구하고, 아직도 시간 초과....!
예전에 수업에서 pop, insert 로 위치를 지정할 시에는 위치를 찾는데 시간이 오래 걸린다 하셨던게 얼핏 기억이 났음..!
gpt 한테 물어보니까, 내가 예측한게 맞았다.
리스트의 insert(0, ...) 및 pop(0) 연산이 리스트의 앞쪽에 원소를 삽입하거나 제거할 때 시간이 많이 걸립니다.
이러한 연산은 리스트의 모든 원소를 한 칸씩 이동시켜야 하므로 시간 복잡도가 O(n)입니다.
그래서 이번엔 pop, append로 맨 뒤에 추가하거나 삭제하는 방식을 썼고, reverse로 순서를 뒤집어서 결합했다.
# 4차 시도
import sys
left = list(sys.stdin.readline().strip()) # strip() 안쓰면 에러 남..! 이유 찾아보기
right = []
for i in range(int(input())) :
x = list(sys.stdin.readline().split())
if x[0] == 'L' and left: # 'L'이면서 left에 문자가 있을 경우
right.append(left.pop())
elif x[0] == 'D' and right : # 'D'이면서 right에 문자가 있을 경우
left.append(right.pop())
elif x[0] == 'B' and left : # 'B'이면서 left에 문자가 있을 경우
left.pop()
elif x[0] == 'P' :
left.append(x[1])
print(''.join(left+right[::-1])) # [::-1] reverse 와 같은 느낌
# print(*left+right[::-1],sep="") 도 가능!
드디어 성공,,,!!!!!!!
stack 예전에 얼핏 배웠던 것 같은데, 그 때, 제대로 코딩해보지 않았어서 그런지 어떻게 구현했는지 다 까먹었다....
이 문제로 stack 구현을 위한, 다양한 시도를 해볼 수 있었고, 앞으로 stack은 절대 안까먹을 듯 싶다..!
----------------------------------------------------------------------------------------------------------------
두 번째 문제는 '키로거'
5397번: 키로거 (acmicpc.net)
이 문제는 앞서 풀었던, 에디터 문제에 비해 시간 제한이 좀 길었다.
그래서 처음에는 stack 이지만 위치를 지정해서 맞는 자리에 입력 시키는 방식으로 구현했으나, 시간 초과가 뜸..!!
# 1차 시도 - 시간 초과
import sys
import re
answer = []
for _ in range(int(input())) :
password = list(sys.stdin.readline().strip())
left = []
right = []
for i in range(len(password)) :
if password[i] == '<' and left :
right.insert(0,left.pop())
elif password[i] == '>' and right :
left.append(right.pop(0))
elif password[i] == '-' and left:
left.pop()
elif re.match(r'[A-z0-9]', password[i]) :
left.append(password[i])
answer.append(''.join(left) + ''.join(right))
print(*answer, sep = '\\n')
# 2차 시도- insert, pop 위치 지정 없앰
import sys
import re
answer = []
for _ in range(int(input())) :
password = list(sys.stdin.readline().strip())
left = []
right = []
for i in range(len(password)) :
if password[i] == '<' and left :
right.append(left.pop())
elif password[i] == '>' and right :
left.append(right.pop())
elif password[i] == '-' and left:
left.pop()
elif re.match(r'[A-z0-9]', password[i]) :
left.append(password[i])
answer.append(''.join(left) + ''.join(right[::-1]))
print(*answer, sep = '\\n')
따라서, 에디터 문제처럼, 위치 지정하지 않고, 하나씩 쌓아가면서, 마지막에 reverse로 뒤집어 붙이는 방식을 활용했다.
이번에는 reverse 코드를 쓰지 않고, [::-1]를 활용!
이건 리스트 뒤에서 부터 값을 추출하는 방식이다. 이게 더 깔끔해보이기는 함..
또, 지난 주에 공부했던 '*'를 활용함! 하나씩 차근 차근 배워 가는게 넘 잼따.
그리고 re 패키지를 불러와서 정규식을 활용해봤다.
ord 순서가 A-9까지 연속적으로 이어져 있어서, r'[A-z0-9]'를 r'[A-9]'로 작성해도 된다.
----------------------------------------------------------------------------------------------------------------
세 번째 문제는 '요세푸스 문제'
1158번: 요세푸스 문제 (acmicpc.net)
이 문제도 stack 같이 하나씩 쌓아가려 했는데, 이전까지 풀었던 방식과 조금 달랐다.
1차 시도 - pop index out of range 오류
N, K = map(int, input().split())
lst = list(range(1,N+1))
answer = []
num = K-1
while lst :
if num < len(lst) :
answer.append(lst.pop(num))
num += (K-1)
elif num >= len(lst) :
while num < len(lst) :
num -= len(lst)
answer.append(lst.pop(num))
num += (K-1)
print(f"<{', '.join(map(str, answer))}>")
요세푸스가 원형의 형태여서 생각하는데 조금 어려웠는데, 이렇게 구현했더니, index out of range 오류가 떴다.
순서대로 디버깅 해보니, while 돌다가 마지막 부분에서 index 오류가 뜬 것을 알 수 있었다.
이번엔 값을 나누어 나머지만 입력하는 식으로 진행했다.
진작에 이렇게 할걸,,,
2차 시도 - % 이용해서 나머지 값 받기
N, K = map(int, input().split())
lst = list(range(1,N+1))
answer = []
num = K-1
while lst : # num %= len(lst) 로 인덱스 현재 길이 내에 있도록 설정
num %= len(lst)
answer.append(lst.pop(num))
num += (K-1)
print(f"<{', '.join(map(str, answer))}>")
코드도 훨씬 간단하고, 이렇게 처음에 나머지로 변환시켜 버리면 index 에러가 뜰 일이 없다..!!
----------------------------------------------------------------------------------------------------------------
이렇게 이번주에 풀었던 7개의 문제 중에 중요한 문제 3개면 정리해봤다.
7개의 문제가 stack 관련 문제였기에, 이번주에 stack 에 대한 개념을 완벽하게 잡을 수 있었다.
앞으로 stack 문제 나와도 어렵지 않게 풀 수 있을 것 같음!!
역시, 사람은 복습을 해야해...
다음 주도 화이팅 !
'Python Coding Test' 카테고리의 다른 글
| [파이썬 코테] Array (알파벳 개수, 방 번호, 두수의 합) (1) | 2024.12.08 |
|---|