algorithm study 프로그래머스 숫자 짝꿍 최고의 집합 하노이의 탑 python

파이썬 알고리즘 : 숫자 짝꿍, 최고의 집합, 하노이의 탑

프로그래머스

2023년 8월 28일 알고리즘 문제풀이

문제 1 프로그래머스 숫자 짝꿍

문제 링크

1차 시도

나의 생각

두 문자열에서 각 숫자가 몇번 등장하는 지를 확인한다. 사용할 수 있는 수는 각 숫자의 등장 횟수 중 적은 쪽이다. 예를 들어, 숫자 5가 X에서는 3번, Y에서는 7번 등장한다면 짝꿍을 위해 숫자 5는 3번 쓰일 수 있다. 짝꿍은 가장 큰 수를 나타내야 하므로 사용 가능한 정수 중 큰것부터 소모하면 된다. 사용 가능한 숫자가 0만 있을 경우와 아무것도 없을 경우도 조건문을 통해 따로 체크한다.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

def solution(X, Y):
    x = str(X)
    nx = len(x)
    y = str(Y)
    ny = len(y)
    arr = [0 for _ in range(10)]
    arr_x = [0 for _ in range(10)]
    arr_y = [0 for _ in range(10)]
    ans = []
    flag = 0

    for i in range(nx):
        tmp = x[i]
        arr_x[int(tmp)] += 1
    for j in range(ny):
        tmp = y[j]
        arr_y[int(tmp)] += 1

    for k in range(10):
        arr[k] = min(arr_x[k],arr_y[k])

    for i in range(9,-1,-1):
        if arr[i]:
            flag = max(flag,i)
        cnt = arr[i]
        while cnt >0:
            ans.append(i)
            cnt -= 1

    if flag:
        answer = ''.join(str(i) for i in ans)
    else:
        if arr[0]:
            answer = "0"
        else:
            answer = "-1"
    return answer

문제 2 최고의 집합

문제 링크

1차 시도

나의 생각

곱해서 최대가 되기 위해선 모든 값들이 가장 비슷한 값을 가져야 한다고 생각하였다. 따라서 s를 n으로 나눈 몫을 구해준 뒤, 나머지만큼 1씩 더해주었다.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13

def solution(n, s):
    answer = []
    tmp = s//n
    cnt = s%n
    if not tmp:
        answer = [-1]
    else:
        for i in range(n):
            answer.append(tmp)
        for i in range(1,cnt+1):
            answer[i] += 1
        answer.sort()
    return answer

문제 3 하노이의 탑

1차 시도

나의 생각

1개를 1에서 3으로 옮길때는 1 -> 3으로 보내면 된다. 2개를 옮길때부터 규칙성이 생긴다. 3개중 도착지가 아닌 남은 목적지로 맨 위 에 있는 1개를 보낸다. 이 후 남은 한개를 목적지로 보내고, 다른 곳으로 간 하나도 마저 옮기면 된다. 즉, n개를 1에서 3으로 옮기는 방법은. 맨 위부터 n-1개 까지를 2번 탑으로 보낸 후 가장 밑에 있던 것을 3번 탑으로 옮기는 것이다. 그 후 2번 탑에서 나머지를 3번탑으로 보내면 된다.

정리하면 다음과 같다.

  • n개를 1에서 3으로 보내는 방법은 n-1개를 1에서 2로 보낸 후, 남은 한개를 3번 탑으로 넘기고 남은 n-1개들을 2번에서 3번으로 옮긴다.
  • n-1개를 1에서 3으로 보내는 방법은 n-2개를 1에서 2로 보낸 후, 남은 한개를 3번 탑으로 넘기고 남은 n-2개들을 2번에서 3번으로 옮긴다.
  • n-2개를 1에서 3으로 보내는 방법은 n-3개를 1에서 2로 보낸 후, 남은 한개를 3번 탑으로 넘기고 남은 n-3개들을 2번에서 3번으로 옮긴다.
  • x개를 a에서 b로 보내는 방법은 x-1개를 a에서 6-a-b로 보낸 후, 남은 한개를 b번 탑으로 넘기고 남은 x-1개들을 6-a-b에서 b번으로 옮긴다. => def move(a,b,x)

move(a,b,x) = move(a,6-a-b,x-1) + move(a,b,1) + move(6-a-b,b,x-1) 임을 유추할 수 있다.

6-a-b 인 이유는 총 탑이 3개이기 때문이다. 1+2+3=6 임을 이용한 것이다. 4라면 6이 아니라 10일 것.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13

def solution(n):
    answer = []

    def move(a,b,x):
        if x == 1:
            answer.append([a,b])
        else:
            move(a,6-a-b,x-1)
            move(a,b,1)
            move(6-a-b,b,x-1)

    move(1,3,n)
    return answer
CATALOG
    algorithm