View

λ°˜μ‘ν˜•

πŸ’‘ 문제

μ •μˆ˜λ‘œ 이루어진 λ°°μ—΄ 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]

μž…μΆœλ ₯ 예 μ„€λͺ…

μž…μΆœλ ₯ 예 #12의 λ’· ν°μˆ˜λŠ” 3μž…λ‹ˆλ‹€. 첫 번째 3의 λ’· ν°μˆ˜λŠ” 5μž…λ‹ˆλ‹€. 두 번째 3 λ˜ν•œ λ§ˆμ°¬κ°€μ§€μž…λ‹ˆλ‹€. 5λŠ” λ’· ν°μˆ˜κ°€ μ—†μœΌλ―€λ‘œ -1μž…λ‹ˆλ‹€. μœ„ μˆ˜λ“€μ„ μ°¨λ‘€λŒ€λ‘œ 배열에 λ‹΄μœΌλ©΄ [3, 5, 5, -1]이 λ©λ‹ˆλ‹€.

μž…μΆœλ ₯ 예 #29λŠ” λ’· ν°μˆ˜κ°€ μ—†μœΌλ―€λ‘œ -1μž…λ‹ˆλ‹€. 1의 λ’· ν°μˆ˜λŠ” 5이며, 5와 3의 λ’· ν°μˆ˜λŠ” 6μž…λ‹ˆλ‹€. 6κ³Ό 2λŠ” λ’· ν°μˆ˜κ°€ μ—†μœΌλ―€λ‘œ -1μž…λ‹ˆλ‹€. μœ„ μˆ˜λ“€μ„ μ°¨λ‘€λŒ€λ‘œ 배열에 λ‹΄μœΌλ©΄ [-1, 5, 6, 6, -1, -1]이 λ©λ‹ˆλ‹€.

πŸ’‘ μ½”λ“œ

⇒ μŠ€νƒμ„ 쓰지 μ•Šμ•„μ„œ μ‹œκ°„ 초과둜 μ‹€νŒ¨ν•œ μ½”λ“œ

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int [numbers.length];
        
        //이쀑for문을 λŒλ©΄μ„œ 자기 λ’€ μžˆλŠ” 수 μ€‘μ—μ„œ 크고 κ°€κΉŒμš΄ 값을 max에 μž„μ‹œ μ €μž₯
        for (int i=0; i<numbers.length; i++){
            int max=0;
            for (int next=i+1; next<numbers.length; next++){
                //큰 수λ₯Ό λ°œκ²¬ν•˜λ©΄ ? -> max에 μž„μ‹œλ‘œ λ„£μ–΄λ‘ 
              if (numbers[i]  < numbers[next] )  {
                  max=Math.max(max, numbers[next]); 
                  break;
                }
            }
            if (max==0){
                //λ‚˜λ³΄λ‹€ 큰 수λ₯Ό λ°œκ²¬ν•˜μ§€ λͺ»ν•˜λ©΄ -1을 λ„£μœΌμ€Œ 
                answer[i]=-1;
            }    
            else {
                answer[i]=max;
            }
             // λ‹€μŒ maxλ₯Ό μ°ΎκΈ° μœ„ν•΄μ„œ 0으둜 μ΄ˆκΈ°ν™” 
            max=0;
        }

        return answer;
    }
}

⬇️ μ™„μ„±λœ μ½”λ“œ

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int [numbers.length];
        
        Stack <Integer> stack = new Stack <>();// 뒀에 μžˆλŠ” 수 쀑에 큰 값을 발견 λͺ»ν•˜λ©΄ μŠ€νƒμ— λ„£μŒ
        Arrays.fill(answer, -1);
        
        for (int i=0; i<numbers.length; i++){
                           while(!stack.isEmpty()  && numbers[stack.peek()]<numbers[i]){
                    answer[stack.pop()]=numbers[i];
                }
                stack.push(i);

        }
        return answer;
    }
}

1. indexλ₯Ό μ΄μš©ν•˜κΈ°

2. λΉ„κ΅ν•˜λŠ” μˆ˜λ³΄λ‹€  큰 수λ₯Ό λ°œκ²¬ν•˜μ§€ λͺ»ν•˜κ±°λ‚˜ μŠ€νƒμ΄ λΉ„μ–΄μžˆλ‹€λ©΄(처음 μ‹œμž‘ν•  λ•Œ λ“±) -> push 

3. λΉ„κ΅ν•˜λŠ” 수 보닀 큰 수λ₯Ό λ°œκ²¬ν–ˆλ‹€λ©΄ μŠ€νƒ -> pop

πŸ’‘ 보완할 점

λΉ„μŠ·ν•œ 문제: https://www.acmicpc.net/problem/17298 λ°±μ€€ κ³¨λ“œ5

λ°˜μ‘ν˜•
Share Link
reply
λ°˜μ‘ν˜•
Β«   2024/11   Β»
일 μ›” ν™” 수 λͺ© 금 ν† 
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30