1874번: 스택 수열

문제 풀이 아이디어

수열에 숫자를 push, pop을 반복하면서 푸는 문제입니다. push는 무조건 1 ~ n의 오름차순으로 해야하고 pop의 주어진 순서대로 해야합니다.

이 경우 숫자를 오름차순으로 push하므로 stack 안에는 오름차순으로 정렬이 되어있습니다.

1. 따라서 만약에 pop해야할 숫자가 stack의 마지막 (pop 대상인) 숫자보다 크다면 더 push를 하고
2. pop할 숫자가 마지막 숫자와 같다면 pop을 하면 됩니다.
3. ⭐️ 하지만 문제는 pop해야할 숫자가 stack의 마지막 숫자보다 작은 경우입니다.

stack에는 1 ~ n의 오름차순으로 push 하므로 pop할 숫자가 stack의 마지막 숫자보다 작다면 그 숫자는 이미 stack에 들어있게 됩니다. 그 숫자는 stack의 마지막 숫자를 pop한 이후에 pop을 해야하므로 당장 pop할 수 없고 결과적으로 스택 수열을 만들 수 없게 되는 것이죠.

구현 자체는 어렵지 않습니다만 🚫 “NO”를 출력하는 조건을 찾는 것이 약간 까다로운 문제였습니다.

처음 풀이 😅

// 스택의 가장 마지막 보다는 새로 pop해야 할 수가 작아야 한다.

var stack = [Int]()
let N = Int(readLine()!)!

// pop 해아할 수들 (이것도 stack으로 만들기 위해서 reverse 함)
var toPops = [Int]()
for _ in 0..<N {
    toPops.append(Int(readLine()!)!)
}
toPops.reverse()

var toPush = 1 // 지금 push할 수
var toPop = toPops.popLast()! // 지금 pop해야하는 수
var result = [String]() // 결과 저장

// stack에 푸시할 때
func push() {
    stack.append(toPush) //👉 숫자 push하고
    toPush += 1 //👉 다음 push할 숫자 1 늘린다.
    result.append("+") //👉 결과에 push했음을 저장
}

// stack에서 pop할 때
func pop() {
    stack.removeLast() //👉 pop하고
    toPop = toPops.popLast() ?? 0 //👉 다음에 pop할 숫자 (끝났으면 0)
    result.append("-") //👉 결과에 pop했음을 저장
}

while toPop > 0 { //👉 pop할 숫자가 없을 때까지
    if stack.isEmpty { //👉 stack이 비었으면 일단 push한다.
        push()
    }
    
    if stack.last! > toPop { //👉 stack의 마지막 수가 pop할 숫자보다 크면 = 수열 만들 수 없음
        break
    } else if stack.last! < toPop { //👉 아직 작다면 더 push
        push()
    } else { //👉 같다면 pop
        pop()
    }
}

if toPops.isEmpty { //👉 전부 pop 했다면 결과 출력
    result.forEach { char in
        print(char)
    }
} else { //👉 중간에 만들 수 없어서 break 되었다면 "NO" 출력
    print("NO")
}

코드 다이어트 🏃‍♂️

위의 코드는 정답이기는 하지만 없어도 될 변수가 너무 많습니다. 조금 간략하게 코드를 만들어봅시다.

import Foundation

let N = Int(readLine()!)!

var toPush = 1
var stack = [Int]()
var result = [String]()

for _ in 0..<N {
    let toPop = Int(readLine()!)! //👉 다음에 pop할 숫자를 여기서 입력을 받는다.
    
		//✅ stack의 last와 비교하는 것을 toPush와 비교하는 것으로 대체
    // 아직 toPop보다 toPush가 작다면 계속 push
    while toPush <= toPop {
        stack.append(toPush)
        result.append("+")
        toPush += 1
    }
    
    // 같다면 pop
    if stack.last == toPop {
        stack.removeLast()
        result.append("-")
    } else { //👉 toPop이 더 작다면 "NO"를 출력하고 종료
        print("NO")
        exit(0)
    }
}

print(result.joined(separator: "\n"))