View
[νλ‘κ·Έλλ¨Έμ€] 2οΈβ£ λ€μ μλ ν° μ μ°ΎκΈ°(JAVA)
μ± μ½λ κ°μ 2023. 3. 4. 15:57π‘ λ¬Έμ
μ μλ‘ μ΄λ£¨μ΄μ§ λ°°μ΄ 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
'μκ³ λ¦¬μ¦ > μ½λ©ν μ€νΈ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[νλ‘κ·Έλλ¨Έμ€ ] 2οΈβ£ μ νλ²νΈ λͺ©λ‘ (JAVA) (0) | 2023.06.26 |
---|---|
[νλ‘κ·Έλλ¨Έμ€] 2οΈβ£ μΉ΄ν«(JAVA) (0) | 2023.03.20 |
[νλ‘κ·Έλλ¨Έμ€] 2οΈβ£μ΅μκ° λ§λ€κΈ° (JAVA) (0) | 2023.02.24 |
[νλ‘κ·Έλλ¨Έμ€] 2οΈβ£ 무μΈλ μ¬ν(JAVA) (0) | 2023.02.24 |
[λ°±μ€] 14502: μ°κ΅¬μ (Java) (0) | 2022.10.09 |