Being Programmer

[백준][파이썬] 16936번 - 나3곱2

문제 번호 : 16936

문제 출처 : https://www.acmicpc.net/problem/16936

Code

n = int(input())
B = list(map(int, input().split()))
x = min(B)
old_power = 0

for b in B:
    i = 3
    power = 0
    while i <= b:
        if b % i == 0:
            power += 1
        i *= 3
    if power > old_power or (power == old_power and b < x):
        x = b
        old_power = power
        
A = []
A.append(x)
count = 1
while count < n:
    if x * 2 in B:
        x = x * 2
        A.append(x)
        count += 1
    else:
        x = x // 3
        A.append(x)
        count += 1

for a in A:
    print(a, end=' ')

Idea

1. 가장 큰 수가 짝수이면 얘는 절대 x는 아니다?    False
   
   • 예제 2번에서 보듯 가장 큰 수가 짝수여도 x일 수 있다.
2. 오른쪽으로 갈수록 수의 2^n배 증가하고 3^-n배로 감소한다.
3. 3의 n승을 약수로 가질 때 n이 클수록 왼쪽에 위치한다.
4. 같은 지수를 가지는 수 중에서 가장 작은 수가 x가 된다.
5. x를 시작으로 법칙대로 수를 A 리스트에 삽입한다.

처음에 생각할 때에는 한 노드에서 2 가지를 모두 탐색한 후 다시 되돌아와서 다른 방향으로 가야 될거라 생각했다.

다른 사람들의 풀이에는 재귀함수를 사용한 경우도 많아 보였다. 나는 x를 찾은 후 문제의 알고리즘대로 A 수열을 만들었는데 다른 사람의 코드에서는 이차원 리스트와 lambda를 사용해서 정렬을 하기도 했다.

n = int(input())
b = list(map(int, input().split()))

a = []

for num in b:
    can3 = 0
    num_origin = num
    while True:
        if num % 3 == 0:
            can3 += 1
            num //= 3
        else:
            break
    a.append([can3, num_origin])

a.sort(key= lambda x: (-x[0], x[1]))
for i in range(n):
    print(a[i][1], end=' ')

이 코드가 훨씬 간결해보인다. key = lambda x: (-x[0], x[1])로 정렬한 것은 -x[0] 즉 3으로 나누어지는 수가 큰 것으로 정렬한 후 원래 값이 작은 순으로 정렬한다. 정렬의 기본 순서는 오름차순이므로 -x[0]를 기준으로 하면 큰 수가 앞으로 온다.

반복문을 진행하면서 모든 과정을 끝내는 것을 연습해야 된다고 생각이 들었다.