[문제 풀이][Java] 백준 16953번 A→B

[문제 풀이][Java]  백준 16953번 A→B

* 학습 목적의 게시물이나 혹시 이 게시물이 문제가 된다면 언제든 연락 부탁드립니다.

* 더 나은 풀이를 위한 훈수, 조언 등 모두 환영합니다!

문 제 

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입 력

첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

출 력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

[문제 링크] 백준 16953번 A→B

---

문제 해석

1. 입력 값이 1 이상 10^9 이하의 정수로 int형으로 받을 수 있다.

2. 계산을 기록하는 count가 필요하다.

3. 몇 번 반복할지 입력값마다 다르니 while을 사용하여 반복한다.

해결 방법

1. 2로 나누어지는지 확인한다.

  가. 2로 나누어질 수 있다면, 2로 나눈다.

  나. 2로 나누어질 수 없다면, 그 수를 10으로 나누었을 때 나머지가 1이 되는지 확인한다.(마지막 자리수가 1인지 확인한다.)

2. 2로 나누어지지 않으면서, 10으로 나누었을 때가 1이 아니면 -1을 출력한다.

3. 위 과정을 반복하다가 B가 A보다 작아져도 -1을 출력한다.

4. 반복 중 B가 A와 같아지면 몇 번 계산했는지(count)에 1을 더하여 출력한다.

참고사항

* 추가 공부 필요내용 : int ↔ String

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B16953 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 입력받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int count = 1;
		
		while(b > a) { // 아래 과정 반복 중 b가 a 이하가 되면 탈출
			// 2의 배수인지 확인
			boolean isBMultipleOf2 = (b % 2 == 0);
			if(isBMultipleOf2) {	// 맞다면 2로 나눔
				b = b/2;
			} else {				// 아니면 문자열로 바꾸어 마지막 숫자가 1인지 확인
				if(b % 10 == 1) {
					String bStr = Integer.toString(b);
					char bLastChar = bStr.charAt(bStr.length() - 1);
					if(bLastChar == '1') {	// 마지막 숫자가 1이 맞으면 그 전까지 자름
						bStr = bStr.substring(0, bStr.length() - 1);
					}
					b = Integer.parseInt(bStr);
				} else {
					break;
				}
			}
			count++;			
		}
		
		if(b == a) {
			System.out.println(count);
		} else {
			System.out.println(-1);
		}
	}
}