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

 

 

스택을 활용하는 문제로, 첨부된 그림에 나타난 것처럼 정식 줄이 있고 그 옆에 임시 저장소 같은 골목길 이렇게 두 공간이 존재하는 상태이기 때문에 스택을 두 개 활용해주면 된다. 

 

접근 방법: 큐와 스택을 활용

- 줄 서있는 사람들을 기존의 arr 스택의 앞에서부터 차례대로 꺼내면서, 카운터에 바로 갈 수 없는 사람은 임시 스택 temp에 저장해두는 방식 

- 현재 사람들이 가져야 할 번호표가 1번부터 시작해 순차적으로 카운터에 도달해야 한다.

- 만약 arr 줄에서 나오는 번호와 번호표가 맞지 않으면 임시 스택 temp에 해당 사람을 보관했다가 나중에 꺼내기!

- 이때 temp 스택에서 번호를 확인하는 조건은 맨 위의 번호가 현재 필요한 번호와 일치한다면, 해당 번호의 사람을 꺼내서 카운터로 전달하고 필요한 번호 변수를 다시 하나 올리는 것이다. 

 

위 과정을 반복하면 됨!

 

N = input()
arr = list(map(int, input().split()))
temp = [] # 임시 대기 장소 
# temp의 맨 위에 있는 번호가 현재 필요한 번호 cnt와 일치할 경우, 해당 번호표를 꺼내서 카운터로 전달

def line_up(arr, temp):
    cnt = 1
    while(arr):
        if(arr[0] == cnt):
            arr.pop(0)
            cnt += 1
        elif temp and temp[-1] == cnt:
            temp.pop()
            cnt += 1
        else: # 둘 다 아닌 경우는 temp에 쌓아야 하는 경우임
            temp.append(arr.pop(0))
    # arr이 다 비었어도 temp 스택에 남아있는 애들 처리해야 함 (가능한지 판별)
    while temp:
        if(temp[-1] == cnt):
            temp.pop()
            cnt += 1
        else:
            return False
    return True

print("Nice" if line_up(arr, temp) else "Sad")

 

- 번호표 순서를 나타내는 cnt 변수를 1로 초기화하여 1부터 N 까지 순서대로 카운터로 가야할 번호를 추적한다.

 

- arr 원본 줄 리스트를 큐처럼 활용해서 줄 서 있는 번호들을 순차적으로 확인하고, temp 임시 리스트를 스택처럼 활용하여 대기하는 장소를 구현하였다.

=> 따라서 arr에서 사람을 순차적으로 빼낼 때는 pop(0)을 사용하고, temp에서 꺼낼 때는 pop() 을 사용한 것!

- 위 pop 을 각각 수행할 때마다 사람이 1부터 순서대로 카운터로 보내지는 것이기 때문에 반복문에서 다음으로 필요한 번호표 번호인 cnt 변수를 1씩 증가시킨다.

 

- 첫 번째 while문이 끝나도 (원본 줄인 arr이 다 비었어도) temp 임시 스택에는 사람들이 남아있을 수 있기 때문에, 여기에 있는 사람들이 pop()을 수행했을 때 현재 필요한 번호인 cnt와 같은지를 판별하여 나머지 pop()을 진행해준다.

 

이 때 이 과정이 제대로 수행되지 않는다면 카운터로 제대로 보낼 수 없는 경우이기 때문에 False를 반환하여 결론적으로 Sad를 출력하게 되고, 제대로 수행되어 두 번째 while문도 종료된다면 True를 반환하여 Nice를 출력하고 종료시킨다.