[Kotlin] 백준 1874번 : 스택 수열 <Silver 2>

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

1874번: 스택 수열

Code

---

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = readLine().toInt()
    val result = mutableListOf<String>()
    val stack = Stack<Int>()

    var now = 1
    for(i in 0 until n) {
        val cmd = readLine().toInt()

        while(now <= cmd){
            stack.push(now)
            result += "+"
            now++
        }

        if (cmd == stack.last()) {
            stack.pop()
            result += "-"
        } else {
            result.clear()
            result += "NO"
            break
        }
    }

    result.forEach {
        bw.write(it + "\n")
    }
    bw.flush()
    bw.close()
}

---

처음에 정말 복잡하게 접근을 했었다. 아니, 맞는 방향이었지만  더 어렵게 생각했다.

 

되는 규칙을 찾아보고, 안되는 규칙을 찾아보자

연속된 숫자 사이에 뭔가 다른 값이 들어가는게 될까?
ex)
3
5
4
-> 된다. 3넣고 pop, 4넣고, 5넣고 pop pop


낮은숫자가 큰 숫자보다 위
넣자마자 팝 하는 방식으로 가능하다
1 넣고 pop, 2 넣고 pop

큰 숫자가 작은 숫자보다 위
두번 넣고 pop pop 하면 된다.



어떤 숫자를 보고,
그 밑에를 봤을 때 그 숫자보다 낮은 숫자가 점점 올라가는 모양이 가능할까?
6
2
4
...

불가능하다.

큰 값을 보고, 그 다음 값이 연결인지 확인. 제일 큰 값 만큼 +
그리고 그 값을 저장한 후 연결된 값 내려간 만큼 빼줌. 그리고 1 더 뺀 다음 - 출력
그 후 다음 값이 자신보다 커졌다면  지금까지 최댓값과 비교해서 더 큰만큼 +


스택에는 그럼 입력받은 순서 반대로 존재한다는 거잖아

1 2 5 7 8 6 3 4

MAX 나오면 지금까지 - 수를 MAX에 빼고 출력

+ + + + - - + + - + + - - - - -

이게 내 사고과정이다.

 

큰 방향은 맞았지만 세부적인 부분을 보자면 완전히 틀렸다.

그래서 list로 구현하다가 때려치고 Stack을 사용했다.

 

맨 앞에 4가 온다면, 1,2,3,4를 push한 후 pop 했다는 뜻이다.

그렇기 때문에 시작할 때의 값에서 4까지 전부 다 push해줘야 한다.

 

그 후 stack의 맨 뒤가 입력받은 값과 같다면 pop 해준다. 

이때 같지 않다면 불가능한 예시가 들어왔다는 의미이기때문에 No를 출력할수 있게 한다.