[백준/1874] 스택 수열

 

📝 문제 이해

입력 받은 수열의 첫번째 항까지 모두 stack에 넣고, 스택의 마지막 원소를 pop하면 수열의 첫번째 항이 완성된다.

 

예컨대 4 3 6 8 7 5 2 1 수열이 있으면 ,2,3,4까지 stack에 push하고 pop을 하면 4가 pop 되면서 수열의 첫번째 항이 완성된다.

 

만약 stack의 top(가장 마지막에 push된 값)이 입력 받은 수열과 같다면 pop해주고, 또 다시 다음 항의 수열만큼 stack에 push하고 조건문을 통해 검사하고.. 다음항이 stack의 top에 없다면 'NO'를 출력해준다.

 

 

🔎 내가 처음 짠 코드 

#중간 단계 메모메모
n = int(input())
sequence = range(1,n+1)
num, stack = [], []

for _ in range(n): # 입력 받기
    num.append(int(input())) 
    
for i in range(num[0]):
    stack.append(sequence[i]) # 수열의 첫번째 항까지 stack에 모두 push & '+' 출력
    print('+')

for _ in range(num[1]):
    if num[1] in stack:
        stack.pop()
        print('-')



    

print(stack)

---

🔎 수정한 코드

import sys
n = int(input())
stack = []
seq = 1

for _ in range(n): # 입력 받기
    num = int(sys.stdin.readline())
    while seq <= num: # 입력 받은 수까지 stack에 오름차순으로 push
        stack.append(seq) 
        print('+')
        seq += 1 # 1씩 증가하는 수열 sequence
    
    if stack[-1] == num:
        stack.pop()
        print('-')

    else:
        print('NO')
        break

 

 

1. 시간 초과를 없애기 위해 sys.stdin.readline()으로 입력을 받았다.

sys.stdin.readline()은 input() 함수와 달리 개행 문자(\n)을 포함해서 입력 받은 문자를 리턴하고, 입력으로 '문자열'을 받지 않기 때문에 input 함수보다 빠른 속도를 갖는다. 

2. while문 사용

예전부터 느끼는 거지만 나는 while에 대한 거부감이 있다..😅 while을 쓴다고 해서 무조건 복잡도가 커지는 건 아닌데 확률상의 이유만으로 거부하는 안좋은 색안경이 생긴 것같다. 이번 기회에 아주 타파하고!! 말겠다.

while문과 조건문 + break 조합을 적절하게 잘 쓰면 문제 조건에 부합하면서 복잡도도 적당히 사용할 수 있다는 점을 깨달았다.

 

---

이렇게 수정을 했지만 출력 초과가 떴다.

그 이유는 내가 입력 받은 수까지 stack에 push할 때 print('+')를 하도록 설정해뒀기 때문이다.

 

💯 최종

import sys
n = int(input())
ans, stack = [], []
seq = 1
flag = True


for _ in range(n): # 입력 받기
    num = int(sys.stdin.readline())
    while seq <= num: # 입력 받은 수까지 stack에 오름차순으로 push
        stack.append(seq) 
        ans.append('+')
        seq += 1 # 1씩 증가하는 수열 sequence
    
    if stack[-1] == num:
        stack.pop()
        ans.append('-')

    else:
        print('NO')
        flag = False
        break

if flag == True:
    print(*ans)

---

💡 배운 점

어떤 값이 될 때까지 작업을 수행하는 일을 여러번 해야 한다면(정확히 n번. 딱 떨어지게 조건걸기 힘든 경우),

while문을 사용하는 것이 좋다. 이때 무한루프에 빠지지 않게 조건문과 break의 조합으로 적절하게 반복문을 빠져 나오도록 구현하는 데에

집중 해야 한다.