문제 바로가기

문제

풀이

정석 풀이

예전에 풀었다가 시간 초과로 실패된 채 남아있던 코드이다.

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length]; 
        
        for(int i=0;i<numbers.length;i++) {
            int cur = -1;
            for(int j=i+1;j<numbers.length;j++) {
                if(numbers[j]>numbers[i]) {
                    cur = numbers[j];
                    break;
                }
            }
            answer[i] = cur;
        }
        
        return answer;
    }
}

각 인덱스 i마다 해당 인덱스 뒤에 위치하는 원소를 모두 방문하여 더 큰 숫자가 나오면 그 값을 answer[i]에 저장한다.

시간복잡도 O(n^2)로, 시간 초과에 걸린다.

DP 활용 풀이

생각한 접근 방식은 아래와 같다.

1. 배열을 역방향으로 순회한다. (i)

2. 방문한 인덱스 i에 대해 뒷 인덱스 j(i< j <배열 길이)를 순회한다.
   이 때 numbers[j] → answer[j] 순으로 비교하여 큰 숫자가 있다면 answer[i]에 저장한다.

   answer[j]는 numbers[j]의 뒷 큰수이므로,
   answer[j] > numbers[i]일 때, numbers[i]보다 크면서 가장 가까이 있는 수인 것이 보장된다.

3. 만일 answer[j] 가 -1이라면 number[i]보다 큰 수가 뒤에는 더 없다는 뜻이므로, answer[i]에 -1을 저장한다.
   → -1이 아니라면, 뒤에 numbers[i]보다 큰 수가 있을 수 있다는 의미이므로 계속해서 순회한다.

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length]; 
        answer[numbers.length-1] = -1;
        
        for(int i=numbers.length-2; i>=0; i--) {
            for(int j=i+1; j<numbers.length; j++) {
                if(numbers[j] > numbers[i]) {
                    answer[i] = numbers[j];
                    break;
                } else if(answer[j] > numbers[i]) {
                    answer[i] = answer[j];
                    break;
                } else if(answer[j] == -1) {
                    answer[i] = -1;
                    break;
                }
            }
        }
        
        return answer;
    }
}

---

다른 사람들 코드를 보니 Stack을 이용해서 풀이한 사람들이 많은 것 같다.
Stack을 사용해야겠다는 생각은 전혀 못 했는데, 이용해서 다시 한 번 풀어봐야겠다.