12789번: 도키도키 간식드리미

문제 풀이 아이디어

원래 줄과 추가 대기열을 통해서 간식을 받을 순서에 따라 간식을 줘야하는 문제입니다. 추가 대기열을 사용해서 간식을 제대로 줄 수 없다면 실패입니다. 추가 대기열은 입구과 출구가 한쪽 밖에 없으므로 stack 자료구조를 사용하면 됩니다.

1. 줄 맨 앞에 서 있는 사람이 현재 순서라면 간식을 주고 번호표를 + 1합니다.
   1. 그리고 나서 만약에 대기열에 간식을 받을 사람이 있다면 줍니다.
2. 줄 맨 앞에 서있는 사람이 현재 순서가 아니라면 대기열(stack)에 push 합니다.

코드

// 입력 받기
let N = Int(readLine()!)!
var line = Array(readLine()!.split(separator: " ").map { Int(String($0))! }.reversed())
    //👉 줄을 뒤집는 이유는 Array를 앞에서 부터 pop하면 O(N)이기 때문에 (뒤에서부터는 O(1))

// 스택 (왼쪽에 1열로 설 수 있는 곳)
var stack = [Int]()

// 현재 간식을 받을 번호표
var now = 1

// 줄이 다 없어질 때까지 반복문 실행
while !line.isEmpty {
    let person = line.popLast()!
    
    // 현재 줄의 맨앞이 간식을 받을 순서라면
    if person == now {
        now += 1 //👉 간식을 주고 번호표 + 1
        
        // 그리고 나서 stack 안에 대기중인 사람 중에 순서가 된 사람이 있으면 주기
        while !stack.isEmpty && stack.last! == now {
            _ = stack.popLast()!
            now += 1
        }
        
    // 현재 줄의 맨앞 사람이 새치기한 사람이라면 대기열로 보내기
    } else {
        stack.append(person)
    }
}

// stack이 비어있다면 순서가 꼬이지 않아서 다 간식을 받은 경우
// stack이 비지 않은 경우 순서가 꼬여서 간식을 못 받은 경우
print(stack.isEmpty ? "Nice" : "Sad")