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

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> s = new Stack<>();
      
        for(int i = numbers.length - 1; i >= 0; i--){
            while(!s.isEmpty()){
                if(s.peek() > numbers[i]){ // 뒤가 더 클 때
                    answer[i] = s.peek();
                    break;
                }
                else{
                    s.pop();
                }
            }
 
            if(s.isEmpty()){
                answer[i] = -1;
            }
            s.push(numbers[i]);
        }
        
        return answer;
    }
}

 

🧩 해결 아이디어

• 스택

- 스택에 들어가는 건 값이 아닌 인덱스

---

🔺 다른 풀이들

- 내가 참고한 풀이는 뒤쪽 원소부터 비교하면서 스택에 넣는 건데, 이 풀이는 앞부터 진행했다.

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

 

---

💬 느낀 점

처음에 브루트포스 2중 for문 써서 풀어봤는데 마지막 20번 TC부터 틀렸당...

아무래도 데이터 크기가 크다 보니..

틀린 코드

import java.util.*;
 
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        List<Integer> list = new ArrayList<>();
 
        for(int i = 0 ; i < numbers.length ; i++) {
            boolean exists = false;
            
            for(int j = i + 1 ; j < numbers.length ; j++) {
                if(numbers[j] > numbers[i]) {
                    list.add(numbers[j]);
                    exists = true;
                    break;
                }
            }
            
            if(!exists) list.add(-1);
        }
        
        for(int i = 0 ; i < list.size() ; i++) {
            answer[i] = list.get(i);
        }
        
        return answer;
    }
}

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

프로그래머스 Lv.2 뒤에 있는 큰 수 찾기-JAVA

 

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