[Python] 백준 12789 도키도키 간식드리미

 

문제 분석

• 맨 앞사람만 이동이 가능하다 : stack
• 번호표 순서대로 통과할 수 있는 라인 - 작은 순서대로 pop
• 현재 대기열의 사람들은 왼쪽 공간으로 올 수 있지만 반대 즉, 왼쪽 공간에서 다시 대기열에 서는 것은 불가능하다.
• 왼쪽 공간 또 다른 stack 필요
• 대기열의 모든 사람이 다 빠져 나가면 "nice", 못빠져나가면 "sad"

 

• 학생들은 1열로 서서 대기중이며, 앞에서부터 한 명씩 이동할 수 있다. 

 

코드 설계

• n : 승환 앞 학생 수 
• 띄어쓰기를 기준으로 origin_line (stack)에 append
• 왼쪽 공간 : left_line

현재 줄서있는 곳 비교

• 번호표는 1번부터 주어짐 : 1부터 비교(comp)
• 오름차순으로 비교하기 위해 1부터 1씩 커지는 comp를 큰 틀의 반복문으로 수행
• comp < stack[i] 이면 left_line에 append
• 아니면 (comp> stack[i] 일 수는 x) comp == stack[i] 이니까 pop() 하고 comp 가 하고 origin_line을 계산하는 반복문 break & 큰 틀의 반복문 continue

left_line 비교

• 현재 줄서 있는 곳에서 continue가 안되었다면 left_line도 비교
• comp > left_line[j] 이면 큰 틀의 반복문 나가기 & 큰 틀의 반복문 다음 반복으
• comp == left_line[j] 이면 pop하고 큰 틀 continue

1~N 했을 때 두 stack이 모두 비어있으면 "Nice" 하나라도 비어있지 않으면 "Sad"

 

정답 코드

1차 - 틀렸습니다

import sys
input = sys.stdin.readline

n = int(input())
origin_line = list(map(int, input().split()))
left_line = []
comp = 1

for _ in range(n):
    for i in origin_line :
        if comp < i :
            left_line.append(origin_line.pop()) # 빼서 넣어야함
        else :
            origin_line.pop() # 빼서 삭제
            comp += 1
            break

    if left_line : # 만약 왼쪽 공간에 사람이 있다면 거기도 비교
        for j in left_line :
            if comp < j :
                break
            else : # comp == j
                left_line.pop()
                break
    comp += 1

if not origin_line and not left_line:
    print("Nice")
else :
    print("Sad")

• 뭔가 별거 아닌거 같아 보이는데 오래걸렸다.. 조금만 더 하면 될거같은데 하면서 1시간 넘게 붙잡고 있었다..
• 잘못된 부분1 : pop을 하면 list의 마지막 요소를 꺼내는 것이기 때문에 pop(0)으로 첫번째 요소를 꺼내줘야 한다. 왜냐면 stack이니까
• left_line 비교할 때 나중에 추가된 학생이 먼저 검사를 받아야 한다. 
• 문제를 다시 보면 원래 줄을 다 검사하고 현재 comp보다 큰 수를 한번에 다 left_line에 넣고 left_line을 검사한다.
• 그리고 stack의 FILO인데 위 코드에서는 먼저 들어간 학생이 먼저 검사되는 오류가 있다.
• 제일 나중에 들어간 학생부터 검사해야한다.
• comp은 간식을 받는 순서에 따라 증가

 

2차 - 정답

import sys
input = sys.stdin.readline

n = int(input().strip())
origin_line = list(map(int, input().strip().split()))
left_line = []
comp = 1

while origin_line or left_line:
    if origin_line and origin_line[0] == comp:
        origin_line.pop(0)
        comp += 1
    elif left_line and left_line[-1] == comp:
        left_line.pop()
        comp += 1
    else:
        if origin_line:
            left_line.append(origin_line.pop(0))
        else:
            break

if not origin_line and not left_line:
    print("Nice")
else:
    print("Sad")

• origin_line과 left_line 둘 중 하나라도 존재하는 한 검사
• 만약 origin_line이 비어있지 않고, 맨 앞의 값이 comp와 같다면 맨 앞의 줄 학생을 빼고 (이때 맨 앞을 빼는 거니까 pop(0)) 다음 번호(comp) 비교

 

• 만약 origin_line 맨 앞에 서 있는 사람이 해당 순서가 아니면 left_line 확인
• left_line이 비어있지 않고 맨 나중에 들어간 사람의 번호[-1]가 comp와 같다면 맨 마지막 요소를 빼는거니까 pop() 하고, 다음 번호 비교

 

• 만약 원래 줄의 맨 앞사람과 left_line의 맨 앞사람이 아닐때
• 원래 줄에 사람이 있으면 맨 앞의 사람을 left_line 맨 마지막 요소에 추가

 

• 해당 순서로 바로 들어갈 사람이 없는데 원래 줄에 사람도 없다면
• break

 

1. 원래 줄 확인
2. 왼쪽 줄 확인
3. 둘 다 먹을 수 있는 번호가 없고 원래 줄에 사람이 있다면 왼쪽줄 끝으로 이동
4. 둘 다 먹을 수 있는 번호가 없는데 원래 줄에 사람이 없으면 break :  "현재 대기열의 사람들은 왼쪽 공간으로 올 수 있지만 반대 즉, 왼쪽 공간에서 다시 대기열에 서는 것은 불가능하다."
5. 두 stack에 값이 있는지 확인하고 "Nice' or "Sad" 출력