[문제풀이] Level2 전화번호 목록

전화번호 목록

---

  🪅 String의 내장 메서드 startsWith()를 알고 있느냐
  🪅 String배열을 Arrays.sort()했을때 어떤 식으로 정렬되는지 알고 있느냐 => 첫번째 문자를 기준으로 정렬된다
  🪅 for문을 한번만 쓰고도 문제를 해결할 수 있느냐(효율성 테스트)

💡 문제 접근 과정
phone_book배열 중에 어떤 원소가 prefix가 될지는 입출력 예마다 다르다. 때문에 prefix가 될 원소를 for문을 통해 하나씩 대입해보고
isContain 메서드에서 prefix를 제외한 나머지 원소들과 접두사를 비교해봄으로써(startsWith())
for문을 두번 돌렸더니 효율성 테스트를 통과하지 못했다.

결국 for문을 한 번 돌리면서 문제를 해결해야했는데
이를 위해 문자열 정렬이 필요했다. Arrays.sort(문자열배열)을 하게 되면 첫문자를 기준으로 정렬된다.
정렬된 String배열을 순회하면서, 현재 원소를 prefix로 두고 바로 다음 원소와 비교함으로써 문제를 해결할 수 있었다
(정렬되어 있으니까)

⚠️ 중첩 for문을 돌리면 효율성 테스트를 통과하지 못할 수 있다.

[효율성테스트를 통과하지 못한 코드.java]

class Solution {
    boolean isContain(String[] phone_book, String prefix, int exceptIdx) {
        for(int i = 0; i < phone_book.length; i++) {
            // 접두사니까 패스
            if(i == exceptIdx) continue;
            String phoneNumber = phone_book[i];

            // 접두사의 길이가 더 길면 패스
            if(phoneNumber.length() < prefix.length()) continue;

            if(phoneNumber.startsWith(prefix)) {
                return true;
            }    
        }
        return false;
    }
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        for(int i = 0; i < phone_book.length; i++) {
            String prefix = phone_book[i];
            if(isContain(phone_book, prefix, i)) {
                answer = false;
                break;
            }
        }
        return answer;
    }
}

[효율성테스트를 통과한 코드.java]

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);

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

        return answer;
    }
}