[BOJ] 5052 전화번호 목록

전화번호 목록

풀이

• 시초에, 런타임에러에.. 생각보다 애먹었다..

• 처음 풀이는 그냥 단순하게 생각한게,전화번호 각각을 Integer로 배열에 저장하고, 배열을 정렬하면 가장 작은 숫자부터 다른 전화번호들과 비교할 수 있으니까 정렬했고, 기준으로 보고 있는 숫자의 자릿수를 구한 다음, 비교할 전화번호들을 그 자릿수까지만 잘라서 비교했다. 그니까 예를 들면 , 지금 기준인 전화번호가 "911" 이고, 내가 비교할 전화번호가 "91123231" 이면, 앞 세자리 "911" 만 잘라서 같은지 다른지를 비교했던 것이다.

  🙅‍♀️ 틀린 풀이

  import java.util.*;
  import java.io.*;
  public class Main {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int T = Integer.parseInt(br.readLine());
          for(int i=0;i<T;i++){
              int N = Integer.parseInt(br.readLine());    //전화번호 갯수 n
              boolean corresp = true;
              int[] numbers = new int[N];
              for(int j=0;j<N;j++){
                  numbers[j] = Integer.parseInt(br.readLine());
              }
              Arrays.sort(numbers);
              for(int j=0;j<N;j++){
                  int now = numbers[j];
                  //now 자릿수에 따라서
                  int cnt = 0;    //자릿수
                  while(now>0){
                      now = now/10;
                      cnt++;
                  }
                  //나 말고 다른 애들이랑 비교
                  for(int k=j+1;k<N;k++){
                      String next = String.valueOf(numbers[k]).substring(0,cnt);
                      if(next.equals(String.valueOf(numbers[j]))){
                          corresp = false;
                          break;
                      }
                  }
                  if(!corresp) break;
              }
              if(!corresp) System.out.println("NO");
              else System.out.println("YES");
          }
      }
  }

  이랬더니 "런타임에러"가 뜬 것이다. NumberFormat Exception이 떴는데, 확실한건 잘 모르겠지만 Integer.parseInt 이 부분에서 문제가 생겼을 수도 있겠다.
  다만 생각했던 예외는, Integer.parseInt(br.readLine() 을 할 때, "010"을 Integer 변환하는 경우 "10"으로 변환된다는 것이었다.
  그래서 아! 틀렸군...하고 다른 풀이를 생각했다.

• 다음 생각한 풀이는 String.substring 을 이용한 방법. 아니 단순하게 생각해보니까 그냥 전화번호 입력받은대로 String으로 저장하고, String 길이 잰다음에 내가 비교할 전화번호를 잘라서 비교하면 되잖아? 라고 갑자기 생각이 들었다.

  🙅‍♀️ 틀린 풀이

  import java.util.*;
  import java.io.*;
  public class Main {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int T = Integer.parseInt(br.readLine());
          for(int i=0;i<T;i++){
              int N = Integer.parseInt(br.readLine());    //전화번호 갯수 n
              boolean corresp = true;
              String[] numbers = new String[N];
              for(int j=0;j<N;j++){
                  numbers[j] = br.readLine();
              }
              for(int j=0;j<N;j++){
                  String now = numbers[j];
                  //now 자릿수에 따라서
                  int cnt = now.length();
                  //나 말고 다른 애들이랑 비교
                  for(int k=j+1;k<N;k++){
                      if(numbers[k].length()>=cnt){
                          String next = numbers[k].substring(0,cnt);
                          if(next.equals(numbers[j])){
                              corresp = false;
                              break;
                          }
                      }
                  }
                  if(!corresp) break;
              }
              if(!corresp) System.out.println("NO");
              else System.out.println("YES");
          }
      }
  }

  하지만 시초나셨음니다
  시초가 날 수밖에 없는.. 풀이같긴 하다. 이 코드를 짜면서 Arrays.sort(numbers) 를 하긴 했었는데, 난 "짧은 길이"로 정렬되어야해! 라는 생각에 매몰되어... 포인트를 보지 못했던 것이다.
  String 배열을 정렬하게 되면, 비슷한 문자열끼리 가까이 있게 된다. 이게 무슨 말이냐
  배열에 ["1234","5423","12345",...] 이렇게 있다고 하자. 이걸 정렬하면 ["1234","12345","5423"...] 이렇게 정렬된다는 것이다! 이게 정답 코드로 가는 키포인트였다.

• 정답 코드는.. 생각보다 간단했다. String.startsWith 함수만 알고 있었다면...

• 예전에 endsWith 함수 몰라서 헤매었던 기억이 새록새록 ...

  🙆‍♀️ 정답 코드

  import java.util.*;
  import java.io.*;
  public class Main {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int T = Integer.parseInt(br.readLine());
          for(int i=0;i<T;i++){
              int N = Integer.parseInt(br.readLine());    //전화번호 갯수 n
              boolean corresp = true;
              String[] numbers = new String[N];
              for(int j=0;j<N;j++){
                  numbers[j] = br.readLine();
              }
              Arrays.sort(numbers);
              for(int j=0;j<N-1;j++){
                  if(numbers[j+1].startsWith(numbers[j])){
                      corresp = false;
                      break;
                  }
              }
              if(!corresp) System.out.println("NO");
              else System.out.println("YES");
          }
      }
  }

  아까 봤던 것처럼, 전화번호 배열을 정렬해주면 비슷한 애들끼리 가까이 있게 된다.
  때문에, for문 하나로, 나랑 내 뒤에 있는 전화번호만 비교해주면 되는 것이다. 내 뒤에 있는 전화번호가 나로 시작하니? 만 물어보면 되는 것.

startsWith!! 기억합시다. 문자열은 정말로 메소드와의 싸움 아닐까...