[백준] 1874번 : 스택 수열

letsbebrave·2022년 1월 14일

codingtest

목록 보기

22/146

문제

느낀점

stack을 이용할 때 count같은 변수를 활용해서 stack에 하나
씩 append해주는 것이 어려웠다. 특히 연달아서 값을 pop해줘야 할 때 어떻게 해줘야 하나 발상하는 게 쉽지 않았다.
모든 경우의 수를 고려해서 문제를 스스로 풀긴 했지만, 시간초과가 떠서 결국 다른 분의 코드를 참고했다.

또한 하나의 수를 입력할 때마다 stack에 push 해주고 해당 stack의 마지막 값이 pop될 수 있는지 없는지 따져주는 방법의 반복은 잘 써본 적이 없어서 (입력 때마다 그때그때 result 리스트에 +나 - 더해줌) 애를 먹었다.

중요한 것

반복문을 사용할 때는 한 개당 몇 개의 반복을 거쳐야 하는지 구조를 생각해보고 작성해야 함

target에 수 입력
while 문 count < target 조건으로 stack에 target 이하의 수를 넣어줌 (push +)
해당 스택의 마지막값 == target이면 빼내기 (pop -)
해당 스택의 마지막값 != target이면 no변수 False로 변경

개념

리스트.pop(x)

pop(x)는 리스트의 x번째 요소를 돌려주고 그 요소는 삭제
pop()은 리스트의 마지막 요소를 삭제

"구분자".join(리스트)

리스트의 값과 값 사이에 '구분자'에 들어온 구분자를 넣어서 하나의 문자열로 만들어서 반환해줌

ex.'\n'.join(리스트) : 리스트 원소를 한 줄씩 개행한 문자열로 반환

## 시간초과 코드

n = int(input())
s = []
b = []
for i in range(n):
    s.append(int(input()))
    b.append(i+1)

a = []
pop = len(s)
j = 0
answer = []

for i in range(n):
    a.append(b[i])
    # print('+')
    answer.append(1)
    
    while pop >= 1 and len(a) > 0:
        if a[len(a)-1] == s[j]:
            # print('-')
            answer.append(0)
            a.remove(a[len(a)-1])
            j += 1
            pop -= 1
        else:
            break

if pop != 0 :
    print('NO')
else :
    for i in answer:
        if i == 1:
            print('+')
        else :
            print('-')

정답 코드

n = int(input())
count = 0
stack = []
result= []
no = True

# 반복문을 사용할 때는 한 개당 몇 개의 반복을 거쳐야 하는지 
# 구조를 생각해보고 작성해야 함

for i in range(n):
    target = int(input())
    
    while count < target:
        count += 1
        stack.append(count)
        result.append("+")
    
    if stack[-1] == target :
        result.append("-")
        stack.pop()
    else :
        no = False
            
            
if no == False :
    print('NO')
else :
    print("\n".join(result))