<프로그래머스> 뒤에 있는 큰 수 찾기(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%EB%92%A4%EC%97%90%20%EC%9E%88%EB%8A%94%20%ED%81%B0%20%EC%88%98%20%EC%B0%BE%EA%B8%B0

[프로그래머스]

https://school.programmers.co.kr/learn/courses/30/lessons/154539

 

이제는 진짜 하루 하루 문제 푸는 시간이 길어지고 있다.

그만큼 내가 느끼는 난이도가 올라가고 그걸 쉽게 내릴 수 있는 방법들이 존재한다는 거겠지...

오늘 이 문제도 힌트 하나를 잡으니까 앞에 들인 시간이 무색하게 쉽게 해결할 수 있었다.

 

처음에 이 문제를 보고 가장 쉽게 떠올릴 수 있는 것은 '반복문을 두 번 돌린다.' 일 것이다.

자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 찾는 거니까 쭉 가다가 가장 먼저 큰 값 나오면 저장하면 된다.

하지만 이 경우는 예상이 되다시피 제한사항에서 배열의 길이가 1000000이므로 O(n^2)인 이 방법으로는 무조건 시간초과가 날 것이다.

 

그래서 이건 피해서 코드를 짜려고 노력했다.

이번에는 코드를 4번 갈아엎었다.(그 중 3개는 깃허브에 남겨놓았다.)

 

첫번째 코드는... 생각이 안 나네?

생각났다.!!

얘는 numbers 하나로 문제를 해결하려고 하다가 예제도 통과 못해서 바로 지웠다!

 

두번째 코드는 예제만 통과하고 제출했을 때 3개를 제외하고 다 틀렸었다.

가장 큰 이유는 자기 자신 다음에 존재하는 값만으로 뒷 큰수를 정했기 때문이었다고 생각한다.(시간초과는 제외...ㅎ)

 

이 부분을 보완해서 세번째 코드가 나왔고 제출했을 때 절반이 맞았고 절반은 모조리 시간초과였다...

DP같은 느낌이 나지만 어쨌든 O(n^2)이었기 때문에 그랬다고 생각한다.

 

이제 고민하는 시간...

'뭐를 써서 해결하는 걸까?'  그렇게 고민하면서 질문들 제목을 보는데(들어가지는 않고!!) 힌트가 될만한 게 있더라

바로 스택이었다.

처음에는 이게 스택이랑 무슨 상관이 있을까 싶었는데 막상 손으로 순서를 그려보니 각이 나오더라

그렇게 이 문제는 해결되었다.

스택에 값을 넣는데 넣을 값이 스택의 top에 있는 값보다 크면 top의 값을 빼고 빼고 그 다음에 넣고, 마지막에는 스택에 남아있는 값들을 싹 빼서 -1 주는 진행방식이다.

 

해당 방법으로 작성한 코드는 다음과 같다.

// 스택을 사용하기 위해 추가
import java.util.*

class Solution {
    fun solution(numbers: IntArray): IntArray {
        var answer: IntArray = IntArray(numbers.size)
        var stack: Stack<Pair<Int, Int>> = Stack()
        
        // numbers 순서대로 순회
        for ((index, item) in numbers.withIndex()) {
            // 스택이 비어있을 때는 바로 넣기(처음 한 번을 위한 거라 안 넣어도 상관없었을 듯)
            if (stack.isEmpty()) {
                stack.push(Pair(index, item))
                continue
            }
            // 스택이 비어있지 않고 넣을 값이 top의 값보다 클 때 반복되는 부분
            while (stack.isNotEmpty() && item > stack.peek().second) {
                val popValue = stack.pop()
                // top의 값의 뒷 큰수는 넣을 값이 된다.
                answer[popValue.first] = item
            }
            stack.push(Pair(index, item))
        }
        // 스택에 남은 값들은 뒷 큰수가 없기에 -1로 설정
        while (stack.isNotEmpty()) {
            val popValue = stack.pop()
            answer[popValue.first] = -1
        }
        
        return answer
    }
}

 

문제를 다 풀고 다른 사람들의 풀이를 보는데 많은 비중의 사람들이 뒤에서부터 순회하는 방식으로 문제를 해결했더라.

그래서 그렇게 뒤에서부터 순회하는 방식을 보는데 오히려 '이걸 어떻게 생각해냈지?'라는 생각이 들었다.

앞에서 가는 것보다 더 복잡하게 느껴졌다.

 

그리고 내가 두번째, 세번째 코드로 작성했지만 통과하지 못한 코드의 느낌으로 해결한 코드도 있더라

역시 내가 해결하지 못했을 뿐 방법은 분명히 있었던 거다.