[백준] 11005 : 진법 변환2 (Stack활용하기, String으로 변환) - JAVA

백준 단계별 문제풀이 8단계 (일반수학)

https://www.acmicpc.net/problem/11005 

11005번: 진법 변환 2

 

# 문제

10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오.

10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.

A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35

 

# 예제

입력

60466175 36

 

출력

ZZZZZ

 

# 필요개념

해당 문제를 풀기 위해서는 진법 변환의 원리를 알아야 한다. 나는 원리를 생각하다가 스택을 사용해야겠다고 생각했다.

1. 진법 변환 원리
2. Stack사용법

 

✅ 진법 변환 원리

 

늘 진법계산기를 써왔고, 8진법, 2진법 등 대표적인 진법 변환만 알고있었기 때문에 이 문제를 풀 때 겁을 먹었었다. 진법 변환을 찾아보니 생각보다 간단하다는 것을 알 수 있었다.

 

진법을 변환할 때에는 나누기를 해서 몫과 나머지를 활용한다.

예를들어, 100을 8진법으로 나타낸다고 하면,

 

100 나누기 8 -> 몫 : 12, 나머지 : 4 가 된다. 이때 몫을 다시 8로 나누는 과정을 반복한다.

12 나누기 8 -> 몫 : 1, 나머지 4 가 된다. 

100을 8진법으로 변환

 

따라서 몫이 원하는 진법보다 작지 않으면 나머지를 계속 스택에 넣어주고, 몫이 진법보다 작아지면 몫을 마지막에 스택에 넣어주었다. 그렇다면 스택은 어떻게 사용해야할까 ?

 

 

✅ 스택 활용하기

 

스택은 정말 많이 사용되는 자료구조 중 하나이다. 자세한 설명은 아래 게시글에 작성해두었다.

https://wanna-developer02.tistory.com/22 

[Data Structure] CHAP 5. Stack and Queues (스택 & 큐) - C언어 ver.

 

자바에는 스택이 구현되어있기 때문에, 꺼내서 사용하기만 하면 된다! 스택의 메소드들만 가볍게 살펴보자.

 

push(T t)

데이터를 스택에 추가하고, 해당 값을 반환한다. 아래 코드는 자바에 구현되어있는 push 메소드 코드이다.

    public E push(E item) {
        addElement(item);

        return item;
    }

 

peek()

스택의 마지막 요소 즉, 제일 최근에 넣은 요소를 확인할 수 있게 해주는 메소드이다. 스택에 변화를 주지 않는다는 특징이 있으며 만약, 스택이 비어있을 떄 peek() 메서드를 호출하면 NoSuchElementException 예외가 발생한다.

아래 코드는 자바에 구현되어있는 peek 메소드 코드이다.

public synchronized E peek() {
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

 

pop()

스택에 넣은 가장 최근 요소를 반환한다. 반환하면 해당 요소는 삭제된다. 아래 코드는 자바에 구현되어있는 pop 메소드 코드이다.

public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

 

empty()

스택이 비어있는지의 여부를 true, false로 반환한다.

public boolean empty() {
    return size() == 0;
}

 

search()

메서드의 인자를 스택에서 검색하여 해당 위치를 반환하고, 인자가 여러 개일 경우 마지막 위치를 반환한다. 여기서 위치는 인덱스가 아닌 빠져나오는 순서를 뜻한다. 만약 찾는 값이 스택에 없다면  -1을 반환한다.

public synchronized int search(Object o) {
    int i = lastIndexOf(o);

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}

 

기본적인 메소드들은 알아두는 것이 좋을 거 같다.

스택에는 객체가 인자로 들어가기 때문에 char형, int형을 넣으려면 Character형, Integer형으로 박싱해주어야 한다. 나는 String형의 인자를 사용할 예정이었어서 스택에 String형으로 타입을 바꾸어 넣어주었다.  

 

int와 char을 스트링으로 바꿀 때에는 String.valueOf(int a (char c)) 메소드를 사용해주면 된다.

 

# Code

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        
        Stack<String> stk = new Stack<>();
        
        int val, rest = 0;
        
        while (true) {
            val = A / B;
            rest = A % B;
            
            if (rest > 9) stk.push(String.valueOf((char)(rest + 55)));
            else stk.push(String.valueOf(rest));
            
            if (val < B) {
                if (val > 9) stk.push(String.valueOf((char)(val + 55)));
                else if (val != 0) stk.push(String.valueOf(val));
                break;
            }
            A = val;
        }
        
        while (!stk.isEmpty()) {
            System.out.print(stk.pop());
        }

    }
}

 

마지막 value가 0일때는 출력을 하지 않아야하므로 val != 0 조건을 추가로 명시하였다.

# 결과