[백준] 1874 (스택 수열)

#1 알고리즘

1. 어떤 스택에는 '이상한' 규칙이 있다. 바로 해당 스택에 push하는 원소의 값이 순서대로 1, 2, 3, ... , n여야 한다는 규칙이다. 즉, 맨 처음 스택에 push하는 값은 반드시 1이어야 하며, 1 다음에는 2, 2 다음에는 3, ... , 62 다음에는 63을 push해야 한다.


2. 반면, pop에 대한 규칙은 없다. 스택이 비어있는 상태에서 pop을 하는게 아닌 이상, 아무렇게나 해도 된다.


3. (1)의 규칙은 (스택에 들어 있는 원소들 중 가장 나중에 push된 값 + 1)을 push하는 규칙이 아님에 유의한다. 예를 들어 1, 2, 3을 차례대로 push하고 pop을 2번 한 상황이 있다. 여기서 추가적으로 push를 하려는 경우, 그 값은 2가 아니라 4다.

4. 테스트케이스(입력)로는 첫 줄에 n의 값이 주어지고 그 다음 줄부터는 줄마다 자연수가 하나씩 주어진다. 이 숫자들은 어떤 정렬되지 않은 배열의 원소를 0번 인덱스부터 시작해 차례대로 나열한 것이다. 이 배열의 원소들은 총 n개다. 원소 값의 범위는 1 ~ n이고, 원소끼리 서로 중복되는 값을 가지지 않는다.

5. '이상한' 규칙을 가진 스택에서 push와 pop을 적절히 배합하면, (pop으로 뱉어내는 값의 나열)과 (테스트케이스 원소의 나열)이 똑같게끔 만들 수 있다. 다만, (1)의 규칙 때문에 불가능할 때도 있다.

6. (5)가 가능하다면 '이상한' 스택에 push을 할 때마다 +, pop 연산을 할 때마다 -를 줄마다 하나씩 출력하라. 불가능하다면, +와 - 대신 NO 한 줄만 출력한다.

이 문제에서 가장 어려운 부분은, 바로 문제 자체의 가독성이 좋지 않다는 점이다. 그래서 내가 다시 적었다.
 

#2 코드 - 코틀린

import java.lang.StringBuilder
import java.util.Stack

fun main() {
    val stack: Stack<Int> = Stack()
    val n = readln().toInt()
    var nextPushValue = 1

    var submit = StringBuilder()
    var nextPopValue = -1
    for(i: Int in 0..<n) {
        nextPopValue = readln().toInt()

        while(nextPushValue <= nextPopValue) {
            stack.push(nextPushValue++)
            submit.append("+\n")
        }

        if(stack.peek() != nextPopValue) {
            submit.clear()
            submit.append("NO\n")
            break
        }

        stack.pop()
        submit.append("-\n")
    }

    print(submit)
}

 

#3 실패한 코드 - 메모리 초과 - 코틀린

import java.util.Stack

fun main() {
    val stack: Stack<Int> = Stack()
    val n = readln().toInt()
    var nextPushValue = 1

    var submit = ""
    var nextPopValue = -1
    for(i: Int in 0..<n) {
        nextPopValue = readln().toInt()

        while(nextPushValue <= nextPopValue) { // inner loop
            stack.push(nextPushValue++)
            submit += "+\n"
        }

        if(stack.peek() != nextPopValue) {
            submit = "NO\n"
            break
        }

        stack.pop()
        submit += "-\n"
    }

    print(submit)
}

#2와의 유일한 차이는, 변수 submit에 StringBuilder대신 String을 사용한 점이다. n은 문제의 조건에 의해 최대 100000(십만)까지기 때문에, String 객체가 담을 수 있는 데이터의 상한을 넘어 메모리 초과가 일어났다.