스택 문제여서 겁없이 도전했던 문제..
뭔가 알듯말듯 하면서도 좀 복잡해서 시간이 꽤나 걸렸는데
아니나 다를까 또!! 또간초과가 떠서 애를 먹었다..
import sys
n = int(sys.stdin.readline())
lst = []
for i in range(n):
lst.append(int(sys.stdin.readline()))
stack = []
res = []
pp = 0
for i in range(n):
if lst[i] not in stack:
for j in range(pp, lst[i]):
stack.append(j + 1)
res.append("+")
pp = max(pp, stack.pop())
res.append("-")
else:
while stack[len(stack) - 1] == lst[i]:
stack.pop()
res.append("-")
if len(stack) == 0:
break
if len(res) != n * 2:
print("NO")
else:
print('\n'.join(res))
이것이 시간초과가 났던 코드이다. 열심히 출력 형태도 sys.stdin.readline()으로 바꿔봤는데도 시간초과는 사라지지 않았다.
로직은 다 잘 나왔다. 설명해보자면
1.수열의 길이가 n 이니 lst를 참조하는 n동안 lst[i]가 stack에 있으면 lst[i] - pp + 1만큼 스택과 res에 더해주고
2.pp는 stack을 pop하고, 그것과 기존 pp를 비교해서 구하는 식으로 했다.
3.pop했으니 res에 '-'추가해줬고...
4.stack에 lst[i]가 들어있지 않은 경우에는 stack의 가장 뒤의 수와 lst[i]를 비교해서 같으면 pop을 해주고 stack이 남아있지 않으면 break해주었다.
5.마지막에 result는 무조건 n * 2이 되어야 하기 때문에 그 조건을 NO로 해주고 나머지는 출력!
으로했더니 결과는 잘 나왔다.
아니... 결과만 잘 나오면 좀 봐주지 이정도면 그렇게 시간초과되지 않는것같은데.. 속상하다..ㅠ
<그렇게 해서 참고해서 고친 코드>
import sys
n = int(sys.stdin.readline())
stack = []
res = []
pp = 1
for i in range(n):
num = int(sys.stdin.readline().strip())
for i in range(pp, num + 1):
stack.append(i)
res.append("+")
pp += 1
if stack[-1] == num:
stack.pop()
res.append("-")
if len(stack) != 0:
print("NO")
else:
print('\n'.join(res))
이는
1.매 for문마다 num을 새로 구해서 그 num만큼을 stack 에 append하고
2.그 num이 stack의 맨 윗값과 같을 때는 pop을 해줌
key point : 한 num마다 딱 그 num에 한해서만 연산을 해주고,
for문의 range가 0보다 작을때는 아예 실행하지 않는다는 점을 이용한 코드이다.
이렇게 보니 내 코드는 계속 처음부터 전체를 훑는 in 연산이나 for 연산이 정답코드에 비해 훨씬 많았던 것 같다.
이제부터 이런 문제가 있을 때는 정답코드처럼 그때그때 num값을 할당받아가면서 순차적으로, 그 안에서 처음부터 끝까지 다시 돌리는 for / in 중첩 구조를 피하자
'알고리즘 공부(C++)' 카테고리의 다른 글
백준 2805 나무 자르기 - 이분 탐색 (0) | 2022.09.06 |
---|---|
백준 1935 후위 표기식2 ( stack ) (0) | 2022.09.05 |
백준 2417 정수 제곱근 (0) | 2022.09.03 |
백준 1158 요세푸스 문제 - 큐 (0) | 2022.09.03 |
백준 10816 숫자카드 2 - 딕셔너리 (0) | 2022.09.02 |