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

1. 접근방식 / 설계

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

  1. phone_book 을 정렬
  2. 이중 for문으로 구성.
    • 첫 for문에서는 startsWith() 할 대상을 지정 (=phone_book[i])
    • 내부 for문에서는 1에서 지정한 대상의 뒤에 있는 원소들을 순회하면서 phone_book[i+1].startsWith(phone_book[i]) 을 체크한다.
    • 맞다면 answer = false;

2. 코드

❗ 실패한 코드

정확성 테스트 12번, 효율성 테스트 3,4번 실패

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

static boolean mySolution(String[] phone_book) {
    boolean answer = true;
    Arrays.sort(phone_book);

    Loop1 :
    for(int i=0; i<phone_book.length; i++) {
        Loop2 :
        for(int j=1; j<phone_book.length-(i+1); j++) {
            if(phone_book[i+j].startsWith(phone_book[i])) {
                answer = false;
                break Loop1;
            }
        }
    }

    return answer;
}

3. 다른 방식 코드 분석

1) hash 이용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

static boolean otherSolution(String[] phoneBook) {
    boolean answer = true;

    Map<String, Integer> map = new HashMap<>();

    for(int i = 0; i < phoneBook.length; i++) {
        map.put(phoneBook[i], i);
    }

    for(int i = 0; i < phoneBook.length; i++) {
        for(int j = 1; j < phoneBook[i].length(); j++) {
            String s = phoneBook[i].substring(0,j);
            if(map.containsKey(s)) {
                answer = false;
                return answer;
            }
        }
    }

    return answer;
}

ex) String[] phone_book = {"119", "97674223", "1195524421"};

  1. phoneBook 배열을 map 으로 변환.
  2. phoneBook[i](=비교할 접두어, "119")의 문자열 길이만큼 내부 for문 반복
    1. i=0, j=1 String s = "119".substring(0,1) == "1"
      ⇒ map에 s 와 동일한 key 가 존재하지 않으므로 j++

    2. i=0, j=2 String s = "119".substring(0,2) == "11"
      ⇒ j++, i++

      (… 생략)

    3. i=2, j=3 String s = "1195524421".substring(0,3) == "119"
      ⇒ map.containsKey(s) == true 가 되면서 return false;


2) sort 이후 한 번의 for문

1
2
3
4
5
6
7
8
9
10
11

static boolean otherSolution2(String[] phoneBook) {
    Arrays.sort(phoneBook);
    boolean result = true;
    for (int i=0; i<phoneBook.length-1; i++) {
        if (phoneBook[i+1].contains(phoneBook[i])) {
            result = false;
            break;
        }
    }
    return result;
}

4. 관련된 개념 공부

1) substring

public String substring(int startIndex)

  • startIndex 부터 끝까지의 문자열을 리턴(startIndex 포함)
    ex) "Hello".substring(2) = "llo"

public String substring(int startIndex, int endIndex)

  • startIndex(포함)부터 lastIndex(불포함) 전까지의 문자열을 리턴
    ex) "Hello".substring(2,4) = "ll"