[Algorithm] 문제풀이 - 해시-4

2. 전화번호 목록

• 전화 번호를 담은 배열 phone_book이 solution 함수의 매개 변수로 주어질 때,
• 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false 그렇지 않으면 true를 리턴

입출력

• 입력 : 전화 번호를 담은 배열 phone_book
• 출력 : 접두어인 경우가 있으면 false 그렇지 않으면 true

제한 사항

• phone_book의 길이는 1이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하 입니다.
  • 같은 전화번호가 중복 해서 들어있지 않습니다.

Brute force

public boolean solution(String[] phone_book) {

      for (int i = 0; i < phone_book.length; i++) {
          for (int j = 0; j < phone_book.length; j++) {
              if (i == j) continue;
              String shorter = phone_book[i].length() <= phone_book[j].length() ? phone_book[i] : phone_book[j];
              String longer = phone_book[i].length() > phone_book[j].length() ? phone_book[i] : phone_book[j];
              if (longer.startsWith(shorter)) {
                  return false;
              }
          }
      }

      return true;
  }

실행 결과

정확성  테스트
테스트 1 〉	통과 (0.02ms, 77.2MB)
테스트 2 〉	통과 (0.04ms, 70MB)
테스트 3 〉	통과 (0.02ms, 74.8MB)
테스트 4 〉	통과 (0.02ms, 70.2MB)
테스트 5 〉	통과 (0.03ms, 75.4MB)
테스트 6 〉	통과 (0.02ms, 79.4MB)
테스트 7 〉	통과 (0.02ms, 66.3MB)
테스트 8 〉	통과 (0.02ms, 76.7MB)
테스트 9 〉	통과 (0.02ms, 72.8MB)
테스트 10 〉	통과 (0.01ms, 75.5MB)
테스트 11 〉	통과 (0.02ms, 82.4MB)
테스트 12 〉	통과 (0.02ms, 74.3MB)
테스트 13 〉	통과 (0.02ms, 72.2MB)
테스트 14 〉	통과 (24.44ms, 79.6MB)
테스트 15 〉	통과 (22.02ms, 87.1MB)
테스트 16 〉	통과 (28.23ms, 85.8MB)
테스트 17 〉	통과 (58.80ms, 82MB)
테스트 18 〉	통과 (80.43ms, 84.2MB)
테스트 19 〉	통과 (38.43ms, 89.8MB)
테스트 20 〉	통과 (108.51ms, 79.8MB)
효율성  테스트
테스트 1 〉	통과 (0.03ms, 55.3MB)
테스트 2 〉	통과 (0.03ms, 55.5MB)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)

해시이용

["12","123","1235","567","88"]
-> 제일 작은 길이로 전부 substring
["12", "12", "12", "56", "88"]
 -> Hash
["12", "56", "88"]
-> 원본 length = hashSet 같으면? true, false

["12","345","3456","567","88"]
-> ["12","34","34","56","88"] ==> 안나옴
-> ["345","345","567","88"]

["12","345","3456","567","88"]
1. sort
["12","88","345","567","3456"]
2. 길이별 hash
작은 길이 기준으로 모두 비교?
[ 
  [ X  , {"12"} ],
  [ X  , {"88"} ],
  [ X, {"34"}, {"345"} ],
  [ X, {"56"}, {"567"} ],
  [ X, {"34"}, {"345"}, {"3456"} ],
3. 
12, 88 없음
다음 길이 3기준
345 

3. 위장

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return

입출력

• 입력 : [의상의 이름, 의상의 종류] 의 배열
• 출력 : 서로 다른 옷의 조합의 수

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 ‘_’ 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.