파이썬 백준 알고리즘 - 3진법 뒤집기 풀이 해석

안녕하세요! 알고리즘을 사랑하는 여러분, 반갑습니다. 오늘은 "3진법 뒤집기" 문제를 다뤄보려고 합니다. 이 문제는 주어진 수를 3진법으로 변환하고, 그 결과를 다시 10진법으로 변환하는 문제입니다. 자, 그럼 문제를 자세히 살펴보겠습니다.

문제 내용

주어진 수를 3진법으로 변환하고, 그 결과를 다시 10진법으로 변환하여 출력하는 문제입니다.

문제 이해하기

주어진 수를 뒤에서부터 한 자리씩 가져와서 3진법 변환을 수행합니다. 변환하는 방법은 다음과 같습니다. 수의 자릿수를 0부터 세어서, 3으로 나눈 나머지에 가중치를 곱한 값을 계속 더해줍니다. 가중치는 1, 2, 4, 1, 2, 4, ...와 같이 반복됩니다. 이렇게 변환한 결과를 다시 10진법으로 변환하여 출력합니다.

풀이 코드

pythonCopy code
s = input()
answer = ''
ans = 0
count = 0
for i in range(len(s)-1, -1, -1):
    if count % 3 == 0:
        ans += int(s[i]) * 1
        count += 1
    elif count % 3 == 1:
        ans += int(s[i]) * 2
        count += 1
    elif count % 3 == 2:
        ans += int(s[i]) * 4
        answer += str(ans)
        ans = 0
        count = 0
if ans >= 0:
    answer += str(ans)
answer = answer[::-1]
print(int(answer))

풀이 방법

주어진 수를 문자열로 입력받습니다. 주어진 수를 뒤에서부터 한 자리씩 가져와서 3진법 변환을 수행합니다. 이때, 가중치를 사용하여 3진법 변환을 진행합니다. 가중치는 1, 2, 4, 1, 2, 4, ...와 같이 반복됩니다. 가중치를 적용하여 변환한 결과를 ans 변수에 더해주고, count 변수를 사용하여 가중치의 인덱스를 계속 추적합니다. count 변수의 값에 따라 가중치를 곱해주는 계산을 수행합니다. 변환한 결과를 answer 변수에 누적하여 저장하고, ans 변수와 count 변수를 초기화합니다. 마지막으로, 변환한 결과를 뒤집어서 10진법으로 변환한 값으로 출력합니다.

시간 복잡도

주어진 수의 길이를 N이라고 할 때, 입력을 한 번 순회하면서 3진법 변환을 수행하므로 시간 복잡도는 O(N)입니다. 따라서, 입력의 크기에 선형적으로 증가하는 효율적인 알고리즘이라고 할 수 있습니다.

 

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음