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

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

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

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
	    public boolean solution(String[] phone_book) {
	        boolean answer = true;
	        Arrays.sort(phone_book);
	        int len[]=new int[phone_book.length];
	        Set <String> set =new HashSet<>();
	        
	        for(int i=0; i<phone_book.length; i++) {
	        	len[i]=phone_book[i].length(); //현재 단어의 길이
	        	
	        	for(int j=0; j<i; j++) {
	        		if(phone_book[i].length()<len[j]) continue;
	        		if(set.contains(phone_book[i].substring(0,len[j]))) {
	        			answer=false;
	        		}
	        	}
	        	if(!answer) break;
	        	set.add(phone_book[i]);
	        }     
	        return answer;
	    }
	}

소요시간 : 27분

 

문제를 똑바로 안 읽어서 접두어인데 그냥 포함하는 단어인 줄 알고 풀다가 문제를 다시 읽고 접두어인 것을 깨달았습니다... 오랜만에 알고리즘을 푸니까 확실히 잘 안 풀리네요...ㅜㅜ

 

로직을 보면

 

1. 현재 전화번호부의 길이를 len[i]에 저장한다.

2. j가 0부터 i-1까지 돌면서 현재 단어를 len[j]만큼 자른 단어가 set에 들어있는지 확인한다

3. set에 전화번호부를 저장한다.

 

 

실수한 부분이 만약 입력이 {"3456456464644566", "2", "55"} 이렇게 들어온다면

정렬을 했을 때 {2, 55, 3456456464644566} 되는 줄 알았는데 {2 , 3456456464644566 , 55}처럼 정렬이 되더라고요...

String인데 int로 착각했습니다ㅜㅜ

 

아무튼 처음에 정렬을 해주는 이유는 

만약 A(119885)라는 전화번호부가 B(119)라는 전화번호부를 접두어로 가지고 있다면 가지고 있다면

정렬을 했을 때 B->A 순서로 정렬이 되게 됩니다.

 

만약 정렬을 하지 않고 A, B순서로 가게 된다면 119885 가 먼저 set에 들어가게 됩니다

그렇다면 119라는 전화번호부를 마주쳤을 때, 현재 len[j]에 저장된 값보다 119라는 값의 길이가 더 작기 때문에 그냥 넘어갑니다! 

 

끝~