[프로그래머스 / 연습문제 / 자바(JAVA)] 뒤에 있는 큰 수 찾기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

[ 요약 ]

시작 시간 : PM 2:20

종료 시간 : PM 2:53

소요 시간(분) : 33분

 

도전 횟수 (제출 횟수) : 4

로직 및 풀이 참고 여부 : O

 

[ 풀어보기 ]

 

 

정답 풀이

📌 로직

프로그래머스 > 코딩테스트 연습 > 스택 / 큐 > 주식가격과 비슷한 문제라고 한다.

• https://eunzzzzz1.tistory.com/50
• https://school.programmers.co.kr/learn/courses/30/lessons/42584

1. numbers를 순회하면서 numbers의 인덱스를 stack에 차례로 넣는다.
2. stack의 가장 상단에 있는 요소 n을 인덱스로 가지는 numbers가 현재 numbers[i] 보다 작으면
   1. numbers[i]가 numbers[n]의 뒷 큰수라는 뜻.
   2. 따라서 s.pop()으로 요소를 꺼내고, 이를 answer의 인덱스로 활용, numbers[i]를 값으로 담는다.
3. stack의 가장 상단에 있는 요소 n을 인덱스로 가지는 numbers가 현재 numbers[i] 보다 크면...
   1. numbers[i]는 numbers[n]의 뒷 큰수가 될 수 없다.
   2. 그러므로 n은 그대로 stack에 담아두고, 다음 numbers[i]로 넘어가 뒷 큰수가 나올 때까지 찾아야한다.

 

📌 코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        Stack<Integer> s = new Stack<>();
        
        for(int i=0; i<numbers.length; i++) {
            while(!s.isEmpty() && numbers[s.peek()] < numbers[i]) {
                answer[s.pop()] = numbers[i];
            }
            s.push(i);
        }
        
        while(!s.isEmpty()) {
            answer[s.pop()] = -1;
        }
        
        return answer;
    }
}

 

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (0.14ms, 67.4MB)
테스트 2 〉	통과 (0.14ms, 70.8MB)
테스트 3 〉	통과 (0.13ms, 76.8MB)
테스트 4 〉	통과 (0.29ms, 80MB)
테스트 5 〉	통과 (1.46ms, 73.9MB)
테스트 6 〉	통과 (4.32ms, 77.4MB)
테스트 7 〉	통과 (4.67ms, 85.3MB)
테스트 8 〉	통과 (19.22ms, 95.4MB)
테스트 9 〉	통과 (15.68ms, 89.3MB)
테스트 10 〉	통과 (20.89ms, 117MB)
테스트 11 〉	통과 (32.24ms, 97.2MB)
테스트 12 〉	통과 (37.51ms, 126MB)
테스트 13 〉	통과 (31.05ms, 129MB)
테스트 14 〉	통과 (47.98ms, 163MB)
테스트 15 〉	통과 (140.30ms, 191MB)
테스트 16 〉	통과 (64.70ms, 215MB)
테스트 17 〉	통과 (61.01ms, 201MB)
테스트 18 〉	통과 (71.75ms, 217MB)
테스트 19 〉	통과 (89.09ms, 189MB)
테스트 20 〉	통과 (82.95ms, 224MB)
테스트 21 〉	통과 (62.51ms, 196MB)
테스트 22 〉	통과 (49.13ms, 174MB)
테스트 23 〉	통과 (62.92ms, 178MB)

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

 

---

[ 오답 노트 ]

오답 1

📌 오답 코드

단순 이중 for문을 이용해서 풀었다.

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        for(int i=0; i<numbers.length; i++) {
            answer[i] = -1;
            
            for(int j=i+1; j<numbers.length; j++) {
                
                if(numbers[i] < numbers[j]) {
                    answer[i] = numbers[j];
                    break;
                }
            }
        }
        
        return answer;
    }
}

 

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (0.01ms, 72MB)
	...
테스트 19 〉	통과 (39.89ms, 178MB)
테스트 20 〉	실패 (시간 초과)
테스트 21 〉	실패 (시간 초과)
테스트 22 〉	실패 (시간 초과)
테스트 23 〉	실패 (시간 초과)

채점 결과
정확성: 82.6
합계: 82.6 / 100.0

 

📌 오답 이유

1. 정확성 테스트 오답 이유 : 시간 초과
   
   • 최악의 경우 (number의 끝까지 가도 numbers[j] 보다 큰 수를 찾을 수 없는 경우)
     내부 for문은 매번 numbers.length - j번을 순회할 것이다.

📌 개선하기

1. 정확성 테스트 오답 개선
   
   • numbers[i] 보다 큰 numbers[j] 를 찾았을 때, j를 따로 저장해두는 변수 idx를 만들고
   • i for문의 다음 회차에서 이를 활용하면 순회횟수를 조금 줄일 수 있지 않을까?
     • idx > i+1 이면 j for문은 idx부터 시작해서 순회하도록
     • idx <= i+1 이면 j for문은 i+1부터 시작해서 순회하도록...

 

 

---

 

오답 2

📌 오답 코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        for(int i=0; i<numbers.length; i++) {
            answer[i] = -1;
            
            for(int j=i+1; j<numbers.length; j++) {
                
                if(numbers[i] < numbers[j]) {
                    answer[i] = numbers[j];
                    break;
                }
            }
        }
        
        return answer;
    }
}

 

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (0.04ms, 69.3MB)
테스트 2 〉	통과 (0.03ms, 70.2MB)
테스트 3 〉	통과 (0.03ms, 67.8MB)
테스트 4 〉	실패 (0.03ms, 71.9MB)
	...
테스트 19 〉	실패 (26.99ms, 181MB)
테스트 20 〉	통과 (12.08ms, 199MB)
테스트 21 〉	실패 (시간 초과)
테스트 22 〉	실패 (11.69ms, 186MB)
테스트 23 〉	실패 (시간 초과)

채점 결과
정확성: 17.4
합계: 17.4 / 100.0

 

📌 오답 이유

1. 정확성 테스트 오답 이유
   
   • 시간초과도 그대로고...
   • 내가 생각하지 못했던 반례가 있는 듯 하다. "질문하기"를 통해 힌트를 얻음.

   • 

     위와 같은 경우, numbers[0]의 뒷 큰수인 numbers[9] ( = 11 ) 의 인덱스가 idx에 저장됨.
   • 그럴 경우, numbers[1]의 뒷 큰수는 10임에도 10의 인덱스가 [1] 이기 때문에
     idx보다 작아지게 됨. numbers[1]의 뒷 큰수가 numbers[9] = 11이 된다.

 

📌 개선하기

1. 정확성 테스트 오답 개선
   
   • stack을 활용하면 된다는 힌트를 얻었다.
   • 스택 / 큐 문제의 '주식가격'과 풀이 방법이 비슷하다고 하니, 이를 참고하자.

1.