알고리즘 공부(C++)

백준 1874 스택 수열

혀니리리 2022. 9. 4. 06:16
728x90

1874번: 스택 수열 (acmicpc.net)

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

스택 문제여서 겁없이 도전했던 문제..

뭔가 알듯말듯 하면서도 좀 복잡해서 시간이 꽤나 걸렸는데

아니나 다를까 또!! 또간초과가 떠서 애를 먹었다..

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 중첩 구조를 피하자

728x90