[PGM_42577] 전화번호 목록 (java)

문제링크

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

코딩테스트 연습 - 전화번호 목록

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 정렬

1. 문제 이해

서로 다른 전화번호에 대한 배열이 주어진다. 전화번호의 접두어에 대한 개념을 이해하기 위해 예를 들어보겠다. 111, 1113, 1424 와 같이 번호가 주어졌다고 하자. 이 때 2번째 전화번호인 1113이 111을 앞에서 포함하고 있다. 그렇다면 111은 1113에 접두어라고 할 수 있다. 이렇게 접두어가 존재하면 false 존재하지 않으면 true을 반환하는 문제이다.

 

2. 접근방법

전화번호부 배열은 String이므로 Arrays.sort 정렬을 하게되면 사전식으로 정렬이 이루어진다. 즉 123, 12, 1, 432, 1234를 정렬하게 되면 1 12 123 1234 432로 정렬이 이루어진다. 따라서 n번 순회하며 앞과 뒤만 비교해주면 문제를 해결할 수 있다. 같은 접두어는 문자가 더 많은 쪽이 뒤로가게 되어있으니,  String.substring을 활용해 잘라서 비교해주면 쉽게 해결이 가능하다.

 

주의할 점은 1234와 432처럼 앞부분이 바뀌는 부분에서는 size의 차이가 발생하기 때문에, 이 부분에 대해서만 따로 처리를 해주면 런타임 에러도 방지할 수 있다.

 

3. 세부 해결방안

Arrays.sort(phone_book);

위와 같이 Arrays.sort()를 사용해주면 된다.

if(prefix.length() > phone_book[i+1].length())
    continue;

반복문을 순회할 때 size가 달라지는 부분은 따로 고려해줄 필요가 없으므로(앞부분이 다르기 때문) 위와같이 처리해주면된다.

구현코드

package pgm_42577;

import java.util.Arrays;

public class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

        Arrays.sort(phone_book);

        for(int i = 0; i < phone_book.length-1; i++){
            String prefix = phone_book[i];
            if(prefix.length() > phone_book[i+1].length())
                continue;
            String val = phone_book[i+1].substring(0, prefix.length());
            if(prefix.equals(val)){
                answer = false;
                break;
            }
            System.out.println("phone_book[i] = " + phone_book[i]);
        }
        return answer;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)