[백준] 1874 스택 수열

[백준] 1874번 스택 수열

자료구조 / 스택

 

 

 

[문제]

 

스택문제!

 

 

처음에 문제 이해가 안됨

나같은 사람이 있나 싶어서 물어보기에 찾아보니 바로 '문제 이해가 안가요..'가 있었음ㅎㅎ

바로 해당 문제 이해하고 문제 풀이를 함

 

 

※ 참고한 다른분의 질문 검색

 

생각보다 푸는데 1시간10분정도로 오래 걸림

은근 까다로웠음

 

 

 

[과정]

 

• 입력값을 저장한 배열(stack)과 현재 저장되고 있는 스택(tmp_stack)의 배열을 선언
• 스택에 들어가는 숫자(cnt)와 스택과 비교할 스택의 인덱스(idx)를 선언
• 무한루프
  • 숫자가 n 초과가 되거나 인덱스가 n 이상이 된다면 break
  • 스택(tmp_stack)이 비어있을 때
    • 첫번째 숫자의 경우라면 '+'추가
    • 중간에 스택이 비는 경우라면 cnt를 1증가해주고 '+'추가
    • continue
  • 현재 idx의 스택의 값이 저장되고 있는 스택(tmp_stack)의 마지막 원소와 같다면
    • pop을 해주고 '-'를 추가한 후 idx를 1증가
  • 그렇지 않다면
    • cnt를 1증가(다음 숫자로 넘어가기 위해)
    • tmp_stack에 cnt를 추가해주고 '+' 추가
• 만약 남아있는 스택(tmp_stack)의 원소가 있다면 해결할 수 없는 경우이기 때문에 'NO'출력
• 남아있는 원소가 없다면 저장된 기호들을 출력

 

 

 

 

[소스코드]

 

# 스택 수열

import sys
input = sys.stdin.readline

result = []      # 기호 저장 
stack = []     # 만들어야하는 수열 
tmp_stack = []     # 차례대로 숫자가 들어가는 스택 
n = int(input())
for _ in range(n):
    tmp = int(input())
    stack.append(tmp)

cnt = 1      # 스택에 들어가는 숫자 오름차순 
idx = 0      # stack의 인덱스
while True:
    if idx >= n or cnt > n:     # 핵심 
        break
    if len(tmp_stack) == 0:
        if idx == 0:           # 첫번째 숫자를 넣는 경우
            tmp_stack.append(cnt)
            result.append('+')
        else:                  # 중간에 스택이 모두 pop되어 비어있게 되는 경우 
            cnt += 1
            tmp_stack.append(cnt)
            result.append('+')
        continue
    
    if stack[idx] == tmp_stack[-1]:
        data = tmp_stack.pop()
        idx += 1
        result.append('-')
    else:
        cnt += 1
        tmp_stack.append(cnt)
        result.append('+')

if len(tmp_stack) != 0:
    print('NO')
else:
    for num in result:
        print(num)

다른 고수분들의 코드를 보면 엄청 간결하고 깔끔해서 대단하다

 

---

 

[통과]

 

 

---

 

※ 반례

 

5

3

2

1

4

5

 

answer

+

+

+

-

-

-

+

-

+

-