[Programmers] Lv.1 | 3진법 뒤집기 | Java

3진법 뒤집기 풀이 | 시간복잡도 O(logN) 최적화 방법

https://school.programmers.co.kr/learn/courses/30/lessons/68935

1. 문제 설명

자연수 n이 주어짐

해야 하는 작업은 총 3단계

• n을 3진법으로 변환
• 숫자를 뒤집기
• 다시 10진수로 변환

예시

45
→ 1200(3진수)
→ 0021(뒤집기)
→ 7(10진수)

• 단순 문자열 문제처럼 보이지만 실제로는 "진법 변환 원리" 이해가 핵심인 문제

---

2. 핵심 아이디어

이 문제는 문자열로 풀 수 있음

하지만 더 빠른 방법 존재

 

핵심 포인트

3으로 나눈 나머지 순서
=
이미 뒤집힌 3진수 순서

• StringBuilder 생성
• reverse 수행
• 문자열 파싱

등의 과정 필요 없이, 바로 10진수 계산 가능

---

3. 풀이 방법 비교

방법 1. 문자열 기반 풀이

흐름

• 3진수 문자열 생성
• reverse 수행
• 다시 10진수 변환

장점

• 직관적 이해 가능

단점

• 문자열 생성 비용 발생
• reverse 추가 연산 발생
• char 처리 필요

시간복잡도

• O(logN)

가능은 하지만 최적은 아님

---

방법 2. 나머지 즉시 누적 계산 방식

흐름

• n % 3 으로 뒤집힌 숫자 추출
• 바로 10진수 계산 수행

장점

• 문자열 생성 없음
• reverse 없음
• 메모리 사용 최소화
• 가장 빠른 방식

시간복잡도

• O(logN)

공간복잡도

• O(1)

---

4. 최적 풀이 선택 이유

이 문제의 핵심은 "뒤집힌 3진수 만들기"

그런데 3으로 계속 나누면 나머지가 이미 뒤집힌 순서로 나옴

 

예시

45 % 3 = 0
15 % 3 = 0
5 % 3 = 2
1 % 3 = 1

얻는 순서

0 → 0 → 2 → 1

• 즉 이미 0021
• 따라서 reverse 자체가 필요 없음
• 실전 코딩테스트에서는 이런 "중간 과정 제거" 최적화가 매우 중요

---

5. 가장 중요한 핵심 원리

많이 헷갈리는 부분

convertedDecimal = convertedDecimal * 3 + remainder;

• 왜 * 3 하는지 이해 필요

---

10진수에서 먼저 생각

숫자 21 만드는 과정

2
→ 2 * 10 + 1
→ 21

왜 10 곱하는가

10진수 자리 하나 왼쪽 이동 때문

2
↓
20
↓
21

---

3진수도 완전히 동일한 원리

3진수에서는 10 대신 3 사용

예시

21(3진수)

계산

2 * 3 + 1
= 7

실제 계산

(2 × 3¹) + (1 × 3⁰)
= 6 + 1
= 7

현재값 * 진법 + 새숫자

= "자리 하나 추가" 의미

---

6. 실제 코드 흐름으로 이해

예시

n = 45

---

1단계

45 % 3 = 0

convertedDecimal = 0 * 3 + 0
                 = 0

현재 상태

0

---

2단계

15 % 3 = 0

convertedDecimal = 0 * 3 + 0
                 = 0

현재 상태

00

---

3단계

5 % 3 = 2

convertedDecimal = 0 * 3 + 2
                 = 2

현재 상태

002

---

4단계

1 % 3 = 1

convertedDecimal = 2 * 3 + 1
                 = 7

의미

기존 숫자 : 2

여기에 숫자 1 추가

21(3진수)

---

7. Java 코드

class Solution {

    public int solution(int n) {

        // 뒤집힌 3진수를
        // 다시 10진수로 변환한 최종 결과 저장 변수
        int convertedDecimal = 0;

        // n이 0이 될 때까지 반복
        // 3으로 계속 나누면서
        // 뒤집힌 3진수 숫자를 순서대로 꺼내는 과정
        while (n > 0) {

            // 현재 3진수 자리값 추출
            // 이 값이 이미 뒤집힌 순서로 나오게 됨
            int remainder = n % 3;

            // 핵심 로직
            //
            // 기존 숫자를 3진수 기준 한 칸 왼쪽 이동
            // 이후 새 숫자 추가 과정
            //
            // 예시
            //
            // 기존 : 2
            // 새 숫자 : 1
            //
            // 2 * 3 + 1
            // = 7
            //
            // 즉 3진수 "21" 생성 의미
            convertedDecimal = convertedDecimal * 3 + remainder;

            // 다음 자리 계산을 위해 3으로 나눔
            n /= 3;
        }

        // 최종 결과 반환
        return convertedDecimal;
    }
}

---

8. 시간복잡도 & 공간복잡도

시간복잡도

• O(log₃N)
• n을 3으로 계속 나누기 때문
• 최대 약 17번 반복 수준

공간복잡도

• O(1)
• 추가 문자열이나 배열 사용 없음

---

9. 최적화 포인트

• StringBuilder 제거
• reverse 제거
• 문자열 변환 제거
• char 처리 제거
• 추가 메모리 제거
• 한 번의 반복으로 즉시 계산

실전 코딩테스트에서는 이런 방식이 가장 안정적

특히

• 진법 변환
• 자리수 계산
• 숫자 뒤집기
• 비트 연산

문제에서 자주 사용 가능

---

10. 마무리 정리

이 문제 핵심은

현재값 * 진법 + 새숫자

원리 이해

 

이 개념 하나만 이해하면

• 2진수
• 8진수
• 16진수
• 문자열 숫자 변환

유형의 문제 쉽게 처리 가능

코딩테스트에서는 문자열보다 "숫자 자체 처리"가 훨씬 빠른 경우 많음

따라서

• 정말 문자열이 필요한가
• 중간 과정 제거 가능한가

먼저 확인하는 습관 중요