6-1 전화번호 목록

유태형·2022년 7월 10일

Java 알고리즘 프로그래머스

알고리즘 - Java

목록 보기

16/32

출처

해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다

문제

문제 분석

접두어를 구하는 문제입니다. 접두어가 무엇을 의미하는지, 정렬시 어떤 기준으로 정렬되는지 등을 아는것이 중요한 것 같습니다.

풀이

나의 풀이

2중 for문을 이용하여 문제를 해결하려 하였습니다. 0번째 인덱스의 문자열 부터 마지막-1 번째 인데스 까지 차례로 뒤의 문자열 들을 모두 비교하려 하였습니다.

하지만 효울성에서 3번과 4번 테스트 케이스를 통과할 수 없었습니다.

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        for(int i = 0; i< phone_book.length - 1;i++){
            String pre = phone_book[i]; //현재 접두어
            for(int j =i+1; j<phone_book.length;j++){ //뒷문자열들 비교
                String number = phone_book[j];
                if(number.startsWith(pre))
                    return false;
                if(pre.length() > number.length()) continue;
                if(pre.compareTo(number.substring(0,pre.length())) > 0) break;
            }
        }
        //접두어가 하나도 존재x
        return true;
    }
}

강의의 풀이

강의에서도 2중 for문을 먼저 사용하였으나 효울성 문제가 있었습니다. 하지만 정렬을 할땐 2가지의 기준으로 요소들을 비교합니다.

해당 위치의 문자를 사전순으로 비교합니다.

앞의 문자들이 모두 같을때는 긴 문자가 뒤로 갑니다.

2번의 기준 덕분에 정렬시 접두어가 항상 앞으로 정렬 되므로 for문 하나로도 비교가 가능합니다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book); //정렬
        //바로 앞뒤로 비교해도 가능
        //1. 앞부분이 다른 경우
        //2. 같은 경우
        //3. 앞부분이 같고 더 긴경우
        //글자 뿐 아니라 알파벳 문자열 길이도 고려하여 정렬됨
        for(int i=1;i<phone_book.length;i++)
            //시작한다면
            if(phone_book[i].startsWith(phone_book[i-1]))
                return false;
        return true;
    }
}