항해 99 15일차 TIL ( 뒤에 있는 큰 수 찾기 / 프로그래머스)

문제

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

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

o(n2)으로 탐색하면 쉬운 문제이지만
numbers의 길이가 1,000,000이다. 시간초과에서 걸릴 것 같아 좋은 방법을 생각해야 한다.
일단 o(n2)로 코드 구현해보자

1 번째 시도

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int n = numbers.length;

        int[] arr = new int[n];

        for(int i = 0; i < n; i++) {
            arr[i] = -1;
        }
        for(int i =0; i < n; i++) {
            for(int j =i+1; j < n ; j++) {
                if(numbers[i] < numbers[j]) {
                    arr[i] = numbers[j];
                    break;
                }                    
            }
        }

        return arr;
    }
}

역시나 시간 초과가 떴다.

다른 사람 풀이를 찾아보니 스택을 사용했다.

2 번째 시도

즉, 스택에 들어가 있는 것들은 아직 자기보다 큰 숫자를 찾지 못한 숫자들이다. 한 배열을 한 번만 탐색하면 되니 시간 복잡도는 O(n)이다.

import java.util.*;


class Solution {
    public int[] solution(int[] numbers) {
        Stack<Integer> stack = new Stack<>();
        int[] answer = new int[numbers.length];

        Arrays.fill(answer, -1); // 초기값을 -1로 세팅

        for (int i = 0; i < numbers.length; i++) {
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                answer[stack.pop()] = numbers[i];
            }
            stack.push(i);
        }
        return answer;
    }
}