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

---

소스코드

N = int(input())

seq = list(map(int, input().split()))

ans = []

for i in seq:

    can3 = 0

    num = i

    while True:

        if i % 3 == 0:

            can3 += 1

            i //= 3

        else:

            break

    ans.append([can3, num])

ans.sort(key= lambda x: (-x[0], x[1]))

for i in range(N):

    print(ans[i][1], end=' ')

---

알고리즘

list에 있는 숫자들이 모두 2와 3으로 이루어져 있는것을 보고 소인수 분해를 해봤다.

4 = 2^2

8 = 2^3

6 = 2      *  3

3 =            3

12 = 2^2 * 3

9 =            3^2

그리고 출력 결과를 보니깐 3을 인수로 많이 갖고 있는 애는 앞으로 가고 뒤로 갈 수록 2를 인수로 가진 애들이 있는 것을 볼 수 있었다.

(즉, 3을 인수로 갖고 있는 애들 중 2가 많은 애들이 뒤로 가는것이다)

두 번 정렬할 필요 없이 큰 수가 뒤로 가기 때문에 3을 인수로 가진 애들 위주로 정렬하여 문제를 풀 수 있었다.