[프로그래머스] 뒤에 있는 큰 수 찾기

문제 설명 :

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

프로그래머스

 

 

문제 요약 :

1. 배열의 각각의 수에 대해, 더 큰 수 이면서 가장 가까운 수 구하기

 

문제 풀이 시간 : 20분

문제 성공 여부 : 성공

 

 

접근 방법(실패) :

1. 배열의 뒤에서부터 접근
2. 뒤에서부터 가장 큰 수를 저장
3. 배열을 앞으로 탐색하며, 가장 큰 수와 비교
4. 가장 큰 수보다 클 경우, 더 큰 수는 뒤에 없기 때문에 -1
5. 가장 큰 수보다 작을 경우, 가장 큰 수 사이를 탐색하며 가장 가깝고 더 큰 수 찾기

제한 사항이 최대 1,000,000까지라 5번 상황에서 시간 초과가 발생했다.

 

900, 800, 300, 200,..................................................................., 1000000

 

이런 경우에서, 최대 100만 * 100만의 시간 복잡도가 발생하게 된다.

 

접근 방법(성공) :

1. 실패한 접근 방법에서 1,2,3,4번은 그대로 진행하였다.
2. 5번에서, 각 배열의 수를 탐색하는 것이 아닌, 각 수의 "뒤에 있는 큰 수" 값을 탐색하였다.

무슨 말이냐면, 

9 1 2 5 2 3 7 9 2

위와 같은 입력이 주어질 경우 3번째 인덱스의 5는 max 값인 9보다 작으면서 5보다 큰 수를 찾기 위해 2, 3, 7까지 탐색을 해야한다.

 

그럴 필요 없이 2의 "뒤에 있는 큰 수"인 3과 5를 비교하고, 3의 "뒤에 있는 큰 수"인 7을 5와 비교하면,

7까지 갈 필요없이 "뒤에 있는 큰 수"를 구할 수 있다.

 

 

전체 코드(성공) :

class Solution {
    public int[] solution(int[] numbers) {
        int max = -1;
        int[] ans = new int[numbers.length]; // 정답 배열
        
        for(int i = numbers.length-1; i>=0; i--){ // 뒤에서 부터 탐색
            int num = numbers[i]; // 현재 인덱스의 수
            
            if(num >= max){ // -1인 경우
                ans[i] = -1;
                max = num; // max값 최신화
                continue;
            }
            
            if(num < numbers[i+1]){ // 다음 인덱스의 수가 더 큰 수일 경우
                ans[i] = numbers[i+1];
                continue;
            }
            
            // 뒤에 있는 각 인덱스의 "더 큰 수"를 num과 비교
            for(int j = i+1; j<numbers.length; j++){
                if(num < ans[j]){ // num보다 클 경우, ans[j]는 가장 가깝고 큰 수이다.
                    ans[i] = ans[j];
                    break;
                }
            }
        }
        
        return ans;
    }
}

 

백준의 오큰수와 동일한 문제이고, 스택을 사용하면 더 간단하게 풀이할 수 있다.

 

지피티로 오큰수를 시각화해봤다.