[programmers] νƒλ°°μƒμž - Java

νƒλ°°μƒμžλ₯Ό νŠΈλŸ­μ— μ‹€μ–΄μ•Ό ν•˜λŠ” λ¬Έμ œμ—μ„œ, μ˜μž¬λŠ” μ»¨ν…Œμ΄λ„ˆ λ²¨νŠΈμ—μ„œ μƒμžλ₯Ό μ›ν•˜λŠ” μˆœμ„œλ‘œ μ‹€μ–΄μ•Ό ν•˜λ©°, 보쑰 μ»¨ν…Œμ΄λ„ˆ 벨트λ₯Ό μ΄μš©ν•΄ μƒμžλ₯Ό μž„μ‹œλ‘œ 보관할 수 μžˆλ‹€. 주어진 μˆœμ„œμ— 맞좰 λͺ‡ 개의 μƒμžλ₯Ό μ„±κ³΅μ μœΌλ‘œ 싀을 수 μžˆλŠ”μ§€λ₯Ό κ³„μ‚°ν•˜λŠ” Java μ†”λ£¨μ…˜μ„ μ œκ³΅ν•˜λ©°, μŠ€νƒμ„ ν™œμš©ν•˜μ—¬ μƒμžλ₯Ό κ΄€λ¦¬ν•˜λŠ” 방법을 μ„€λͺ…ν•œλ‹€.
DriedPollack's avatar
Oct 21, 2024
[programmers] νƒλ°°μƒμž - Java

νƒλ°°μƒμž

문제 μ„€λͺ…

μ˜μž¬λŠ” νƒλ°°μƒμžλ₯Ό νŠΈλŸ­μ— μ‹£λŠ” 일을 ν•©λ‹ˆλ‹€. μ˜μž¬κ°€ μ‹€μ–΄μ•Ό ν•˜λŠ” νƒλ°°μƒμžλŠ” 크기가 λͺ¨λ‘ κ°™μœΌλ©° 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

More articles

See more posts

πŸ‘¨πŸ»β€πŸ’»DriedPollack's Blog