[백준 - 2356번] 제곱 ㄷㄷ 수 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, 수학, 문자열

입력

양의 정수 $N$($1 \le N \le 10^{18}$)이 주어진다.

출력

 $N$ 이상의 가장 작은 제곱ㄷㄷ수를 출력한다.

풀이

가장 작은 제곱 ㄷㄷ수를 구해야 한다.

만약, N이 0, 1, 4, 9 중 하나라도 존재한다면, 2, 3, 5, 6, 7, 8 중 하나로 변환해 줘야 한다.

그런데 가장 작은 수를 구해야 하기 때문에 가능한 수중 가장 작은 값으로 변환하는 것이 최선의 선택이 된다. 예를 들어 0 -> 2, 1 -> 2, 4 -> 5, 9 -> 2와 같이 말이다.
(여기서 9는 다르게 처리할 필요가 있다. N 이상이기 때문에 앞 자리수의 +1을 해줘야 하는데 +1를 했을 때 앞 자리수도 다시 체크해 줘야 한다.)

또한 가장 작은 수를 구해야 하기 때문에 변환되는 지점 뒤로는 전부 2값을 가진다. 왜냐하면 0과 1은 정수 제곱근이 존재하기 때문이다. 예를 들어 770444라 할 때 772222가 최적해가 된다.

여기서 주의할 점은 5와 6이다. 25나 36인 경우 0, 1, 4, 9가 존재하지 않지만 부분 문자열인 5와 6의 제곱수가 된다.

5와 6이 들어가는 경우 그 제곱이 5와 6을 반드시 포함하기 때문이기도 하다. ex) 5 => 25, 15 => 225
반면에 2, 3, 7, 8은 그 제곱이 자신을 절대 포함하지 않는다.

그래서 5와 6은 앞의 문자를 연결해 가면서 제곱근이 있는지 확인해야 한다.
예를 들어 N이 676일 때 76을 확인하고, 676을 확인해야 한다. 676은 26의 제곱수다.

만약 제곱수가 존재한다면, 앞에서처럼 다음 값으로 변환해 줘야 한다. 5 -> 6, 6 -> 7
그리고 5 -> 6이 되는 경우는 다시 한번 체크를 해야 한다. 제곱수가 있을 수 있기 때문이다.

이 풀이는 상수 시간 복잡도를 가진다.

소스 코드

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

public class Main {
    static StringBuilder sb;
    static HashMap<Character, Character> map = new HashMap<>();
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      sb = new StringBuilder(br.readLine());
      map.put('0', '2');
      map.put('1', '2');
      map.put('4', '5');
      map.put('5', '6');
      map.put('6', '7');
      map.put('9', '9');
      
      answer(sb.length() - 1);
      System.out.println(sb.toString());
  }
  
  static void answer(int end) {
      for(int i=0; i<=end; i++) {
          if(sb.charAt(i) == '0' || sb.charAt(i) == '1' || sb.charAt(i) == '4' || sb.charAt(i) == '9') {
              sb.setCharAt(i, map.get(sb.charAt(i)));
              for(int j=i + 1; j<=end; j++) {
                  //나머지 다 2로 변환
                  sb.setCharAt(j, '2');
              }
              
              if(sb.charAt(i) == '9') {
                  //전에 숫자가 9일 때
                  
                  long next = Long.parseLong(sb.substring(0, i + 1)) + 1;
                  sb.replace(0, i+1, String.valueOf(next));
                  int nextEnd = i;
                  if(i + 1 != String.valueOf(next).length()) {
                      //자리수가 하나 늘어남 ex) 999 -> 1000
                      nextEnd += 1;
                  }
                  answer(nextEnd);
              } else if(sb.charAt(i) == '5') {
                  //다음값이 5가 됨
                  answer(i);
              }
              break;
          } else if(sb.charAt(i) == '5' || sb.charAt(i) == '6') {
              if(check(i)) {
                  //변환될 필요가 있음
                  sb.setCharAt(i, map.get(sb.charAt(i)));
                  for(int j=i+1; j<=end; j++) {
                      //나머지 다 2로 변환
                      sb.setCharAt(j, '2');
                  }
                  answer(i);
                  break;
              }
          }
      }
  }
  
  static boolean check(int end) {
      StringBuilder sb2 = new StringBuilder();
      sb2.append(sb.charAt(end));
      for(int i=end - 1; i>=0; i--) {
          sb2.insert(0, sb.charAt(i));
          if(isPerfectSquare(Long.parseLong(sb2.toString()))) {
              return true;
          }
      }
      return false;
  }
  
  static boolean isPerfectSquare(long num) {
      long sqrt = (long) Math.sqrt(num);
      return (sqrt * sqrt == num);
  }
}