β˜•JavaπŸ’‘Coding Test

[programmers] ν”Όλ‘œλ„ - Java

XXκ²Œμž„μ˜ ν”Όλ‘œλ„ μ‹œμŠ€ν…œμ—μ„œ μœ μ €κ°€ νƒν—˜ν•  수 μžˆλŠ” μ΅œλŒ€ λ˜μ „ 수λ₯Ό λ°˜ν™˜ν•˜λŠ” 문제λ₯Ό ν•΄κ²°ν•˜κΈ° μœ„ν•΄, 깊이 μš°μ„  탐색(DFS)λ₯Ό μ‚¬μš©ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜μ΄ μ œμ‹œλ˜μ—ˆμŠ΅λ‹ˆλ‹€. 각 λ˜μ „μ˜ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"와 "μ†Œλͺ¨ ν”Όλ‘œλ„"λ₯Ό κ³ λ €ν•˜μ—¬, ν˜„μž¬ ν”Όλ‘œλ„κ°€ μΆ©λΆ„ν•˜κ³  아직 νƒν—˜ν•˜μ§€ μ•Šμ€ λ˜μ „μ„ νƒμƒ‰ν•˜λ©°, 탐색이 λλ‚œ λ˜μ „μ€ λ‹€μ‹œ νƒμƒ‰ν•˜μ§€ μ•Šμ€ μƒνƒœλ‘œ λ³€κ²½ν•©λ‹ˆλ‹€. 이 과정을 λ°˜λ³΅ν•˜λ©° νƒν—˜ν•œ λ˜μ „μ˜ μ΅œλŒ€ 수λ₯Ό κ³„μ‚°ν•©λ‹ˆλ‹€.
DriedPollack's avatar
DriedPollack
Mar 20, 2024
[programmers] ν”Όλ‘œλ„ - Java
Contents
ν”Όλ‘œλ„ solution.java핡심 ν‚€μ›Œλ“œκ²°λ‘ !

ν”Όλ‘œλ„

문제 μ„€λͺ…

XXκ²Œμž„μ—λŠ” ν”Όλ‘œλ„ μ‹œμŠ€ν…œ(0 μ΄μƒμ˜ μ •μˆ˜λ‘œ ν‘œν˜„ν•©λ‹ˆλ‹€)이 있으며, 일정 ν”Όλ‘œλ„λ₯Ό μ‚¬μš©ν•΄μ„œ λ˜μ „μ„ νƒν—˜ν•  수 μžˆμŠ΅λ‹ˆλ‹€. μ΄λ•Œ, 각 λ˜μ „λ§ˆλ‹€ νƒν—˜μ„ μ‹œμž‘ν•˜κΈ° μœ„ν•΄ ν•„μš”ν•œ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"와 λ˜μ „ νƒν—˜μ„ λ§ˆμ³€μ„ λ•Œ μ†Œλͺ¨λ˜λŠ” "μ†Œλͺ¨ ν”Όλ‘œλ„"κ°€ μžˆμŠ΅λ‹ˆλ‹€. "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"λŠ” ν•΄λ‹Ή λ˜μ „μ„ νƒν—˜ν•˜κΈ° μœ„ν•΄ 가지고 μžˆμ–΄μ•Ό ν•˜λŠ” μ΅œμ†Œν•œμ˜ ν”Όλ‘œλ„λ₯Ό λ‚˜νƒ€λ‚΄λ©°, "μ†Œλͺ¨ ν”Όλ‘œλ„"λŠ” λ˜μ „μ„ νƒν—˜ν•œ ν›„ μ†Œλͺ¨λ˜λŠ” ν”Όλ‘œλ„λ₯Ό λ‚˜νƒ€λƒ…λ‹ˆλ‹€. 예λ₯Ό λ“€μ–΄ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"κ°€ 80, "μ†Œλͺ¨ ν”Όλ‘œλ„"κ°€ 20인 λ˜μ „μ„ νƒν—˜ν•˜κΈ° μœ„ν•΄μ„œλŠ” μœ μ €μ˜ ν˜„μž¬ 남은 ν”Όλ‘œλ„λŠ” 80 이상 이어야 ν•˜λ©°, λ˜μ „μ„ νƒν—˜ν•œ ν›„μ—λŠ” ν”Όλ‘œλ„ 20이 μ†Œλͺ¨λ©λ‹ˆλ‹€.
이 κ²Œμž„μ—λŠ” ν•˜λ£¨μ— ν•œ λ²ˆμ”© νƒν—˜ν•  수 μžˆλŠ” λ˜μ „μ΄ μ—¬λŸ¬κ°œ μžˆλŠ”λ°, ν•œ μœ μ €κ°€ 였늘 이 λ˜μ „λ“€μ„ μ΅œλŒ€ν•œ 많이 νƒν—˜ν•˜λ € ν•©λ‹ˆλ‹€. μœ μ €μ˜ ν˜„μž¬ ν”Όλ‘œλ„ k와 각 λ˜μ „λ³„ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„", "μ†Œλͺ¨ ν”Όλ‘œλ„"κ°€ λ‹΄κΈ΄ 2차원 λ°°μ—΄ dungeons κ°€ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, μœ μ €κ°€ νƒν—˜ν• μˆ˜ μžˆλŠ” μ΅œλŒ€ λ˜μ „ 수λ₯Ό return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μ™„μ„±ν•΄μ£Όμ„Έμš”.

μ œν•œμ‚¬ν•­

  • kλŠ” 1 이상 5,000 μ΄ν•˜μΈ μžμ—°μˆ˜μž…λ‹ˆλ‹€.
  • dungeons의 μ„Έλ‘œ(ν–‰) 길이(즉, λ˜μ „μ˜ 개수)λŠ” 1 이상 8 μ΄ν•˜μž…λ‹ˆλ‹€.
    • dungeons의 κ°€λ‘œ(μ—΄) κΈΈμ΄λŠ” 2 μž…λ‹ˆλ‹€.
    • dungeons의 각 행은 각 λ˜μ „μ˜ ["μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„", "μ†Œλͺ¨ ν”Όλ‘œλ„"] μž…λ‹ˆλ‹€.
    • "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"λŠ” 항상 "μ†Œλͺ¨ ν”Όλ‘œλ„"보닀 ν¬κ±°λ‚˜ κ°™μŠ΅λ‹ˆλ‹€.
    • "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"와 "μ†Œλͺ¨ ν”Όλ‘œλ„"λŠ” 1 이상 1,000 μ΄ν•˜μΈ μžμ—°μˆ˜μž…λ‹ˆλ‹€.
    • μ„œλ‘œ λ‹€λ₯Έ λ˜μ „μ˜ ["μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„", "μ†Œλͺ¨ ν”Όλ‘œλ„"]κ°€ μ„œλ‘œ 같을 수 μžˆμŠ΅λ‹ˆλ‹€.

μž…μΆœλ ₯ 예

k
dungeons
result
80
[[80,20],[50,40],[30,10]]
3

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

ν˜„μž¬ ν”Όλ‘œλ„λŠ” 80μž…λ‹ˆλ‹€.
λ§Œμ•½, 첫 번째 β†’ 두 번째 β†’ μ„Έ 번째 λ˜μ „ μˆœμ„œλ‘œ νƒν—˜ν•œλ‹€λ©΄
  • ν˜„μž¬ ν”Όλ‘œλ„λŠ” 80이며, 첫 번째 λ˜μ „μ„ λŒκΈ°μœ„ν•΄ ν•„μš”ν•œ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„" λ˜ν•œ 80μ΄λ―€λ‘œ, 첫 번째 λ˜μ „μ„ νƒν—˜ν•  수 μžˆμŠ΅λ‹ˆλ‹€. 첫 번째 λ˜μ „μ˜ "μ†Œλͺ¨ ν”Όλ‘œλ„"λŠ” 20μ΄λ―€λ‘œ, λ˜μ „μ„ νƒν—˜ν•œ ν›„ 남은 ν”Όλ‘œλ„λŠ” 60μž…λ‹ˆλ‹€.
  • 남은 ν”Όλ‘œλ„λŠ” 60이며, 두 번째 λ˜μ „μ„ λŒκΈ°μœ„ν•΄ ν•„μš”ν•œ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"λŠ” 50μ΄λ―€λ‘œ, 두 번째 λ˜μ „μ„ νƒν—˜ν•  수 μžˆμŠ΅λ‹ˆλ‹€. 두 번째 λ˜μ „μ˜ "μ†Œλͺ¨ ν”Όλ‘œλ„"λŠ” 40μ΄λ―€λ‘œ, λ˜μ „μ„ νƒν—˜ν•œ ν›„ 남은 ν”Όλ‘œλ„λŠ” 20μž…λ‹ˆλ‹€.
  • 남은 ν”Όλ‘œλ„λŠ” 20이며, μ„Έ 번째 λ˜μ „μ„ λŒκΈ°μœ„ν•΄ ν•„μš”ν•œ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"λŠ” 30μž…λ‹ˆλ‹€. λ”°λΌμ„œ μ„Έ 번째 λ˜μ „μ€ νƒν—˜ν•  수 μ—†μŠ΅λ‹ˆλ‹€.
λ§Œμ•½, 첫 번째 β†’ μ„Έ 번째 β†’ 두 번째 λ˜μ „ μˆœμ„œλ‘œ νƒν—˜ν•œλ‹€λ©΄
  • ν˜„μž¬ ν”Όλ‘œλ„λŠ” 80이며, 첫 번째 λ˜μ „μ„ λŒκΈ°μœ„ν•΄ ν•„μš”ν•œ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„" λ˜ν•œ 80μ΄λ―€λ‘œ, 첫 번째 λ˜μ „μ„ νƒν—˜ν•  수 μžˆμŠ΅λ‹ˆλ‹€. 첫 번째 λ˜μ „μ˜ "μ†Œλͺ¨ ν”Όλ‘œλ„"λŠ” 20μ΄λ―€λ‘œ, λ˜μ „μ„ νƒν—˜ν•œ ν›„ 남은 ν”Όλ‘œλ„λŠ” 60μž…λ‹ˆλ‹€.
  • 남은 ν”Όλ‘œλ„λŠ” 60이며, μ„Έ 번째 λ˜μ „μ„ λŒκΈ°μœ„ν•΄ ν•„μš”ν•œ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"λŠ” 30μ΄λ―€λ‘œ, μ„Έ 번째 λ˜μ „μ„ νƒν—˜ν•  수 μžˆμŠ΅λ‹ˆλ‹€. μ„Έ 번째 λ˜μ „μ˜ "μ†Œλͺ¨ ν”Όλ‘œλ„"λŠ” 10μ΄λ―€λ‘œ, λ˜μ „μ„ νƒν—˜ν•œ ν›„ 남은 ν”Όλ‘œλ„λŠ” 50μž…λ‹ˆλ‹€.
  • 남은 ν”Όλ‘œλ„λŠ” 50이며, 두 번째 λ˜μ „μ„ λŒκΈ°μœ„ν•΄ ν•„μš”ν•œ "μ΅œμ†Œ ν•„μš” ν”Όλ‘œλ„"λŠ” 50μ΄λ―€λ‘œ, 두 번째 λ˜μ „μ„ νƒν—˜ν•  수 μžˆμŠ΅λ‹ˆλ‹€. 두 번째 λ˜μ „μ˜ "μ†Œλͺ¨ ν”Όλ‘œλ„"λŠ” 40μ΄λ―€λ‘œ, λ˜μ „μ„ νƒν—˜ν•œ ν›„ 남은 ν”Όλ‘œλ„λŠ” 10μž…λ‹ˆλ‹€.
λ”°λΌμ„œ 이 경우 μ„Έ λ˜μ „μ„ λͺ¨λ‘ νƒν—˜ν•  수 있으며, μœ μ €κ°€ νƒν—˜ν•  수 μžˆλŠ” μ΅œλŒ€ λ˜μ „ μˆ˜λŠ” 3μž…λ‹ˆλ‹€.
β€» 곡지 - 2022λ…„ 2μ›” 25일 ν…ŒμŠ€νŠΈμΌ€μ΄μŠ€κ°€ μΆ”κ°€λ˜μ—ˆμŠ΅λ‹ˆλ‹€.

solution.java

import java.util.*;
class Solution {
    public int answer;
    public boolean[] visited;

    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        dfs(0, k, dungeons);
        return answer;
    }
    
    public void dfs(int depth, int k, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && dungeons[i][0] <= k) {
                visited[i] = true;
                dfs(depth + 1, k - dungeons[i][1], dungeons);
                visited[i] = false;
            }
        }
        answer = Math.max(answer, depth);
    }
}
 

핡심 ν‚€μ›Œλ“œ

  • μ΅œλŒ€ 탐색 수λ₯Ό 담을 λ³€μˆ˜μ™€ 각 λ˜μ „μ„ ν˜„μž¬ νƒμƒ‰ν•œ μƒνƒœμΈμ§€ λ‚˜νƒ€λ‚΄λŠ” 배열을 μ„ μ–Έν•œλ‹€.
  • ν˜„μž¬ κΉŠμ΄μ™€ ν˜„μž¬ ν”Όλ‘œλ„λ₯Ό νŒŒλΌλ―Έν„°λ‘œ dfs λ©”μ„œλ“œλ₯Ό μ‹€ν–‰ν•œλ‹€.
    • 첫 번째 λ˜μ „λΆ€ν„° λ°©λ¬Έν•˜λ©° λ§Œμ•½ ν•΄λ‹Ή λ˜μ „μ„ νƒμƒ‰ν•œ μƒνƒœκ°€ μ•„λ‹ˆκ³ , ν˜„μž¬ ν”Όλ‘œλ„κ°€ λ°©λ¬Έν•œ λ˜μ „μ˜ ν•„μš” ν”Όλ‘œλ„λ³΄λ‹€ κ°™κ±°λ‚˜ μž‘μ€ 경우, λ‹€μŒκ³Ό 같이 μ§„ν–‰λœλ‹€.
      • λ˜μ „μ„ νƒμƒ‰ν•œ κ²ƒμœΌλ‘œ ν‘œμ‹œν•˜κ³ , 깊이λ₯Ό μ—…λ°μ΄νŠΈν•˜κ³ , λ˜μ „μ—μ„œ μ†Œλͺ¨ν•œ ν”Όλ‘œλ„λ§ŒνΌ 남은 ν”Όλ‘œλ„λ₯Ό κ°μ†Œμ‹œν‚€κ³ , dfsλ₯Ό μž¬κ·€μ μœΌλ‘œ ν˜ΈμΆœν•΄μ„œ 좔가적인 λΆ„κΈ°λ₯Ό νƒμƒ‰ν•œλ‹€.
      • ν•΄λ‹Ή λΆ„κΈ°μ˜ 탐색이 λλ‚˜λ©΄ νƒμƒ‰ν–ˆλ˜ λ˜μ „μ„ νƒμƒ‰ν•˜μ§€ μ•Šμ€ λ˜μ „μœΌλ‘œ λ°”κΎΌλ‹€.
    • ν˜„μž¬ κΉŠμ΄μ™€ μ΅œλŒ€ 탐색 수λ₯Ό λΉ„κ΅ν•΄μ„œ 더 큰 값을 μ΅œλŒ€ 탐색 수둜 μ €μž₯ν•œλ‹€.
 

κ²°λ‘ !

처음 문제λ₯Ό μ ‘ν–ˆμ„ λ•Œ dfsλ₯Ό ν™œμš©ν•˜λŠ” λ¬Έμ œμž„μ„ νŒŒμ•…ν•˜μ§€ λͺ»ν•΄ μ•Œκ³ λ¦¬μ¦˜ ꡬ성에 어렀움을 κ²ͺμ—ˆλ‹€.
 
Share article

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

RSSΒ·Powered by Inblog