뒤에 있는 큰 수 찾기

문제를 보고 이중 for문으로 풀수 있겠다 싶어서 금방 풀었다.

public static int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        //해당 수 뒤를 순회하면서 자기보다 큰수발견하면 바로 해당인덱스에 그 수 넣기
        //만약 발견하지 못하면 해당인덱스에 -1
        for(int i = 0; i < numbers.length; i++){
            for(int j = i+1; j < numbers.length; j++){
                if(numbers[i] < numbers[j]){
                    answer[i] = numbers[j];
                    break;
                }else{
                    answer[i] = -1;
                }
            }
        }
        answer[answer.length-1] = -1;
        return answer;
    }

그럼 그렇지...테스트케이스는 통과되지만, 시간복잡도가 높아서 통과되지 않았다. 그래서 스택으로 다시 풀었다.

 

public static int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>();
        for(int i = numbers.length-1; i >=0; i--){
            int num = numbers[i];
            answer[i] = -1;
            while(!stack.empty()){
                int top = stack.peek();
                if(top > num){
                    answer[i] = top;
                    break;
                }
                stack.pop();
            }
            stack.add(num);
        }
        return answer;
    }

 

어떻게 진행되는지 보자면

처음 상태:

stack: 빈 스택

answer: 배열 크기만큼의 배열, 초기값은 모두 -1 ({-1, -1, -1, -1, -1, -1})

i = 5 (numbers[5] = 2):

stack: [2] (스택에 2 추가)

answer: { -1, -1, -1, -1, -1, -1 }

i = 4 (numbers[4] = 6):

stack: [2, 6] (스택에 6 추가)

answer: { -1, -1, -1, -1, -1, -1 }

현재 6에 대해서는 뒷 큰수를 찾을 수 없으므로 그대로 둔다.

i = 3 (numbers[3] = 3):

stack: [2] (3보다 작은 6을 스택에서 제거)

answer: { -1, -1, -1, 6, -1, -1 }

현재 3에 대해서는 6이 3보다 크고 가장 가까우므로 answer[3]을 6으로 갱신.

i = 2 (numbers[2] = 5):

stack: [2, 5] (스택에 5 추가)

answer: { -1, -1, 6, 6, -1, -1 }

현재 5에 대해서는 6이 5보다 크고 가장 가까우므로 answer[2]을 6으로 갱신.

i = 1 (numbers[1] = 1):

stack: [2, 1] (5보다 작은 6을 스택에서 제거)

answer: { -1, 5, 6, 6, -1, -1 }

현재 1에 대해서는 5가 1보다 크고 가장 가까우므로 answer[1]을 5로 갱신.

i = 0 (numbers[0] = 9):

• stack: [9] (스택에 9 추가)
• answer: { -1, 5, 6, 6, -1, -1 }

현재 9에 대해서는 뒷 큰수를 찾을 수 없으므로 그대로 둔다.

이런식으로 스택을사용하니 numbers를 뒤에서부터 비교해가면서 answer에 넣으면 된다.

아직 자료구조에대해 더 적응할 필요가 있다...