[baekjoon] 21275 폰 호석만 - 진법 변환

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

오늘의 문제는

• 수학
• 브루트포스 알고리즘

이다.

 

진법 변환에 대한 문제다.

 

처음 풀이는 아래와 같다.

import java.io.*;
import java.util.*;

public class Main {
  public static String str1, str2;
  public static Map<Character, Integer> map;

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    input(br);
    pro();
  }

  static void pro()  {
    int count = 0;
    int A = 0;
    int B = 0;
    long X =0;
    for(int a=2; a<37 ; a++){
      for(int b=2; b<37 ; b++){
        if(a==b) continue;
        long x1 = ch(str1, a);
        long x2 = ch(str2, b);
        if(x1 == -1 || x2 == -1 || x1 != x2) continue;
        X = x1;
        A = a;
        B = b;
        count++;
        if(count > 1) {
          System.out.println("Multiple");
          return;
        }
      }
    }
    if(count == 0){
      System.out.println("Impossible");
      return;
    }

    System.out.println(X + " " + A + " " + B);
  }

  static long ch(String str, int n) {
    long res = 0;
    int len = str.length();
    for(int i=0; i< len; i++){
      char c = str.charAt(i);
      int k = map.get(c);
      if(k >= n) return -1;
      res += (long)Math.pow(n, len - 1 - i) * (long)k;
    }
    return res;
  }

  static void input(BufferedReader br) throws Exception {
    StringTokenizer st = new StringTokenizer(br.readLine());
    str1 = st.nextToken();
    str2 = st.nextToken();
    map = new HashMap();
    char c = '0';
    for(int i=0 ; i< 10 ; i++){
      map.put(c++, i);
    }
    c = 'a';
    for(int i=10 ; i< 36 ; i++){
      map.put(c++, i);
    }
  }

}

여기서 java 제공 라이브러리를 활용하면 변환 메서드를 아래처럼 변경할 수 있다.

static long ch(String str, int n) {
    try{
        return Integer.parseInt(str,n);
    }catch(NumberFormatException e){
        return -1;
    }
}

 

사실 중간에 -1확인 하는 부분도 둘 중 하나만 체크해주면 알아서 걸러진다!

if(x1 == -1 || x1 != x2) continue;

 

최종 코드

import java.io.*;
import java.util.*;

public class Main {
  public static String str1, str2;

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    input(br);
    pro();
  }

  static void pro()  {
    int count = 0;
    int A = 0;
    int B = 0;
    long X =0;
    for(int a=2; a<37 ; a++){
      for(int b=2; b<37 ; b++){
        if(a==b) continue;
        long x1 = ch(str1, a);
        long x2 = ch(str2, b);
        if(x1 == -1 || x1 != x2) continue;
        X = x1;
        A = a;
        B = b;
        count++;
        if(count > 1) {
          System.out.println("Multiple");
          return;
        }
      }
    }
    if(count == 0){
      System.out.println("Impossible");
      return;
    }

    System.out.println(X + " " + A + " " + B);
  }

  static long ch(String str, int n) {
    try{
      return Long.parseLong(str,n);
    }catch(NumberFormatException e){
      return -1;
    }
  }

  static void input(BufferedReader br) throws Exception {
    StringTokenizer st = new StringTokenizer(br.readLine());
    str1 = st.nextToken();
    str2 = st.nextToken();
  }

}

근데 이상한 점이 있다..

문제의 범위가

• 0 ≤ X < 2^63

인데 int를 해도 통과한다! 문제 오류 발견인가?

아니면 

길이는 최대 70이면 int 범위를 넘어서지 못하는걸까? 그건아니다..

String s = "";
for(int i=0 ; i<70 ; i++){
  s += "z";
}
//    System.out.println(Integer.parseInt(s, 36));
//    System.out.println(Long.parseLong(s, 36));
System.out.println(ch(s,36)); // -4662340520662534092

// 메서드

static long ch(String str, int n) {
long res = 0;
int len = str.length();
for(int i=0; i< len; i++){
  char c = str.charAt(i);
  int k = map.get(c);
  if(k >= n) return -1;
  res += (long)Math.pow(n, len - 1 - i) * (long)k;
}
return res;
}

여기서 결과가 -4662340520662534092 가 나오므로 그건아니다.

 

테스트케이스가 int범위를 벗어나지 않는 듯 하다.