[BOJ] 1874 - 스택 수열

2022. 4. 18. 09:21

문제

풀이 코드

// Stack 구조체 선언
public struct Stack<T> {
    private var elements = [T]()
    public init() {}
    
    public mutating func pop() -> T? {
        return self.elements.popLast()
    }
    
    public mutating func push(_ elements: T) {
        self.elements.append(elements)
    }
    
    public func top() -> T? {
        return self.elements.last
    }
    
    public var empty: Bool {
        return self.elements.isEmpty
    }
}

// 변수 선언
let n = Int(readLine()!)!
var sequence = [Int]()
var result = [String]()
var sequenceStack = Stack<Int>()
var pushValue = 1

// 입력값 저장 배열
for _ in 0..<n { sequence.append(Int(readLine()!)!) }

// 1부터 현재의 value 까지 채워넣고, 스택의 마지막 값과 현재 value 의 값을 비교하여 같으면 pop, 다르면 해당 수열을 만들 수 없으므로 NO 출력
for value in sequence {
    while pushValue <= value {
        sequenceStack.push(pushValue)
        result.append("+")
        pushValue += 1
    }
    if sequenceStack.top()! == value {
        sequenceStack.pop()
        result.append("-")
    } else { print("NO"); break }
}

// 스택이 비어있는 상태면 정상적인 계산 완료
if sequenceStack.empty {
    print(result.joined(separator: "\n"))
}

풀이 과정

조금 어려웠다 일단 문제 이해가 어려웠고, 그다음 구현이 어려웠다.. 그렇게 몇시간을 고민하다가 다른 분들의 코드를 보고 힌트를 얻어 구현했다..

일단 문제를 해설하자면 입력으로 주어진 순서의 값들이, 스택에 1부터 오름차순으로 push 해서 pop 할때와의 순서와 같아야 하고, 그렇게 할수 없는 경우 NO를 출력하면 된다

나도 이게 무슨소리인지 몰랐지만

정리하면 예시로 나온 4 3 6 8 7 5 2 1 로 보자

처음에 4가 pop으로 나와야하니 스택에

1 2 3 4 가 들어가고 4 가 pop 된다 그러면

+ + + + - 까지 되고 그다음 숫자인 3이 pop되야하니 그냥 pop하면 된다 그러면

+ + + + - - 까지가 4 3 이 출렷 된다! 그다음 숫자는 6이기 때문에 우선 6까지 채워줘야 하므로

+ + + + - - + + 이렇게 하면 스택에 1 2 5 6 이 있고, 여기서 pop을 하면 1 2 5 가 스택에 남는다

+ + + + - - + + - 이렇게 반복하여서 Push 할땐 + 를, pop할땐 - 를 해주면 된다,

그러다가 중간에 pop을 해도 해당 순서로 정렬할수 없는경우 가차없이 NO를 출력하면 된다!

여기에 해당하는 조건은 stack.top() 이 현재 출력해야할 수보다 크면 순서대로 정렬할 수 없기 때문에 NO를 출력하면 된다!!

문제를 이해하고나면 그리 많이 어려운 문제는 아니였는데,,

이해하는데도 오래걸리고 1부터 채워서 어떻게 출력하지? 라는 고민때문에 다른분의 코드를 보고 힌트를 얻은게 참 아쉽다

Chikong