• 문제 link

0. 문제

---

예를 들어, test case 2 인 [9, 1, 5, 3, 6, 2] 배열을 numbers라고 할 때,
numbers와 길이가 같은 answer 배열을 만들어
numbers[i] 인 값의 뒤로 numbers[i] 보다 큰 값을 answer[i]에 담아
배열 answer을 return하는 solution을 작성하시오.

1. Solution

---

1.1 이론

1. 예외 없이 전체 탐색을 하는, for문 한 번에 모든 처리를 하기 위해,
   배열 answer는 index가 높은 요소부터 채워나간다.
2. 첫 for문에서는 answer에 i번째 요소에, 최종 반환 할 answer에 i번째 요소가 있는 numbers의 index를 저장한다.
3. numbers[i]와 numbers[i + 1]을 비교했을 때,
   numbers[i] < numbers[i + 1]이면, answer[i]에 'i + 1'을 저장하고,
   그렇지 않으면, answer배열을 이용하여 비교에 유효한 값들만 numbers[i]와 비교한다.
4. 마지막으로 for문을 하나 추가하여, answer[i]에 number[answer[i]] 를 저장한다.

1.2 코드

class Solution {
    int[] answer;
    int[] numbers;
    
    public int[] solution(int[] numbers) {
        this.numbers = numbers;
        int len = numbers.length;
        this.answer = new int[len];

        this.answer[len - 1] = -1;

        for (int i = len - 2; i >= 0; i--) {
            this.answer[i] = getBiggerNumIdx(this.numbers[i], i + 1);
        }

        for (int i = 0; i < len; i++) {
            if (answer[i] == -1) continue;
            this.answer[i] = this.numbers[this.answer[i]];
        }

        return this.answer;
    }
    
    private int getBiggerNumIdx(int num, int idx) {
        if (num < this.numbers[idx]) return idx;

        if (this.answer[idx] == -1) return -1;

        return getBiggerNumIdx(num, this.answer[idx]);
    }
}