[lv.2] 전화번호 목록

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

• 문제
  전화번호 배열 p가 있을때, 어떠한 번호가 다른 번호의 접두사인지의 여부 조사
  (p는 중복번호x, p의 길이 100만, 각 번호의 길이 1~20)

• 풀이1, 단순 for문
  1) 먼저 배열p를 정렬한다.
  2) 이때, 정렬한 p일 경우 1~9순 다음 길이에 따라 정렬되므로, 바로 다음 문자열만 비교하면 된다.

• 풀이2, HashSet 사용
  1) 모든 전화번호를 Set에 저장한다.
  2) 각 전화번호의 subString이 set에 있는지 확인한다.

• 소감
  BFS같은 특정 알고리즘만 편식한 필자에게 팩트펀치를 날린 첫 문제 되시겠다.
  이 문제가 아마 pccp의 1번이나 2번일거 같은데 여기서 50분을 소비했다. 그 뜻은...바로 광탈이란 것이다.
  앞으로는 편식하지 말자.
  아 그리고 문자열 함수중 str.matches(s+"(.*))이랑 str.startsWith(s)는 문자열 일부분이 포함되어있는지 검사하는 함수라 정말로 유용한 함수이니 이거 꼭 기억하자.

• 코드1 (단순 for문)

import java.util.*;

class Solution {
    public boolean solution(String[] p) {
        Arrays.sort(p);
        // 어차피 정렬은 했으니 바로 뒷번호만 확인한다.
        for(int i=1; i<p.length; i++){
            if(p[i].matches(p[i-1]+"(.*)")) return false;
            //if(p[i].startsWith(p[i-1])) return false;
        }
        return true;
    }
}

• 코드2 (해시 사용)

import java.util.*;

class Solution {
    public boolean solution(String[] p) {
        HashSet<String> set = new HashSet<>();
        for(int i=0; i<p.length; i++){
            set.add(p[i]);
        }
        // 모든 전화번호의 substring이 HashSet에 존재하는지 확인한다.
        for(int i=0; i<p.length; i++){
            for(int j=0; j<p[i].length(); j++){
                if(set.contains(p[i].substring(0, j))) return false;
            }
        }
        return true;
    }
}

• 실패 코드1 (시간 초과)

import java.util.*;

class Solution {
    public boolean solution(String[] p) {
        Arrays.sort(p);
        boolean answer = true;
        roop:for(int i=0; i<p.length; i++){
            String now = p[i];
            for(int j=i+1; j<p.length; j++){
                if(p[j].matches(now+"(.*)")){
                    answer = false;
                    break roop;
                }
            }
        }
        return answer;
    }
}

• 실패 코드2 (시간초과, 로직은 사실상 같다.)

import java.util.*;

class Solution {
    public boolean solution(String[] p) {
        boolean answer = true;
        Arrays.sort(p);
        HashSet<String> set = new HashSet<>();
        set.add(p[0]);
        roop:for(int i=1; i<p.length; i++){
            Iterator<String> iter = set.iterator();
            while(iter.hasNext()){
                String now = iter.next();
                if(p[i].matches(now+"(.*)")){
                    answer = false;
                    break roop;
                }
            }
            set.add(p[i]);
        }
        return answer;
    }
}