백준 11005번: 진법 변환 2
10진법으로 주어진 수 N을 B진법으로 변환하는 문제입니다. 10진법 수를 다른 진법으로 변환하는 고전적인 알고리즘인 '나머지 연산의 반복'과정을 정확하게 구현하는 것이 핵심입니다.
✅ 문제 개요
| 항목 | 내용 |
|---|---|
| 문제 번호 | 11005번 - 진법 변환 2 |
| 난이도 | 브론즈 1 |
| 핵심 알고리즘 | 수학, 구현 |
✅ 문제 설명 요약
- 입력: 첫째 줄에 10진법 수
N(1 ≤ N ≤ 1,000,000,000)과 진법B(2 ≤ B ≤ 36)가 주어집니다. - 출력:
N을B진법으로 변환한 결과를 출력합니다. - 규칙:
- B진법에서 10~35에 해당하는 값은 알파벳 대문자 'A'부터 'Z'로 표현합니다.
✅ 풀이 전략
10진법 수를 다른 진법으로 변환하는 표준적인 방법은, 주어진 수를 몫이 0이 될 때까지 계속해서 해당 진법으로 나누고, 그 나머지를 기록하는 것입니다.
1️⃣ 핵심 원리: 나머지 연산의 반복
- 어떤 10진수 N을 B진법으로 바꾸려면, N을 B로 나눈 나머지가 가장 낮은 자리의 숫자가 됩니다.
- 그 후, N을 B로 나눈 몫을 새로운 N으로 삼아 이 과정을 반복합니다.
- 이 과정에서 나오는 나머지들을 역순으로 이어 붙이면 B진법 표현이 완성됩니다.
2️⃣ 알고리즘 설계
- 결과를 저장할
StringBuilder를 생성합니다. while반복문을N이 0보다 클 동안 실행합니다.- 나머지 계산:
remainder = N % B를 통해 현재 자리의 값을 구합니다. - 문자 변환:
remainder를 B진법 문자로 변환합니다. (아래 3️⃣ 참고) - 문자 추가: 변환된 문자를
StringBuilder에 추가합니다. - 몫 계산:
N = N / B로 다음 계산을 위해 N을 업데이트합니다. - 결과 뒤집기:
while문이 끝나면StringBuilder에 저장된 문자열은 결과가 역순으로 담겨있으므로,.reverse()메소드를 이용해 뒤집어줍니다.
3️⃣ 숫자-문자 변환
- 나머지가 0~9인 경우와 10~35인 경우를 나누어 문자로 변환해야 합니다.
remainder < 10이면:(char)(remainder + '0')을 통해 '0'~'9' 문자로 변환remainder >= 10이면:(char)(remainder - 10 + 'A')을 통해 'A'~'Z' 문자로 변환
예시: 10진수 60466175를 36진법으로 변환
1. N=60466175: 60466175 % 36 = 35 ('Z'). N = 1679615. 결과: "Z"
2. N=1679615: 1679615 % 36 = 35 ('Z'). N = 46655. 결과: "ZZ"
3. N=46655: 46655 % 36 = 35 ('Z'). N = 1295. 결과: "ZZZ"
4. N=1295: 1295 % 36 = 35 ('Z'). N = 35. 결과: "ZZZZ"
5. N=35: 35 % 36 = 35 ('Z'). N = 0. 결과: "ZZZZZ"
6. N이 0이므로 반복 종료.
7. 결과 "ZZZZZ"를 뒤집어도 "ZZZZZ".
✅ Java 코드 예제
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
StringBuilder sb = new StringBuilder();
// N이 0보다 클 동안 반복
while (N > 0) {
int remainder = N % B;
// 나머지를 문자로 변환
if (remainder < 10) {
// 0-9 사이의 수
sb.append((char) (remainder + '0'));
} else {
// 10-35 사이의 수 (A-Z)
sb.append((char) (remainder - 10 + 'A'));
}
// N을 B로 나눈 몫으로 업데이트
N /= B;
}
// 결과가 역순이므로 뒤집어서 출력
bw.write(sb.reverse().toString());
bw.flush();
bw.close();
br.close();
}
}⚠️ 실전 주의사항
| 항목 | 설명 |
|---|---|
| 결과 뒤집기 | 이 알고리즘은 숫자를 가장 낮은 자리수(오른쪽)부터 생성하므로, 최종 결과를 반드시 뒤집어줘야 합니다. StringBuilder의 reverse() 메소드를 사용하면 매우 편리합니다. |
| Java 내장 함수 | 사실 이 문제는 Integer.toString(N, B).toUpperCase() 한 줄로 해결할 수 있습니다. 하지만 진법 변환 원리를 학습하기 위해 직접 구현하는 것이 중요합니다. |
| 문자 변환 로직 | 10 이상의 나머지를 'A'부터 시작하는 문자로 변환하는 (remainder - 10 + 'A') 로직을 정확히 구현해야 합니다. 아스키 코드의 원리를 이용하는 것입니다. |
| 자료형 | 입력 N이 최대 10억이므로 int 자료형으로 충분히 처리 가능합니다. |
📝 마무리 요약
✔️ 10진법을 B진법으로 변환하는 핵심은 몫이 0이 될 때까지 B로 나누고 그 나머지를 기록하는 것입니다.
✔️ 계산을 통해 얻어지는 나머지들은 B진법 수의 역순이므로, 마지막에 반드시 결과를 뒤집어 주어야 합니다.
✔️ StringBuilder를 사용하여 문자를 추가하고, 마지막에 .reverse() 메소드를 호출하는 것이 효율적입니다.
✔️ 10 이상의 나머지는 'A'부터 'Z'까지의 알파벳 대문자로 변환하는 과정을 거쳐야 합니다.
