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

[문제]

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

알고리즘 연습 - 전화번호 목록 | 프로그래머스

 

[풀이방법]

 

문자열 비교 문제입니다. 

 

알고리즘 분류가 해시로 되어있는데 질문하기 목록을 보니 여러 가지 방법으로 문제를 풀이할 수 있는 것 같습니다. 

 

1. 해시
2. 정렬
3. 트라이 

저는 정렬을 사용했는데 이 세 가지 방법을 추후에 다 해봐야 할 것 같아요! 

 

먼저 접두사의 기준이 될 문자열을 뽑아야 합니다. 접두사가 되기 최적의 조건은 저는 가장 짧은 문자열을 선택했습니다. 

 

문자열 배열로 주어지기 때문에 저는 list로 만들어서 sort 함수를 사용해서 정렬을 해주었습니다. 

 

        list.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() == o2.length()) {
                    return o1.compareTo(o2);
                } else{
                    return Integer.compare(o1.length(), o2.length());
                }
            }
        });

 

더 효율적인 방법이 있다면 그 방법을 사용하셔도 무방합니다. 

 

접두사 == 가장 짧은 문자열 (저 같은 경우에는 list의 가장 앞에 위치한 원소입니다.)

 

그리고 문자열 배열을 탐색하면서 접두사의 길이만큼 앞 부분을 잘라 (substring. 접두사이기 때문에 앞 부분만 같아야 합니다. 이 부분을 고려하지 않으면 테스트 케이스 5번이 틀립니다.)

 

앞 부분이 아까 구한 가장 짧은 문자열과 같을 경우 (equals) 접두사를 포함한 전화번호가 목록에 있으므로 false를 반환하고 반복문을 중단합니다.

 

 

---

 

import java.util.ArrayList;
import java.util.List;
import java.util.Comparator;
import java.lang.Integer;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        List<String> list =new ArrayList<>();
        
        for (String s : phone_book) {
            list.add(s);
        }
        
        list.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() == o2.length()) {
                    return o1.compareTo(o2);
                } else{
                    return Integer.compare(o1.length(), o2.length());
                }
            }
        });
        
        int size = list.size();
        int index = 0;
        String stand = list.get(index);  //가장 짧은 문자열을 기준으로 접두사를 살핀다.
        for (int i = 1; i < size; i++) {
            if (list.get(i).substring(0, stand.length()).equals(stand)) {
                answer = false;
                break;
            }  
        }
        
        return answer;
    }
}