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

 

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

프로그래머스

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        answer[answer.length-1] = -1;
        // stream 사용해서 List로 바꾸기
        List<Integer> numbersList = Arrays.stream(numbers).boxed().collect(Collectors.toList());
        
        // 반복문 사용해서 List로 바꾸기
//         List<Integer> numbersList2 = new ArrayList<>();        
//         for(int i=0 ;i<numbers.length; i++) {
//             numbersList.add(numbers[i]);
//         }
        
        int max = Collections.max(numbersList); // numbers 배열 속 최대값
        for(int i=0; i<numbers.length-1; i++) {
            if(numbers[i] == max) answer[i] = -1; // 자신이 max값이면 더이상 큰 수 없음
            else {
                for(int j=i+1; j<numbers.length; j++) {
                    if(numbers[j] > numbers[i]) {
                        answer[i] = numbers[j];
                        break;
                    } else if (j == numbers.length-1) answer[i] = -1;
                }
            }
        }
        
        return answer;
    }
}

 

그냥 단순하게 뒤로가면서 비교하면 될 거 같은데 왜 레벨2인거지? 했는데 역시 쉽게 풀리는 문제가 아니었던거다 for문 두개 써서 단순비교로 정답을 내면 시간초과가 난다

 

 

어떻게 풀지 생각해보다가 스택에 담아서 최대값을 확인하는걸 생각해봤다

처음했던 코드의 연장선인데 한 스택에는 배열을 정렬하고 옮겨서 최대값을 가장 위에 두고 max로 설정했다 그렇게 한 후 max랑 같은 값이면 -1로 바꾼 후 지나가고(지나갈때 최대값 스택에서는 가장 위에 있는 값을 pop하고 새로 위로 올라오는 값을 max로 바꿔줌  max랑 같은 값이 아니면 뒤로뒤로가면서 더 큰 수 찾고 break로 나오는걸 생각했다

근데 이거 역시 for문을 두번 써야했고 당연히 시간 초과가 났다

 

다른 방법으로도 해보다가 뒤에서부터 접근해야 시간 초과가 안난다는 것을 알아내고 다시 풀어보았다

 

최종코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Arrays.fill(answer,-1);
        
        Stack<Integer> stack = new Stack<>(); 
        stack.push(numbers[numbers.length-1]);
            
        for(int i=numbers.length-1; i>=0; i--) {
            while (!stack.isEmpty()) {
                if(stack.peek() > numbers[i]) {
                    answer[i] = stack.peek();
                    break;
                }
                else if (stack.peek() <= numbers[i]) {
                    stack.pop();
                    answer[i] = -1;
                }
            }
            stack.push(numbers[i]);
        }
        
        return answer;
    }
}

 

뒤에서부터 확인하면서 정답 배열을 뒤부터 채워준다

일단 모든 배열을 -1 로 채우고 시작하는데 이렇게 안하고 나중에 if문 조건 만족안하면 -1 넣어주는 식으로 해도됨

스택이 비어있으면(뒤에 더 큰수가 아예 없음) 그대로 스택에 추가해준 후 지나가고 스택에 뭔가 들어있으면 크기를 비교하면서 진행하면 된다

 

끝