99클럽 3기 코테 스터디 1일차 TIL/[프로그래머스] 뒤에 있는 큰 수 찾기 자바 풀이

 

 

 

 

 

1. 오늘의 학습 문제 

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=java

프로그래머스

 

 

문제 설명
정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항
4 ≤ numbers의 길이 ≤ 1,000,000
1 ≤ numbers[i] ≤ 1,000,000
입출력 예
numbers result
[2, 3, 3, 5] [3, 5, 5, -1]
[9, 1, 5, 3, 6, 2] [-1, 5, 6, 6, -1, -1]
입출력 예 설명
입출력 예 #1
2의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.

입출력 예 #2
9는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

 

 

 

 

 

 

 

---

처음의 접근방법은 이중for문 이었으나,

numbers의 길이가 100만이므로, 100만*100만=1조로 시간복잡도 O(n^2)에서 최대연산수 1억을 초과한다. 

따라서 스택으로 풀이함.

1. 스택에 인덱스i 를 담고, 

2. 다음 numbers[i+1]이 스택.peek()보다 크다면 스택.pop()의 인덱스에 해당하는 answer원소를 뒷큰수로 넣어주기

 

 

 

 

코드

---

import java.util.*;

//이중 for문 시간초과->스택으로

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length]; //배열의 length는 속성이므로 괄호x
        
        Stack<Integer> stack = new Stack<>();//인덱스를 순서대로 담을 스택
        
        int idx=0; //answer용 인덱스
       
        for(int i=0;i<numbers.length-1;i++){
            stack.push(i);//인덱스를 넣어줌
            while(!stack.isEmpty() && numbers[stack.peek()] < numbers[i+1]){ 
            // 스택이 비어있지 않고, stack.peek() < 뒷큰수일때
                answer[stack.pop()]=numbers[i+1]; 
                //answer의 해당 pop의 인덱스에 뒷 큰수를 넣어줌
            }
        }
       
        while(!stack.isEmpty()){ //스택을 비우고 -1넣어줌.
            answer[stack.pop()]=-1;
        }
        answer[numbers.length-1]=-1;
        
        return answer;
        
    }
}

 

 

2. 오늘의 회고

---

 

• 주어진 조건에 대한 시간복잡도를 잘 생각해보자
• 하나의 뒷 큰수가 여러 원소에 대해 답이 될 수 있는데, 이때 stack을 통해 일괄로 처리한 방법을 잘 기억해두자
• 3기가 시작되었다. 파이팅! 

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL