[programmers] νλ°°μμ - Java
νλ°°μμλ₯Ό νΈλμ μ€μ΄μΌ νλ λ¬Έμ μμ, μμ¬λ 컨ν
μ΄λ 벨νΈμμ μμλ₯Ό μνλ μμλ‘ μ€μ΄μΌ νλ©°, 보쑰 컨ν
μ΄λ 벨νΈλ₯Ό μ΄μ©ν΄ μμλ₯Ό μμλ‘ λ³΄κ΄ν μ μλ€. μ£Όμ΄μ§ μμμ λ§μΆ° λͺ κ°μ μμλ₯Ό μ±κ³΅μ μΌλ‘ μ€μ μ μλμ§λ₯Ό κ³μ°νλ Java μ루μ
μ μ 곡νλ©°, μ€νμ νμ©νμ¬ μμλ₯Ό κ΄λ¦¬νλ λ°©λ²μ μ€λͺ
νλ€.
Oct 21, 2024
νλ°°μμ
λ¬Έμ μ€λͺ
μμ¬λ νλ°°μμλ₯Ό νΈλμ μ£λ μΌμ ν©λλ€. μμ¬κ° μ€μ΄μΌ νλ νλ°°μμλ ν¬κΈ°κ° λͺ¨λ κ°μΌλ©° 1λ² μμλΆν° nλ² μμκΉμ§ λ²νΈκ° μ¦κ°νλ μμλλ‘ μ»¨ν
μ΄λ 벨νΈμ μΌλ ¬λ‘ λμ¬ μμ¬μκ² μ λ¬λ©λλ€. 컨ν
μ΄λ 벨νΈλ ν λ°©ν₯μΌλ‘λ§ μ§νμ΄ κ°λ₯ν΄μ 벨νΈμ λμΈ μμλλ‘(1λ² μμλΆν°) μμλ₯Ό λ΄λ¦΄ μ μμ΅λλ€. νμ§λ§ 컨ν
μ΄λ 벨νΈμ λμΈ μμλλ‘ νλ°°μμλ₯Ό λ΄λ € λ°λ‘ νΈλμ μ£κ² λλ©΄ νλ°° κΈ°μ¬λμ΄ λ°°λ¬νλ μμμ νλ°°μμκ° μ€λ € μλ μμκ° λ§μ§ μμ λ°°λ¬μ μ°¨μ§μ΄ μκΉλλ€. λ°λΌμ νλ°° κΈ°μ¬λμ΄ λ―Έλ¦¬ μλ €μ€ μμμ λ§κ² μμ¬κ° νλ°°μμλ₯Ό μ€μ΄μΌ ν©λλ€.
λ§μ½ 컨ν
μ΄λ 벨νΈμ 맨 μμ λμΈ μμκ° νμ¬ νΈλμ μ€μ΄μΌ νλ μμκ° μλλΌλ©΄ κ·Έ μμλ₯Ό νΈλμ μ€μ μμκ° λ λκΉμ§ μ μ λ€λ₯Έ κ³³μ 보κ΄ν΄μΌ ν©λλ€. νμ§λ§ κ³ κ°μ 물건μ ν¨λΆλ‘ λ
μ λ μ μμ΄ λ³΄μ‘° 컨ν
μ΄λ 벨νΈλ₯Ό μΆκ°λ‘ μ€μΉνμμ΅λλ€. 보쑰 컨ν
μ΄λ 벨νΈλ μ λ€λ‘ μ΄λμ΄ κ°λ₯νμ§λ§ μ
ꡬ μΈμ λ€λ₯Έ λ©΄μ΄ λ§ν μμ΄μ 맨 μμ μμλ§ λΊ μ μμ΅λλ€(μ¦, κ°μ₯ λ§μ§λ§μ 보쑰 컨ν
μ΄λ 벨νΈμ 보κ΄ν μμλΆν° κΊΌλ΄κ² λ©λλ€). 보쑰 컨ν
μ΄λ 벨νΈλ₯Ό μ΄μ©ν΄λ κΈ°μ¬λμ΄ μνλ μμλλ‘ μμλ₯Ό μ£μ§ λͺ» νλ€λ©΄, λ μ΄μ μμλ₯Ό μ£μ§ μμ΅λλ€.
μλ₯Ό λ€μ΄, μμ¬κ° 5κ°μ μμλ₯Ό μ€μ΄μΌ νλ©°, νλ°° κΈ°μ¬λμ΄ μλ €μ€ μμκ° κΈ°μ‘΄μ 컨ν
μ΄λ 벨νΈμ λ€ λ²μ§Έ, μΈ λ²μ§Έ, 첫 λ²μ§Έ, λ λ²μ§Έ, λ€μ― λ²μ§Έ λμΈ νλ°°μμ μμμΈ κ²½μ°, μμ¬λ μ°μ 첫 λ²μ§Έ, λ λ²μ§Έ, μΈ λ²μ§Έ μμλ₯Ό 보쑰 컨ν
μ΄λ 벨νΈμ 보κ΄ν©λλ€. κ·Έ ν λ€ λ²μ§Έ μμλ₯Ό νΈλμ μ£κ³ 보쑰 컨ν
μ΄λ 벨νΈμμ μΈ λ²μ§Έ μμ λΉΌμ νΈλμμ£μ΅λλ€. λ€μμΌλ‘ 첫 λ²μ§Έ μμλ₯Ό μ€μ΄μΌ νμ§λ§ 보쑰 컨ν
μ΄λ 벨νΈμμλ λ λ²μ§Έ μμλ₯Ό, κΈ°μ‘΄μ 컨ν
μ΄λ 벨νΈμλ λ€μ― λ²μ§Έ μμλ₯Ό κΊΌλΌ μ μκΈ° λλ¬Έμ λμ΄μμ μμλ μ€μ μ μμ΅λλ€. λ°λΌμ νΈλμλ 2κ°μ μμλ§ μ€λ¦¬κ² λ©λλ€.
νλ°° κΈ°μ¬λμ΄ μνλ μμ μμλ₯Ό λνλ΄λ μ μ λ°°μ΄
order
κ° μ£Όμ΄μ‘μ λ, μμ¬κ° λͺ κ°μ μμλ₯Ό μ€μ μ μλμ§ return νλ solution ν¨μλ₯Ό μμ±νμΈμ.μ νμ¬ν
- 1 β€
order
μ κΈΈμ΄ β€ 1,000,000
order
λ 1μ΄μorder
μ κΈΈμ΄ μ΄νμ λͺ¨λ μ μκ° νλ²μ© λ±μ₯ν©λλ€.
order[i]
λ κΈ°μ‘΄μ 컨ν μ΄λ 벨νΈμorder[i]
λ²μ§Έ μμλ₯Ό i+1λ²μ§Έλ‘ νΈλμ μ€μ΄μΌ ν¨μ μλ―Έν©λλ€.
μ μΆλ ₯ μ
order | result |
[4, 3, 1, 2, 5] | 2 |
[5, 4, 3, 2, 1] | 5 |
μ μΆλ ₯ μ μ€λͺ
μ
μΆλ ₯ μ #1
- λ¬Έμ μμμ κ°μ΅λλ€.
μ
μΆλ ₯ μ #2
- λͺ¨λ μμλ₯Ό 보쑰 컨ν μ΄λ 벨νΈμ λͺ¨λ λ£κ³ , μμμΌλ‘ νλμ© λΉΌμ νΈλμ μ£μ΅λλ€.
solution.java
import java.util.*; class Solution { public int solution(int[] order) { Stack<Integer> stack = new Stack<>(); // 보쑰 컨ν μ΄λ λ²¨νΈ int currentBox = 1; // 컨ν μ΄λ 벨νΈμ λ€μ μμ int loadedCount = 0; // μ±κ³΅μ μΌλ‘ μ€μ μμ μ for (int targetBox : order) { // μνλ μμμ λλ¬νκ±°λ λ€ κΊΌλΌ λκΉμ§ λ°λ³΅ while (currentBox <= order.length && currentBox < targetBox) { stack.push(currentBox); currentBox++; } // νμ¬ μ»¨ν μ΄λ 벨νΈμ μμκ° μνλ μμμΈ κ²½μ° μ€λλ€ if (currentBox == targetBox) { loadedCount++; currentBox++; } // μλλΌλ©΄ μνλ μμκ° λ³΄μ‘° μ€νμ μλ¨μ μλμ§ νμΈ else if (!stack.isEmpty() && stack.peek() == targetBox) { stack.pop(); loadedCount++; } // λ 쑰건 λͺ¨λ μΆ©μ‘±λμ§ μμΌλ©΄ μμλ₯Ό μ€μ μ μμ else { break; } } return loadedCount; } }
ν΅μ¬ ν€μλ
- 컨ν
μ΄λ 벨νΈμ
νμ¬ μμ
κ° order λ°°μ΄μλͺ©ν μμ
λ³΄λ€ μμΌλ©΄λͺ©ν μμ
μ λλ¬ν λκΉμ§ μ€νμ λ°μ΄ λ£λλ€.
- μ€ν μλ¨μ μλ μμκ° μνλ μμμΈ κ²½μ° μ€νμμ ν΄λΉ μμλ₯Ό
pop
νκ³ μΉ΄μ΄νΈλ₯Ό μ¦κ°μν¨λ€.
- 벨νΈλ μ€νμ μνλ μμκ° μμΌλ©΄ μ μ¬λ₯Ό μ€μ§νλ€.
κ²°λ‘ !
μ€νμ μ΄μ©ν΄μ ν΄λΉ λ¬Έμ λ₯Ό ν μ μμλ€.
Share article