[프로그래머스/Lv.2] 전화번호 목록

 

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

프로그래머스

 

최종 코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        int len = phone_book.length;
        Map<Integer, String> map = new HashMap<Integer, String>();      
        Arrays.sort(phone_book);
        
        for(int i = 0; i < len; i++) {
            map.put(i, phone_book[i]);
        }
        
        for(int i = 0; i < len - 1; i++) {
            if(map.get(i+1).startsWith(map.get(i))) {
                answer = false;
                break;
            } else continue;
        }
        
        return answer;
    }
}

 

정렬하면 쉽게 풀리는 문제들이 은근 있는거같다 정렬도 항상 머리속에 넣고 있어야할듯

 

	for(int i = 0; i < len; i++) {
		for(int j = 0; j < len; j++) {
			if(j != i) {
				if(map.get(j).startsWith(map.get(i))) {
					answer = false;
					break;
				} else {
					continue;
				}
			}
		}
	}

 

처음에는 정렬하지않고 이런식으로 현재 기준값 제외하고 나머지 값들을 다 돌며 현재값으로 시작하는 단어인지 검사해주었다 답은 다 맞았지만 당연히 효율성에서는 시간초과로 다 나왔다

그렇게 해서 생각한게 정렬이었다 정렬을 하면 현재 기준 다음값만 가져와서 현재값으로 시작하는 단어인지 딱 한번씩만 검사해주면 되는거였다!! 

예를 들어 ["135", "157", "13", "1357"] 배열은 sort로 오름차순정렬시 ["13', "135", "1357", "157"] 이렇게 정렬되기때문에 각인덱스마다 바로 다음값과의 비교만 하면 된다 훨씬 효율적!!

 

근데 풀면서 의문이 이걸 해시로 꼭 풀어야하는건가? 였다 해시 카테고리가 아니었다면 그냥 배열을 돌며 비교했을거같고 그거도 나쁘지 않은 방법같단 생각을 했다

 

그래서 직접 하고 비교해보기로 했다

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        int len = phone_book.length;     
        Arrays.sort(phone_book);
        
        for(int i = 0; i < len - 1; i++) {
            if(phone_book[i+1].startsWith(phone_book[i])) {
                answer = false;
                break;
            } else continue;
        }
        
        return answer;
    }
}

 

 

오히려 코드도 짧고 좀더 빠른거같기도,,?🤔🤔🤔

해시 카테고리에 있어서 해시로 먼저 풀어봤으나 만약 실제 코테에서 이 문제를 만났다면 이 방식으로 풀었을거같다