10828번
이 문제를 풀기 위해서는 input() 대신 sys.stdin.readline()을 사용해야 한다.
둘은 기능 상 큰 차이는 없지만, 속도 차이가 커서 백준문제를 푸는 중
input으로 작업한 코드가 시간 초과가 났을 때,
바꿔 입력해주면 정답처리가 된다고 한다.
다만 모든 input을 전부 변경하기엔 번거롭기에,
import sys
sys.stdin.readline()을 코드 제일 위에 추가해준다면 input이 sys.stdin.readline()과 같은 속도를 갖게 된다.
다시 문제로 돌아와서
이 문제를 풀기 위해 다음과 같은 알고리즘을 생각했다.
- 명령의 수(N)를 입력 받는다.
- 스택은 리스트 형태로 생성한다.
- 명령의 수를 모두 수행할 때까지 명령을 받는다.
- 각각의 명령에 따른 동작은 if문으로 설계한다.
import sys
N = int(sys.stdin.readline())
stk = []
for i in range(N):
instruction = sys.stdin.readline().split()
if instruction[0] == 'pop':
pop = stk.pop() if stk else -1
print(pop)
elif instruction[0] == 'size':
print(len(stk))
elif instruction[0] == 'empty':
empty = 0 if stk else 1
print(empty)
elif instruction[0] == 'top':
top = stk[-1] if stk else -1
print(top)
else:
push = int(instruction[1])
stk.append(push)
10773번
이 문제를 풀기 위해서 생각한 알고리즘은 다음과 같다.
- 정수 K 입력을 받는다.
- 스택을 리스트 형태로 생성한다.
- 0이 입력되면 가장 최근에 입력한 수를 지운다.
- 입력된 숫자가 0이 아니라면 그 숫자를 스택에 추가한다.
import sys
input = sys.stdin.readline
K = int(input())
stk = []
for i in range(K):
num = int(input())
if num == 0: stk.pop()
else: stk.append(num)
print(sum(stk))
9012번
이 문제를 풀기 위해 생각한 알고리즘은 다음과 같다.
- 테스트 개수 K개를 입력한다.
- 테스트 괄호를 입력한다.
- '(' 괄호가 입력되면 스택에 추가한다.
- ')' 괄호가 입력되면 스택을 검사한다.
- 스택이 비어있다면 'NO'를 출력하고, 그렇지 않다면 pop을 한 번 해준다.
K = int(input())
for i in range(K):
stk = []
bracket = input()
for i in bracket:
if i == '(':
stk.append(i)
elif i == ')':
if stk:
stk.pop()
else:
print('NO')
break
else: // break에 걸리지 않은 경우 재검사
if not stk:
print('YES')
else:
print('NO')
이 문제에서는 ')'괄호가 입력됐을 때, 스택에 추가하는 것이 아닌
스택을 검사를 한 후에 '('가 있으면 pop
비어 있다면 'NO'를 출력하는 생각을 하는 것이 어려웠던 것 같다.
4949번
방금 전 문제와 비슷하지만 좀 더 까다로운 문제이다.
내가 처음 생각한 알고리즘은 다음과 같다.
- '.'이 입력되면 종료
- 열린 괄호는 스택에 추가한다.
- 괄호를 닫을 때 스택이 비어있거나, 스택의 top이 닫는 괄호와 짝이 맞지 않다면 거짓이다.
import sys
while True:
sen = sys.stdin.readline().rstrip()
stack = []
result = True
if sen == '.':
break
for i in sen:
if i == "(" or i == "[":
stack.append(i)
elif i == ")":
if not stack or stack[-1] == "[":
print("no")
result = False
break
else:
stack.pop()
elif i == "]":
if not stack or stack[-1] == "(":
print("no")
result = False
break
else:
stack.pop()
if len(stack) == 0 and result == True:
if not stack:
print('yes')
else:
print('no')
이 문제를 풀면서 rstrip()을 처음 활용해봤다.
rstrip에 대해 좀 더 찾아보니 sys 라이브러리를 사용할 때는
반드시 rstrip()를 호출해줘야 한다고 한다.
(readline()은 \n도 받으므로, 이 공백문자를 제거하는 역할을 한다.)
기억하자!
1874번
이번 문제는 솔직히 문제 자체를 이해하는 데도 너무 어려웠다.
문제가 이해가 안돼서 접근 자체를 어떻게 해야할 지 막막했고,
나름대로 최대한(?)의 알고리즘을 생각해보았다.
- n까지 수를 입력한다.
- 스택에 수를 입력하되, 오름차순 정렬로 저장한다.
- pop 명령 시 스택에 입력된 순서대로 수행한다.
2번까지 작성하고 나니까 정렬된 스택 요소들을
다시 입력된 순서대로 pop이 될 수 있도록 하는 지 방법을 떠올리기 힘들었다.
그래서 다른 분의 풀이를 참고했고, 문제 접근 자체가 잘못됐다는 것을 알게됐다.
출처
[백준] 1874번 스택 수열 - Android Teacher
n = int(input())
stack = []
answer = []
flag = 0
cur = 1
for i in range(n):
num = int(input())
while cur <= num: # 입력한 수를 만날 때 까지 오름차순으로 push
stack.append(cur)
answer.append("+")
cur += 1
# 입력한 수를 만나면 while문 탈출. 즉 cur = num일 때 까지 while문을 돌아 스택을 쌓는다.
if stack[-1] == num: # stack의 TOP이 입력한 숫자와 같다면
stack.pop() # 스택의 TOP을 꺼내 수열을 만들어 준다.
answer.append("-")
else: # stack의 TOP이 입력한 수가 아니면 주어진 스택을 만들 수 없다.
print("NO") # 왜냐하면 12345 처럼 오름차순으로 스택이 입력되는데
flag = 1 # TOP이 num보다 크면 num은 TOP보다 더 아래에 쌓여있기 때문이다.
break
if flag == 0:
for i in answer:
print(i)깔끔하다..
예제로 N = 8이고 다음줄부터 4, 3, 6, 8, 7, 5, 2, 1을 입력한 상황을 예로 들어보면
위의 코드는 다음과 같은 과정으로 접근했다.
-
첫 입력이 4이므로 첫 번째로 pop한 숫자는 4가 되어야 한다.
이를 위해서는 1, 2, 3, 4가 이미 스택 안에 있어야 한다.
그래서 입력한 수를 만날 때 까지는 계속 push를 해야 한다. -
4를 꺼내 스택은 현재 1, 2, 3인 상황이고, 다음으로 3이 주어졌으므로
현재 스택에서 pop을 한다. -
그 다음 입력으로 6이 주어졌으므로, 다시 6을 만날 때 까지 이전 숫자를 push한다.
위의 알고리즘과 나의 알고리즘을 비교했을 때,
- 수를 입력하면 그보다 작은 수까지 모두 push 한다.
- push와 동시에 pop을 한다.
두 가지의 생각을 하지 못했다.
이 문제를 풀면서 또 하나의 중요한 포인트는
stack에서 pop할 숫자(top)가 입력한 숫자가 아닐 경우(작을 경우)
top값이 입력한 숫자보다 커서, 입력한 수를 꺼내기 위해 계속 pop을 해야 하기 때문에
pop한 수들의 수열이 정답과 일치하지 않게 된다는 점을 고려해야 한다는 것이다.
예를 들어 1, 2, 5, 3, 4를 입력으로 가정해보면,
1을 입력했을 때 스택은 [1] -> pop -> 1
2를 입력했을 때 스택은 [2] -> pop -> 2
5를 입력했을 때 스택은 [3, 4, 5] -> pop -> 5
3을 입력했을 때 스택은 [3, 4] -> pop -> 4
3 입력시 3이 먼저 나와야 하는데 4가 나온 것이다.
이를 조심해야 한다.
다른 분들의 풀이를 보면서 코드 작성시 자주 사용됐던 기법(?)을 발견했는데,
flag = 0
cur = 1
for i in range(n):
num = int(input())
while cur <= num: # 입력한 수를 만날 때 까지 오름차순으로 push
stack.append(cur)
answer.append("+")
cur += 1
# 입력한 수를 만나면 while문 탈출. 즉 cur = num일 때 까지 while문을 돌아 스택을 쌓는다.
if stack[-1] == num: # stack의 TOP이 입력한 숫자와 같다면
stack.pop() # 스택의 TOP을 꺼내 수열을 만들어 준다.
answer.append("-")
else: # stack의 TOP이 입력한 수가 아니면 주어진 스택을 만들 수 없다.
print("NO") # 왜냐하면 12345 처럼 오름차순으로 스택이 입력되는데
flag = 1 # TOP이 num보다 크면 num은 TOP보다 더 아래에 쌓여있기 때문이다.
break
if flag == 0:
for i in answer:
print(i)flag 부분이다.
기본적으로 flag 객체를 0으로 참조해놓고
조건을 만족하는 지에 따라 참조 값을 1로 변경하는 것이다.
이를 이용하면 제어문을 모두 만족한 후 스택을 재검사 하는 과정에서
유용하게 사용할 수 있다는 점이다.
앞으로 자주 이용하게 될 것 같다.
어려운 알고리즘 .. 화이팅
