[Algorithm] 백준_16936번: 나3곱2

오늘의 문제는 🚀 백준 16936 나3곱2이다.

오 어려운데 라고 생각했는데 테스트 케이스를 잘 보니깐 금방 풀렸다. 룰루

테스트케이스 이해하기

곱하기2를 하거나 3으로 나누어 질 경우에 3으로 나눈값들이 뒤섞여서 input으로 입력된다.

그러면 그 숫자들의 순서들을 찾으면 된다! 틀린 경우는 존재 하지 않는다.

그래서 주어진 테스트 케이스만 저렇게 찬찬히 봤는데, 마지막에 오는 숫자만 나누기3, 곱하기2에 해당하는 숫자가 없는 걸 알아냈다!

알고리즘

1. start와 딕셔너리를 선언해준다. for문을 한번만 돌려고 딕셔너리를 사용해줬다!
2. 3으로 나누어지면 na3으로 값을 설정해주고, input값이 이전에 있고 딕셔너리에 없다면 딕셔너리에 추가해준다.
3. 2 곱하기도 마찬가지로 해준다.
4. na3과 kob2이 둘다 arr이 없는 경우가 마지막 숫자이다.
5. for 문들을 다 돌면서 위의 과정을 진행한다.
6. 딕셔너리 값들을 거꾸로 프린트하기 위해 재귀함수를 사용한다.

p.s 이전에 문제 풀때 배웠던 재귀함수를 사용해봤다. 익숙해져봐야지

정답코드

from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
start = 0
dict = defaultdict(list)

for i in range(n):
    #딕셔너리 값채우기
    na3= 0
    if arr[i]%3 == 0:
        na3 = arr[i]//3
        if na3 in arr and not na3 in dict:
            dict[na3] = arr[i]
    kob2 = arr[i]*2

    if kob2 in arr and not kob2 in dict:
        dict[kob2] = arr[i]

    #처음 시작값 찾기
    if not na3 in arr and not kob2 in arr:
        start = arr[i]


#딕셔너리에서 거꾸로 프린트하기
def printtool(llen, n, m):
    if llen != n:
        printtool(llen,n+1, dict[m])
    print(m, end=" ")

printtool(n,1,start)

🚀Reference: 백준 16936 - 나3곱2