[Baekjoon] 12789번 도키도키 간식드리미 문제 리뷰
개요
이전에 코딩 테스트에 주로 나오는 알고리즘들에 대해서 알아보며 관련하여 포스트도 작성해 보았습니다. 이제는 공부한 내용을 토대로 코딩 테스트도 준비할겸 해서 백준에 있는 여러 문제들을 풀어보면서 리뷰할만한 문제들이 있으면 리뷰를 하고자 이렇게 포스트 작성하게 되었습니다. 저 혼자서 문제를 풀이한 거라 다른분들에 비해 코드가 너저분하거나 부족해 보일 수도 있습니다만 저의 오답 노트라고 생각하시고 봐주시면 좋겠습니다!
12789번 도키도키 간식드리미
문제 소개
인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다.
그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.
사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.
현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.
입력
입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N($1<=N<=1000$) 이 주어진다.
다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1, 2, $\ldots$, N) 순서가 앞에서부터 뒤 순서로 주어진다.
출력
승환이가 무사히 간식을 받을 수 있으면 “Nice”(따옴표는 제외)를 출력하고 그렇지 않다면 “Sad”(따옴표는 제외)를 출력한다.
예제 입력
5
5 4 1 3 2
예제 출력
Nice
문제 풀이
첫 번째 시도
문제 유형이 스택과 큐였고, 문제에 있는 이미지를 봤을 때 누가봐도 스택을 사용하는 문제로 생각을 하였습니다. 그래서 스택은 따로 구현하지 않고, Python 의 리스트를 그대로 사용하기로 했습니다. 그리고 문제를 보니 현재 순서가 맞아야 간식 받는 곳으로 갈 수 있다고 하여 순서를 정해주었고, 이 순서는 문제에서 모든 학생들의 번호표(1, 2, $\ldots$, N) 순서가 앞에서부터 뒤 순서로 주어진다. 라고 하였기 때문에 순서는 1부터 시작하도록 하고 문제 풀이를 진행했고 아래 코드를 제출했습니다. 또한 간식 받는 곳인 out 리스트를 이용해 최종 답을 구하도록 하였는데 그 방법은 N 의 최대가 1,000 인 것을 감안하여 만약에 out 에 있는 번호표들이 정렬이 되었다면 승환이가 간식을 먹을 수 있을 것이고 그게 아니라면 못 먹기 때문에 out 리스트를 복사해 정렬을 진행했고, out 리스트와 out 리스트를 복사하고 정렬시킨 리스트의 각 요소들을 비교하도록 하여 만약 중간에 요소가 하나라도 다른게 있으면 Sad 를 모두 동일하다면 Nice 를 출력하도록 구현하였습니다. 오답인 코드이기 때문에 복사 기능을 추가히진 않았습니다.
"""
baekjoon 12789
"""
import sys
input = sys.stdin.readline
# N 을 받아옴
n = int(input())
# 학생들의 번호표들을 리스트 형태로 받아옴
wait_list = list(map(int, input().split()))
# 주어진 번호표가 순서대로 정렬이 잘 되는지 체크하기 위한 boolean 변수
judge = True
# 한 줄로 설 수 있는 라인을 스택으로 표현
stack = []
# 순서대로 들어갔는지 확인하기 위한 리스트
out = []
# out 에 넣어주기 위해 현재 순서를 체크하기 위한 변수 번호표가 1~N 까지 주어진다고 했으므로 1로 시작
current_order = 1
# 번호표 리스트에서 순서대로 번호표를 가져옴
for i in wait_list:
# 현재 순서와 번호표를 비교해서 순서가 맞다면 out 리스트에 추가하고 현재 순서를 하나 증가
if i == current_order:
out.append(i)
current_order+=1
else: # 현재 순서와 번호표가 일치 하지 않는다면
# 스택이 비어있지 않다면 스택의 맨 위와 현재 순서를 비교
if len(stack) > 0 and stack[-1] == current_order:
# 만약 스택의 맨 위 번호표와 현재 순서가 일치하다면 out에 추가하고 스택의 맨위 요소 pop
out.append(stack[-1])
stack.pop()
# 현재 순서 1 증가
current_order+=1
# 현재 번호표는 스택에 추가
stack.append(i)
else: # 스택이 비었거나, 스택의 맨위 요소가 현재 요소와 맞지 않다면 스택에 현재 번호표 추가
stack.append(i)
# 스택에 남아 있는 요소들 out 에 추가
while stack:
out.append(stack[-1])
stack.pop()
# 정렬된 out 리스트
sorted_out = list(out)
sorted_out.sort()
#out 리스트와 정렬된 out 리스트 비교 중간에 하나라도 다른 요소가 있다면 judge 변수에 False 값 대입
for i in range(len(out)):
if out[i] != sorted_out[i]:
judge = False
break
# judge 가 True 이면 Nice 출력 그게 아니라면 Sad 출력
if judge:
print("Nice")
else:
print("Sad")
위 코드로 채점을 진행했지만 오답이라고 하였고, 여기서 더 이상 진행할 수가 없어 게시판을 통해 도움을 구했습니다.
두 번째 시도
게시판을 보니 짠 코드에 대한 반례를 알려주는 사이트가 있었고 그 사이트에서는 다음과 같은 반례들을 맞추지 못하고 있다고 알려주었습니다.
입력
5
3 2 1 5 4
실제 정답
Nice
코드 결과
Sad
위 예제를 보니 최초 번호표 리스트를 순회하며 동작할 때 현재 번호표가 현재 순서랑 맞지 않아 스택에 있는 요소들을 검사할 때 스택의 맨 위에 있는 요소가 현재 순서랑 동일하지 않을 때까지 스택의 맨 위 요소와 현재 순서를 계속 비교하도록 하는 로직이 들어가야 한다는걸 알게 되었고 앞에서 설명한 것과 같이 수정하였더니 맞았다는 것을 확인할 수 있었습니다. 정답 코드는 아래와 같습니다.
"""
baekjoon 12789
"""
import sys
input = sys.stdin.readline
# N 을 받아옴
n = int(input())
# 학생들의 번호표들을 리스트 형태로 받아옴
wait_list = list(map(int, input().split()))
# 주어진 번호표가 순서대로 정렬이 잘 되는지 체크하기 위한 boolean 변수
judge = True
# 한 줄로 설 수 있는 라인을 스택으로 표현
stack = []
# 순서대로 들어갔는지 확인하기 위한 리스트
out = []
# out 에 넣어주기 위해 현재 순서를 체크하기 위한 변수 번호표가 1~N 까지 주어진다고 했으므로 1로 시작
current_order = 1
# 번호표 리스트에서 순서대로 번호표를 가져옴
for i in wait_list:
# 현재 순서와 번호표를 비교해서 순서가 맞다면 out 리스트에 추가하고 현재 순서를 하나 증가
if i == current_order:
out.append(i)
current_order+=1
else: # 현재 순서와 번호표가 일치 하지 않는다면
# 스택이 비어있지 않다면
if len(stack) > 0:
while stack: # 스택이 빌 때까지 스택을 순회
# 스택의 맨위 요소와 현재 순서가 같으면 스택 맨위 요소를 out 에 넣고 pop 진행
if stack[-1] == current_order:
out.append(stack[-1])
stack.pop()
current_order+=1
else: # 스택의 맨위 요소가 현재 순사랑 맞지 않다면 while 문 탈출
break
# 번호표에 있는 건 현재 순서랑 맞지 않았으므로 스택에 추가
stack.append(i)
else: # 스택이 비었거나, 스택의 맨위 요소가 현재 요소와 맞지 않다면 스택에 현재 번호표 추가
stack.append(i)
# 스택에 남아 있는 요소들 out 에 추가
while stack:
out.append(stack[-1])
stack.pop()
# 정렬된 out 리스트
sorted_out = list(out)
sorted_out.sort()
#out 리스트와 정렬된 out 리스트 비교 중간에 하나라도 다른 요소가 있다면 judge 변수에 False 값 대입
for i in range(len(out)):
if out[i] != sorted_out[i]:
judge = False
break
# judge 가 True 이면 Nice 출력 그게 아니라면 Sad 출력
if judge:
print("Nice")
else:
print("Sad")
문제 풀이 후기
이번 12789 번 문제는 스택과 관련된 문제였고, 이 문제를 풀게 된 계기는 저 스스로가 아직 자료구조에 대한 지식이 부족하다고 느끼고 있었고, 정답 비율도 낮아 생각보다 공부가 되겠다고 생각했기 때문입니다.
문제의 난이도는 정답 비율이 34%정도 되는 것을 보아 어려운 것으로 볼 수 있는데 이 문제가 어렵게 느껴지는 이유 중에 하나는 문제의 설명만 봤을 때는 현재 줄 서 있는 곳에서 간식 받는 곳으로 넘기는 과정에서 스택의 모든 구성 요소를 모두다 탐색을 해야 한다는 것에 대한 설명이 조금 부족해서 그런게 아닌가 합니다. 또한 여러 사람들이 공감하는 백준과 같은 저지 사이트에서는 테스트 케이스를 하나 밖에 주지 않아서 더 어려운 것 같습니다.
이것은 오로지 제 개인적인 생각인데 이 문제를 풀면서 저는 이 문제가 그렇게 좋은 문제라는 생각은 들지 않았습니다. 그 이유는 문제에서 해주는 설명만으로는 문제 풀이에 사용되는 모든 케이스를 알아내기에는 너무나도 부족하다고 느꼈기 때문입니다. 예전에 알고리즘 수업 때 알고리즘을 알려주시던 교수님께서는 과제로 이런 코딩 테스트와 관련된 알고리즘 문제를 내주셨는데 그 때는 하나의 케이스가 아닌 문제 설명으로는 부족하다고 볼 수 있는 여러 다른 반례들도 같이 주시곤 했었습니다. 하지만 이 문제는 케이스는 단 한 가지이고 그렇다면 문제 설명이라도 상세해야 하는데 너무 간단한 설명만 있어서 그렇게 좋은 문제는 아닌거 같다는 생각이 들었습니다.
Comments