풀이
- 먼저 예제를 보면서 각 사람이 이동하는 방식을 이해하려고 노력했다.
- 앞으로 편의상 현재 줄 서있는 곳을 now, 한 명씩 설 수 있는 공간을 stack으로 쓰겠다.
- 해당 번호표는 간식받는 곳으로 이동해야 되는데, 해당 번호표는 now와 stack 모두에 존재할 수 있다.
- 번호표가 now에 존재한다면 그 앞에 있는 사람들을 stack에 하나씩 이동시켜주면 된다.
- 번호표가 now에 없다면 stack에 있을 것인데, stack의 맨 뒤에 존재해야지만 스무스하게 이동해서 모든 사람이 간식을 순서대로 받을 수 있다. stack에서는 더 이상 이동시킬 데가 없기 때문이다.
- 즉, 스택에서 맨 뒤가 아닌 경우에 해당 번호표가 존재한다면 순서대로 간식을 받을 수 없게 되는 것이다.
- 따라서 해당 번호표가 이동할 수 있는 경우의 수는 다음 3가지로 좁혀진다.
- 현재 줄 서 있는 곳 맨 앞
- 한 명씩 설 수 있는 공간(스택) 맨 뒤
- 현재 줄 서 있는 곳에 있지만 맨 앞이 아닌 경우
- 그래서 이 3가지는 now와 stack이 모두 빌 때까지 계속 간식을 받는 곳으로 이동시키고(=now나 stack에 하나라도 번호가 존재하면 시행), 이 경우의 수에 해당하지 않는 순간은 더 이상 이동이 불가하게 된다(break).
- 이동이 멈춘 시점에 stack이 비어있다면 모두가 순서대로 간식을 받은 것이 되겠다.
코드
import sys
input = sys.stdin.readline
N = int(input())
now = list(map(int, input().split()))
stack = []
next = 1
while now or stack:
if now and now[0] == next:
now.pop(0)
next += 1
elif stack and stack[-1] == next:
stack.pop()
next += 1
elif next in now:
for _ in range(now.index(next)):
stack.append(now.pop(0))
else:
break
if stack:
print("Sad")
else:
print("Nice")- 인덱스에 접근할 때 now나 stack이 비어 있으면 에러가 뜬다. 그렇기 때문에 꼭 들어있는지 확인하면서 인덱스에 접근하자.
구글링한 코드
- 처음에 다른 사람들 코드를 도저히 이해하지 못하겠더라.. 그런데 정답을 맞추고 나니까 이해할 수 있었다.
- 사실 그냥 내 코드를 예쁘게 정리한 거에 가까웠다. 내가 직관적으로 경우의 수로 푼 거라면 구글링한 코드는 조금 더 알고리즘스럽게 푼 거랄까?
- 물론 다양한 방법이 있었지만, 가장 많이 보이는 그리고 나랑 거의 같은 방식으로 푼 코드들을 참고하며 작성해 보았다.
import sys
input = sys.stdin.readline
N = int(input())
now = list(map(int, input().split()))
stack = []
next = 1
for i in now:
if i == next: # 해당 번호표이면 간식 받는 곳으로 이동
next += 1
else: # 해당 번호표가 아니라면 스택으로 이동
stack.append(i)
# 스택의 맨 위에 해당 번호표가 존재하면 계속 간식 받는 곳으로 이동
while stack and stack[-1] == next:
stack.pop()
next += 1
if stack:
print("Sad")
else:
print("Nice")- 처음에 도대체 왜 stack and stack[-1] == next에 while문을 쓰는지 이해하지 못했다.
- 만약에 stack에 5, 4, 3 순으로 들어있다면 예쁘게 3, 4, 5 순서대로 간식을 받기 때문에 스택에서 pop하는 게 반복되는 것이다.
- 또한 처음에는 now에 있는 걸 하나씩 다 돌면 이동하지 못할 때는 어떻게 되는 거지?했는데, 이동하지 못하면 if문도, else문도, while문도 실행되지 않아서 아무런 변동이 없게 되는 것이다. 즉, 이동이 멈추는 것까지 표현된 것이다.
결론
-
손으로 막 적어가며 굉장히 오래 걸린 문제이다.
-
이동시키는 방식을 정리하는 게 어려워서 다른 사람 코드도 좀 보았지만 온전히 내 힘으로 풀긴 했다.
-
구글링한 코드는 내 스스로가 떠올리지는 못할 것 같다....
-
역대 가장 어려웠던 문제였다..
-
아래가 내가 푼 코드이다.
