[BOJ] 1874: 스택 수열

이슬비·2022년 3월 24일

Algorithm

목록 보기

19/110

처음으로 ~! 다른 사람의 풀이를 봤다! 괜찮다 ~! 하루종일 고민하기보다는 다른 사람의 풀이를 제대로 이해하고 나한테 녹여내기만 한다면... 된다고 했다 !!!

1874: 스택 수열

이건 진짜 문제부터 이해하기 어려웠다... 1~n까지의 수열을 내가 가지고 있을 때, 입력으로 들어온 수열을 pop과 push를 이용해서 만들 수 있으면 +와 -를 이용해 나타내보라, 만들 수 없으면 NO를 출력해라! 라는 문제였다.

음, 수열이 3개가 있다고 생각하면 쉽다.

내가 가진 수열: 1부터 n까지 정렬된 수열
입력으로 주어진 수열 (정답 레이블)
빈 수열

여기서 내가 가진 수열로 pop과 push를 하게 된다. 입력으로 주어진 수열에 맞춰 pop과 push를 진행하다가, pop으로 나온 숫자들은 다시 빈 수열 (3번 수열)에 차곡차곡 쌓는다. 그리고 내가 가진 수열(1번 수열)에서 더 이상 push할 게 없다면! 그런데 pop 명령이 있다면! 빈 수열에서 (3번 수열) 차례대로 꺼내서 정답에 맞게 쌓는 것이다!

휴 정말 이해하는데 힘들었다.
문제를 이해하는 것도 이해하는 것이지만, 입력으로 주어진 수열을 만족하지 못하는 조건을 생각하는 것도 어려웠다. 그래서 생각해보니, 꼭대기 top에서부터 간격이 1씩 증가하는 게 있으면 만족하지 못하는 것이 아닌가...! 생각했다. 네... 딱 여기까지만 생각나고 더 이상 생각에 진전이 없어서 결국 인터넷을 찾아봤다.

1. 내 풀이: 실패

뭐 사실 실패라고 할 것도 없음... 그냥 끝까지 코드를 작성하지 못했으니...

import sys

N = int(sys.stdin.readline())
seq = [int(sys.stdin.readline().strip()) for _ in range(N)]

for i in range(1, len(seq)):
    err = seq[i-1]+1
    if err == seq[i]:
        print('NO')
        break

이렇게 하면... 예제 2번에 맞게 NO를 잘 출력하기는 한다...

2. 다른 풀이: 성공

역시 이번에도 깨지고 부서져라님의 풀이를 참고했다.

import sys

N = int(sys.stdin.readline())
s = []
op = []
count = 1
temp = True

for i in range(N):
    num = int(sys.stdin.readline().strip())
    while count <= num: 
        s.append(count)
        op.append('+')
        count+=1
    if s[-1] == num:
        s.pop()
        op.append('-')
    else:
        temp = False

if temp == False:
    print('NO')
else:
    for i in op:
        print(i)

(출처: https://pacific-ocean.tistory.com/231)

놀라운 건 이 풀이를 보고도 "우오아아앗...!!" 이 아닌... "어...?" 라는 것...^^ 풀이를 이해하는데도 한참 걸렸다.

하나하나 뜯어보자.

import sys

N = int(sys.stdin.readline())
s = []
op = []
count = 1
temp = True

일단 몇 개의 숫자를 입력 받을지를 정해주는 N을 정의한다. 그리고 들어오는 숫자를 담을 리스트 s, pop과 push 를 표시할 리스트 op도 추가해준다. 사실... count를 정의하는데 있어서는 정확히 이해하지 못했는데, 나중에 들어올 num과 비교를 해주기 위해 + s에 count 값을 append 하기 위해 쓰이는 것 같다 (?) 그리고 만들 수 있는 수열인지 아닌지를 판단해줄 temp 변수를 추가해준다. True 값으로 설정해줬기 때문에 일단은 만들 수 있다!고 생각하자는 의미.

for i in range(N):
    num = int(sys.stdin.readline().strip())
    while count <= num: 
        s.append(count)
        op.append('+')
        count+=1
    if s[-1] == num:
        s.pop()
        op.append('-')
    else:
        temp = False

N을 이용한 for 문과 num을 통해 수열의 숫자를 하나씩 입력 받는다. 이 부분의 코드를 보면 아까 count를 왜 썼는지를 알 수 있는데, num을 통해서 들어오는 숫자들은 꼭대기 top의 숫자들이다. 그런데 우리는 맨 아랫 부분부터 차곡차곡 쌓아 나가야 하니까 이 둘을 비교하면서 s에 count 값들을 append 하는 것이다.

그래서 while 문을 통해서 num보다 count가 작으면 계속해서 count를 s에 append, op에 +(push)를 append를 해준다.

자, 그렇게 num까지 append를 해줬는데, s의 맨 끝 숫자가 num이다 ?! 그러면 다시 빼준다. 왜냐하면 우리의 num은 top에서부터 내려오기 때문이다. 아직 s의 중간 부분(?)에 쌓이면 안되는 것임.
이 부분은 나도 이해가 잘 안 돼서 하나하나 다 찍어보면서 이해해보려 했다.

여기서 5까지 정상적으로 작동되는데, num이 count보다 작아진 순간 while 문이 아닌 바로 if-else문으로 넘어가게 되고, s[-1] = 4이고 num =3 이므로 else문을 따르게 된다. 그러면 temp에 false가 저장되는 것이다. 더 이상 빼고 더하고의 문제가 아니라 그냥 만들 수 없는 수열인 것!!!

if temp == False:
    print('NO')
else:
    for i in op:
        print(i)

그 후에는 쉽다. 그냥 저장된 값 찍어내기...

3. 에필로그: 새로운 오류

temp를 이용해서 조건을 판단하지 말고 내가 만든 조건문으로는 판단할 수 없을까?! 해서 코드를 조금 수정해서 돌려봤다.

import sys

N = int(sys.stdin.readline())
s = []
op = []
count = 1
temp = True

for i in range(N):
    num = int(sys.stdin.readline().strip())
    while count <= num: 
        s.append(count) 
        op.append('+')
        count+=1
    if s[-1] == num:
        s.pop()
        op.append('-')
    else:
        temp = False
    print(f'num: {num}, count: {count}, s: {s}, op: {op}, temp: {temp}')

for i in range(1, len(s)):
    err = s[i-1]+1
    if err == s[i]:
        print('NO')
        break

for i in op:
    print(i)