[Swift 알고리즘] 백준 BOJ - 1874 스택 수열

안녕하세요. 개발 중인 정주입니다.

 

오늘은 백준 BOJ - 1874 스택 수열 문제를 풀었습니다.

 

---

목차

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

---

풀이

스택 수열 문제는 이름 그대로 스택을 이용한 문제입니다.

 

Input

백준 특성상 input도 직접 받아야 하기 때문에 초반 코드는 input을 받는 코드입니다.

input을 받아 append 해주고 reverse()를 해줍니다.

왜냐하면 removeFirst()는 정렬에 많은 코스트가 들기 때문에 비교적 코스트가 적은 removeLast()로 삭제를 하기 위해서입니다.

 

스택 수열 판단

input이 완료되면 스택 수열인지 판단해야 합니다.

1부터 n까지의 값 i가 스택의 top과 똑같지 않거나 스택이 비어있다면 stack에 append를 해주고 똑같으면 pop을 해줍니다.

이때 append를 한 후에도 추가적으로 stack의 top과 i가 동일한지 반복문을 통해 확인해야 합니다.

pop이 됨으로써 연쇄적으로 pop이 되는 경우도 있기 때문입니다.

 

결과 출력하기

스택 수열이 아니라면 NO를 출력해야 하기 때문에 +, -는 배열에 넣어 마지막에 한 번에 출력해주었습니다.

 

---

전체 코드

import Foundation

let count = Int(readLine()!)!
var inputs: [Int] = []
var stack: [Int] = []
var result: [String] = []

for _ in 0..<count {
    let num = Int(readLine()!)!
    inputs.append(num)
}
inputs.reverse()

for i in 1...count {
    if let top = stack.last, top == inputs.last! {
        result.append("-")
        stack.removeLast()
    } else {
        result.append("+")
        stack.append(i)
        
        while !stack.isEmpty {
            if let top = stack.last, top == inputs.last! {
                result.append("-")
                stack.removeLast()
                inputs.removeLast()
            } else {
                break
            }
        }
    }
}

if inputs.isEmpty {
    for s in result {
        print("\(s)")
    }
} else {
    print("NO")
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.