๐Ÿ”ฅ[99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋””] 7์ผ์ฐจ TIL - ํ•˜๋…ธ์ด์˜ ํƒ‘

HOONSSACยท2024๋…„ 7์›” 28์ผ
1

99Club Coding Test Study

๋ชฉ๋ก ๋ณด๊ธฐ
7/41
post-thumbnail

โณ๋ฌธ์ œ

๋ฌธ์ œ ์„ค๋ช…

ํ•˜๋…ธ์ด ํƒ‘(Tower of Hanoi)์€ ํผ์ฆ์˜ ์ผ์ข…์ž…๋‹ˆ๋‹ค. ์„ธ ๊ฐœ์˜ ๊ธฐ๋‘ฅ๊ณผ ์ด ๊ธฐ๋™์— ๊ฝ‚์„ ์ˆ˜ ์žˆ๋Š” ํฌ๊ธฐ๊ฐ€ ๋‹ค์–‘ํ•œ ์›ํŒ๋“ค์ด ์žˆ๊ณ , ํผ์ฆ์„ ์‹œ์ž‘ํ•˜๊ธฐ ์ „์—๋Š” ํ•œ ๊ธฐ๋‘ฅ์— ์›ํŒ๋“ค์ด ์ž‘์€ ๊ฒƒ์ด ์œ„์— ์žˆ๋„๋ก ์ˆœ์„œ๋Œ€๋กœ ์Œ“์—ฌ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฒŒ์ž„์˜ ๋ชฉ์ ์€ ๋‹ค์Œ ๋‘ ๊ฐ€์ง€ ์กฐ๊ฑด์„ ๋งŒ์กฑ์‹œํ‚ค๋ฉด์„œ, ํ•œ ๊ธฐ๋‘ฅ์— ๊ฝ‚ํžŒ ์›ํŒ๋“ค์„ ๊ทธ ์ˆœ์„œ ๊ทธ๋Œ€๋กœ ๋‹ค๋ฅธ ๊ธฐ๋‘ฅ์œผ๋กœ ์˜ฎ๊ฒจ์„œ ๋‹ค์‹œ ์Œ“๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

  1. ํ•œ ๋ฒˆ์— ํ•˜๋‚˜์˜ ์›ํŒ๋งŒ ์˜ฎ๊ธธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  2. ํฐ ์›ํŒ์ด ์ž‘์€ ์›ํŒ ์œ„์— ์žˆ์–ด์„œ๋Š” ์•ˆ๋ฉ๋‹ˆ๋‹ค.

ํ•˜๋…ธ์ด ํƒ‘์˜ ์„ธ ๊ฐœ์˜ ๊ธฐ๋‘ฅ์„ ์™ผ์ชฝ ๋ถ€ํ„ฐ 1๋ฒˆ, 2๋ฒˆ, 3๋ฒˆ์ด๋ผ๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. 1๋ฒˆ์—๋Š” n๊ฐœ์˜ ์›ํŒ์ด ์žˆ๊ณ  ์ด n๊ฐœ์˜ ์›ํŒ์„ 3๋ฒˆ ์›ํŒ์œผ๋กœ ์ตœ์†Œ ํšŸ์ˆ˜๋กœ ์˜ฎ๊ธฐ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

1๋ฒˆ ๊ธฐ๋‘ฅ์— ์žˆ๋Š” ์›ํŒ์˜ ๊ฐœ์ˆ˜ n์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, n๊ฐœ์˜ ์›ํŒ์„ 3๋ฒˆ ์›ํŒ์œผ๋กœ ์ตœ์†Œ๋กœ ์˜ฎ๊ธฐ๋Š” ๋ฐฉ๋ฒ•์„ returnํ•˜๋Š” solution๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ ์‚ฌํ•ญ

  • n์€ 15์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ž…๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

nresult
2[ [1,2], [1,3], [2,3] ]

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

๋‹ค์Œ๊ณผ ๊ฐ™์ด ์˜ฎ๊ธธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.




โœ๏ธํ’€์ด

ํ•˜๋…ธ์ด์˜ ํƒ‘ ๋ฌธ์ œ๋Š” ๊ทœ์น™์ด ์กด์žฌํ•˜๋Š” ๋Œ€ํ‘œ์ ์ธ ์žฌ๊ท€ ๋ฌธ์ œ์ด๋‹ค.
๊ทธ๋ ‡๊ธฐ ๋•Œ๋ฌธ์—, ์ ํ™”์‹์„ ์„ธ์šฐ๋ฉด ์‰ฝ๊ฒŒ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

์šฐ์„  ์ถœ๋ฐœ์ง€, ๊ฒฝ์œ ์ง€, ๋„์ฐฉ์ง€ ์ด๋ ‡๊ฒŒ 3๊ฐœ์˜ ์œ„์น˜๋ฅผ ์„ ์–ธํ•œ๋‹ค.

๊ทธ๋ฆฌ๊ณ  ์šฐ๋ฆฌ์˜ ์ตœ์ข… ๋ชฉํ‘œ์ธ n๊ฐœ์˜ ์›ํŒ์„ ์ถœ๋ฐœ์ง€์—์„œ ๋„์ฐฉ์ง€๋กœ ์˜ฎ๊ธฐ๋Š” ๊ณผ์ •์—์„œ ์•„๋ž˜์˜ ๊ทœ์น™์ด ๋ฐœ์ƒํ•œ๋‹ค.

n-1๊ฐœ, ์ถœ๋ฐœ์ง€ -> ๊ฒฝ์œ ์ง€ + 1๊ฐœ, ์ถœ๋ฐœ์ง€ -> ๋„์ฐฉ์ง€ + n-1๊ฐœ, ๊ฒฝ์œ ์ง€ -> ๋„์ฐฉ์ง€

๊ทธ๋ฆฌ๊ณ  ์ด๋ฅผ ์ฝ”๋“œ๋กœ ๊ตฌํ˜„ํ•ด๋ณด์ž!

๐Ÿ–ฅ๏ธ์ฝ”๋“œ

import java.util.*;

class Solution {
    private static List<int[]> arr = new ArrayList<>();

    public int[][] solution(int n) {
        move(n, 1, 2, 3);
        int[][] answer = arr.stream()
                .toArray(int[][]::new);
        return answer;
    }

    private static void move(int cnt, int start, int mid, int end) {
        if (cnt == 0) {
            return;
        }
        move(cnt - 1, start, end, mid);
        arr.add(new int[]{start, end});
        move(cnt - 1, mid, start, end);
    }
}

์šฐ์„ , ์ด๋™ ์ •๋ณด๋ฅผ ์ €์žฅํ•  ๋ณ€์ˆ˜ List<int[]> arr๋ฅผ ์„ ์–ธํ•ด ์ฃผ์—ˆ๋‹ค.
๊ทธ๋ฆฌ๊ณ , ์›ํŒ์„ ์˜ฎ๊ธฐ๋Š” ๋ฉ”์†Œ๋“œ move๋ฅผ ๋งŒ๋“ค์–ด ์ฃผ์—ˆ๋Š”๋ฐ, ์—ฌ๊ธฐ์„œ cnt๋Š” ์ด๋™ํ•  ์›ํŒ์˜ ๊ฐœ์ˆ˜์ด๊ณ , start๋Š” ์ถœ๋ฐœ์ง€, mid๋Š” ๊ฒฝ์œ ์ง€, end๋Š” ๋„์ฐฉ์ง€์ด๋‹ค.

move(cnt - 1, start, end, mid);
arr.add(new int[]{start, end});
move(cnt - 1, mid, start, end);

๋งˆ์ง€๋ง‰์œผ๋กœ ์•ž์„œ ์ฐพ์€ ๊ทœ์น™์„ ๋ฐ”ํƒ•์œผ๋กœ ์ ํ™”์‹์„ ์ž‘์„ฑํ•ด ์ฃผ๋ฉด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค.


๐Ÿ”—๋ฌธ์ œ ๋งํฌ
๐Ÿ’ปRepository

profile
ํ›ˆ์‹น์˜ ๊ฐœ๋ฐœ์—ฌํ–‰

0๊ฐœ์˜ ๋Œ“๊ธ€