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

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

---

풀이

import java.io.*;
import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        for(int i = 0; i < phone_book.length; i++){
            int spaceIndex = phone_book[i].indexOf(" ");
            phone_book[i] = (spaceIndex == -1) ? phone_book[i] : phone_book[i].substring(0, spaceIndex);
        }

        Arrays.sort(phone_book, Comparator.comparingInt(String::length));
        int maxLength = phone_book[0].length();
        HashSet<String> set = new HashSet<>();
        for(String x : phone_book){
            for(int i = 1; i <= maxLength; i++){
                if(set.contains(x.substring(0,i))){
                    answer = false;
                    break;
                }
            }
            maxLength = Math.max(maxLength, x.length());
            set.add(x);

        }
        
        return answer;
    }

}

먼저 사용자에게 입력받은 전화번호를 공백을 기준으로 가장 앞부분만 따서 저장했다.

왜냐하면 우리에게 필요한 것은 접두사이기 때문이다!

여기서 알아두면 좋을 것 같은 코드는 .indexOf를 했을 때 없으면 -1이 나온다는 것. 또한 substring 할 때 indexOf는 공백의 위치를 반환하기 때문에 별다른 손질 없이 사용해도 된다는 것!

 

그 이후엔 배열을 문자열의 길이 오름차순으로 정렬했다.

일단 메서드를 설명하고 한 이유에 대해 알아보자.

Arrays.sort(phone_book, Comparator.comparingInt(String::length));

사실 나도 처음 사용해봤고, gpt가 알려준 방법인데 잘 기억해 둔다면 이런 문제를 풀 때 매우 유용하게 사용할 수 있을 것 같다. String::length로 문자열의 길이를 인트로 만든 뒤에 comparingInt를 통해 길이를 비교하는 방식이다. 기억하기 어렵겠지만 꼭 기억해 보자!

 

그럼 왜 문자열의 길이로 오름차순 정리를 했나??

처음부터 생각한 것은 아니었지만 테스트케이스에서 계속 오류가 발생했고, 이에 대해 코드를 직접 생각해보다 보니 떠오른 케이스가 있었다. 만약 저 한 줄이 없다고 가정하고 코드를 생각해 보자.
테스트 케이스인 119, 11923231 만 생각해 보면 된다.
1.  119가 들어왔고 1,11,19 모두 없으니 이 접두사는 없구나 하고 set에 추가하게 된다.

2. 11923231이 들어왔고, 1 11 119에서 키를 갖고 있기 때문에 false를 저장하고 반복문을 탈출하며 끝이 난다.

즉 우리가 원하는 상황대로 처리가 된다.

 

하지만 반대로 11923231, 119 순으로 들어온다면?

1. 11923231이 들어왔고 1 11 119 1192 11923...으로 키 검사가 진행되며 한 번도 걸리지 않았기에 11923231이 추가된다.

2. 1 11 119를 검사하지만 11923231만 set에 들어있으므로 걸리지 않고 set에 추가하게 된다.

여기서 오류가 발생하는 것이다. 위의 것과 동일한 결과를 가져야 하지만 순서가 다르다고 오답이 된다는 것. 즉, 작은 원소에서부터 검사해야 안전하게 처리가 가능하다는 것이다!

 

maxLength를 둔 이유는 간단하다. 오름차순 정렬을 해뒀기 때문에 이 전의 키값들은 나보다 같거나 작은 길이를 갖게 된다. 그렇다면 굳이 내 길이만큼 비교를 하는 것은 큰 손해라고 생각했고, 단 한 번이라도 적게 검사하자!라는 생각으로 넣은 것이다.