# \[99클럽 코테 스터디 5일차 TIL]  프로그래머스 - 전화번호 목록

## \[level 2] 전화번호 목록 - 42577

[문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/42577)

#### 문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.\
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

* 구조대 : 119
* 박준영 : 97 674 223
* 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone\_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

**제한 사항**

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

**입출력 예제**

| phone\_book                        | return |
| ---------------------------------- | ------ |
| \["119", "97674223", "1195524421"] | false  |
| \["123","456","789"]               | true   |
| \["12","123","1235","567","88"]    | false  |

**입출력 예 설명**

입출력 예 #1\
앞에서 설명한 예와 같습니다.

입출력 예 #2\
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3\
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

***

## 풀이 코드

```java
import java.util.*;

class Solution {
    public boolean solution(String[] phoneBook) {
        Arrays.sort(phoneBook);
        for(int i = 0; i < phoneBook.length - 1; i++) {
            if (phoneBook[i + 1].length() < phoneBook[i].length()) continue;
            if (phoneBook[i + 1].substring(0, phoneBook[i].length()).equals(phoneBook[i])) return false;
        }
        return true;
    }
}
```

* Time: 323.87 ms
* Memory: 96.8 MB

### 풀이 과정

1. 문자열 배열 그대로 오름차순 정렬을 통해 접두어가 되는 문자가 있다면 순서대로 배치되도록 한다.
2. `i` 번째 문자열과 `i + 1` 문자열의 길이를 비교하여 `i + 1` 의 문자열의 길이가 더 짧다면 넘긴다. 접두어가 같을 경우, 문자열의 길이가 긴 문자가 무조건 `i + 1` 에 배치될 수 밖에 없다.\
   (ex. `{ "2423390", "2420" }` -> `{ "2420", "2423390" }`)
3. `i + 1` 번째 문자열을 `i` 번째 문자열의 길이만큼 자르고 동일한 문자인지 비교한다.

### 개선하기

```java
import java.util.*;

class Solution {
    public boolean solution(String[] phoneBook) {
        Arrays.sort(phoneBook);
        for (int i = 0; i < phoneBook.length - 1; i++) {
            if (phoneBook[i + 1].startsWith(phoneBook[i])) return false;
        }
        return true;
    }
}
```

* Time: 337.13 ms
* Memory: 98.5 MB

앞선 풀이와 속도나 메모리 차이가 크진 않다. 해당 문제를 풀 때 IDE 의 도움없이 문제를 풀어봤는데 `startsWith()` 함수가 있다는걸 알았으나 `startWith()` 로 기억하고 있어서 해당 함수를 쓰질 못했다.

해당 함수를 활용한 풀이로 함수 이름이 매우 직관적이어서 코드의 간결함이나 가독성 면에서는 더 좋다고 생각한다.

### 다른 사람의 풀이

```java
import java.util.*;

class Solution {
    public boolean solution(String[] phoneBook) {
        boolean answer = true;
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < phoneBook.length; i++) {
            map.put(phoneBook[i], i); // key 에 전화번호를 할당
        }
        for (String s : phoneBook) {
            for (int j = 0; j < s.length(); j++) {
                /*
                전화번호를 문자 단위로 잘라서 맵에 있는지 확인
                j 까지만 잘라서 자기 자신을 비교하지 않도록 함
                */
                if (map.containsKey(s.substring(0, j))) {
                    return false;
                }
            }
        }
        return answer;
    }
}
```

* Time: 307.91 ms
* Memory: 226 MB

`HashMap` 을 사용한 풀이로 `cotainsKey()` 함수를 활용하고 `j` 길이까지만 잘라서 자기 자신은 포함되지 않게 하는 부분이 참신했다.

위 풀이에서 `HashMap` 의 value 값은 사용하지 않기 때문에 `HashSet` 으로도 풀어봤다.

### 다른 사람의 풀이를 개선하기

```java
import java.util.*;

class Solution {
    public boolean solution(String[] phoneBook) {
        boolean answer = true;
        Set<String> set = new HashSet<>();
        Collections.addAll(set, phoneBook);
        for (String s : phoneBook) {
            for (int j = 0; j < s.length(); j++) {
                /*
                전화번호를 문자 단위로 잘라서 set 에 있는지 확인
                j 까지만 잘라서 자기 자신을 비교하지 않도록 함
                */
                if (set.contains(s.substring(0, j))) {
                    return false;
                }
            }
        }
        return answer;
    }
}
```

* Time: 282.45 ms
* Memory: 219 MB

메모리 사용량의 차이는 크지 않으나 속도는 유의미하게 감소했다. 시도한 풀이 방법 중 가장 빠르다.

***

## 돌아보기

이번에 풀어본 문제는 실제 코딩테스트 환경에 익숙해지기 위해 IDE(IntelliJ) 없이 프로그래머스 페이지에서만 풀어봤다. 앞서 언급했던 `StartsWith()` 함수가 있는건 알지만 철자가 틀려서 함수 사용을 하지 못하고 다른 방식의 풀이로는 풀질 못했다. 회사 동료가 힌트를 줘서 겨우 풀 수 있었다.

IDE에 생각보다 더 많이 의존하고 있다는 생각을 했다. 하나의 문제로 여러 풀이법을 알 수 있어서 재밌었다.

### 다음에는

* 앞으로도 IDE 없이 문제 풀어보기
* 경쟁심이나 열등감을 인정하기

***

\#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL