[Java] 백준 1025 제곱수 찾기 - 골드5

 

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

1025번: 제곱수 찾기

 

규칙도 전혀 없고, 계산하다 중간에 멈추고 가지치기할 만한 규칙도 보이지 않는다.

그냥 다 구해서 완전제곱수를 찾아 최대인지 비교하는 게 최선일 것 같다. 

 

최대 9x9 배열이고 -> 81

step은 최대 -8부터 8까지 될 수 있음 -> 최대 1~8

81 x 8 x 8 = 5184

5184 정도의 경우의 수면... 다 비교하는 게 나쁘지 않을 지도 모르겠다.

 

완전제곱수인지 판별하는 방법은 sqrt를 한 정수를 제곱했을 때 해당 값과 같은지 비교하는 식으로 구현하려고 한다. 

등차수열은 for문을 중첩해서 구현하면 될 것 같다. 

 

 

 

내 풀이(브루트포스)

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

public class Main {

  public static void main(String args[]) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st= new StringTokenizer(br.readLine());
    int result = -1;
    int resultLen = -1;

    int rowLen = Integer.parseInt(st.nextToken());
    int colLen = Integer.parseInt(st.nextToken());
    int[][] arr = new int[rowLen][colLen];

    for (int i=0; i<rowLen; i++) {
      String tmp = br.readLine();
      for (int j =0; j<colLen; j++)
        arr[i][j] = Integer.parseInt(String.valueOf(tmp.charAt(j)));
    }

    //계산
    for (int i =0; i<rowLen; i++) {
      for (int j =0; j<colLen; j++) {
        for (int stepRow = -(rowLen-1); stepRow <= (rowLen-1); stepRow++) {
          for (int stepCol = -(colLen-1); stepCol <= (colLen-1); stepCol++) {
            if (stepRow == 0 && stepCol == 0)
              continue;

            StringBuffer sb = new StringBuffer();
            sb.append(arr[i][j]);

            int cnt = 1;
            while (true) {
              int row = i+stepRow*cnt;
              int col = j+stepCol*cnt;

              if (row < 0 || rowLen <= row || col < 0 || colLen <= col)
                break;

              sb.append(arr[row][col]);
              cnt++;
            }

            String tmpR = sb.toString();

            for (int t= 1; t<tmpR.length(); t++) {
              String subString = tmpR.substring(0, t+1);
              int tmp = Integer.parseInt(subString);

              //가지치기
              if (result != -1 && resultLen > (int)(Math.log10(tmp) + 1))
                continue;

              if (isResult(tmp)) {
                if (result < tmp) {
                  resultLen = (int)(Math.log10(tmp) + 1);
                  result = tmp;
                }
              }
            }
          }
        }
      }
    }

    if (result == -1 || resultLen == 1) {
      for (int i =0; i<rowLen; i++) {
        for (int j = 0; j < colLen; j++) {
          int tmp = arr[i][j];
          if (isResult(tmp)) {
            if (result < tmp)
              result = tmp;
          }
        }
      }
    }
    
    System.out.println(result);
  }

  private static boolean isResult(int num) {
    if (num == 1 || num == 0)
      return true;

    int sqrtNum = (int)Math.sqrt(num);
    if (Math.pow(sqrtNum, 2) == num)
      return true;

    return false;
  }
}

• for문 2개: 모든 칸 NxM에 대해 동작한다
• 다음 for문 2개: row의 등차수열 step과 col의 등차수열 step을 지정해준다. step의 범위는 -(rowLen-1) ~ (rowLen-1) 이다
  • 만약 row의 step과 col의 step이 둘 다 0이면 움직이지 않기 때문에 제외해준다
• 한 칸에서 step으로 갈 수 있는 모든 경우를 while문으로 계산하여 StringBuffer에 넣는다
  • 만약 칸을 벗어날 경우 while문을 빠져나온다
• StringBuffer에 저장된 문자열은 1이상의 문자열일건데, 여기서도 for문을 한 번 더 돌려서 숫자가 완전제곱수인지 판별한다
  • 예시를 들면 "1234"문자열이 저장되었을 경우 "12", "123", "1234" 에 대해 완전제곱수인지 판별한다
  • 한 자리 수인 경우는 나올 확률도 적고, 포함시키면 시간이 초과될 수 있기 때문에 마지막으로 빼줬다 (ex. "1")
  • 판별은 (int)(Math.log10(tmp) + 1)을 사용한다
• 만약 완전제곱수인 답을 하나 찾았을 경우, substring의 길이가 답보다 작은 경우는 완전제곱수인지 판별하지 않고 가지치기 해준다

 

 

• 정수의 자릿수 판별을 제대로 안해서 4번틀림ㅠㅠ

 

 

참고한 질문게시판

https://www.acmicpc.net/board/view/106860

• 이 문제 덕분에 정수 자릿수를 제대로 판별하지 못했다는 걸 알아냄

 

 

참고 블로그

https://velog.io/@skditjsdud35/JAVA-int%ED%98%95-%EC%88%AB%EC%9E%90%EC%9D%98-%EC%9E%90%EB%A6%BF%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-780zkxgp

• int형의 자릿수 구하기
• 00000이 5자리로 인식되어 가지치기할 때 같이 쳐지는 문제를 해결함!

 

 

 

다른 풀이를 보고 느낀점

• 제 풀이에서 substring으로 구하지 않고 while문 안에서 그때그때 추가될 때마다 판별을 할 수도 있었겠다는 생각이 듭니다
  
  • 이러면 코드길이 더 줄었을듯
• 1일 때 굳이 안써줘도 될듯
• 완전제곱수 판별 다른방법: Math.abs(Math.sqrt(t) - (int)Math.sqrt(t)) < 1e-10