(프로그래머스) 전화번호 목록

문제

https://programmers.co.kr/learn/courses/30/lessons/42577

접근

솔직히 단순하게 전부 돌려가면서 비교하는 방법이 먼저 생각났는데, O(n^2)의 시간복잡도록 시간초과가 날 것 같아 다른 방법을 생각하게 되었다.

잘못된 접근

문자열 첫 글자에 대한, ArrayList 타입의 배열을 만들고 사전처럼 첫 번째 숫자를 통해 찾아가서 쭉 비교해보는 방법을 택하게 되었다.

코드

import java.util.*;

class Solution {
  public boolean solution(String[] phone_book) {
      boolean answer = true;
      
      ArrayList<String>[] dictionary = new ArrayList[10];
      
      for (int i = 0; i < dictionary.length; i++) {
          dictionary[i] = new ArrayList();
      }
      
      for (int i = 0; i < phone_book.length; i++) {
          String book = phone_book[i];
          int start = book.charAt(0) - '0';
                                              
          for (int j = 0; j < dictionary[start].size(); j++) {
              String str = dictionary[start].get(j);
                              
              String target;
              if (book.length() > str.length()) {
                  // 들어오는 문자열이 더 길 경우
                  target = book.substring(0, str.length());
                                      
                  if (target.equals(str)) {
                      answer = false;
                      return answer;
                  }
              } else {
                  // 기존 리스트의 문자열이 더 길 경우
                  target = str.substring(0, book.length());
                                      
                  if (target.equals(book)) {
                      answer = false;
                      return answer;
                  }
              }
          }
          
          dictionary[start].add(book);
      }
      
      return answer;
  }
}

정확성 측면에서는 모든 테스트케이스가 성공했지만 효율성 측면에서는 몇 개의 테스트케이스에서 시간초과가 났다. 생각해보니 입력 문자열 배열의 각 문자열의 맨 앞에 오는 숫자가 전부 같으면 O(n^2)로 시간 복잡도가 같은 것이다. 아니, 시간 복잡도만 같지 위에서 완전 처음에 떠올렸던 방법보다 더 안좋은 경우가 발생할 것이다.

개선된 접근

해시맵을 이용한 방법이다.

1. 입력값으로 주어진 문자열 배열을 각 문자열의 크기 비오름차순으로 정렬한다.
2. 가장 긴 문자열에 대해서는 앞에서부터 누적해서 쪼개면서 해시맵에 넣어준다.
   ex) "123456"인 경우
   "1", "12", "123", "1234", "12345", "123456"
3. 문자열 하나하나 비교하면서 현재 해시맵에 본인과 키값이 일치하는 원소가 있는지 확인하고 없으면 2의 과정을 거친다.
   (문자열 본인은 적어도 해시맵에 들어있는 문자열들 중 가장 긴 녀석보다 길이가 짧거나 같다는게 보장된 상태기 때문이다.)

접근 계기

제한 사항이 다음과 같을 때 이 방법을 사용하면 최악의 경우 1000000 * 20 * (배열 정렬하는데 걸리는 시간) 정도로 위의 방법의 최악의 경우(1000000 * 1000000) 보다는 훨씬 낫지 않을까 생각하였다.

코드

import java.util.*;
class MyComparator implements Comparator<String> {
  @Override
  public int compare(String s1, String s2) {
      int l1 = s1.length();
      int l2 = s2.length();
      
      return l2 - l1;
  }
}


class Solution {
  public boolean solution(String[] phone_book) {
      boolean answer = true;
      
      Map<String, Integer> map = new HashMap<>();
      
      Arrays.sort(phone_book, new MyComparator());
      
      for (int i = 0; i < phone_book.length; i++) {
          String book = phone_book[i];
          
          if (i > 0 && map.containsKey(book)) {
              answer = false;
              break;
          }
          
          for (int j = 0; j < book.length(); j++) {
              map.put(book.substring(0, j + 1), 0);
          }
      }
      
      return answer;
  }
}