송민준의 개발노트

프로그래머스-level2-전화번호 목록 본문

알고리즘/프로그래머스

프로그래머스-level2-전화번호 목록

송민준 2019. 12. 2. 21:53

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

 

코딩테스트 연습 - 전화번호 목록 | 프로그래머스

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 r

programmers.co.kr

전화번호부에 있는 값들이 다른 전화번호에 접두어가 될 수 있는가를 푸는 문제이다.

문제 분류가 Hash인만큼 효율성 또한 보겠군싶어서 HashMap을 사용했다.(결론부터 말하자면 그럴필요 없음)

 public boolean solution(String[] phone_book) {
    	        HashMap<Integer, String> bookMap = new HashMap<Integer, String>();
    	    	for(int i =0; i < phone_book.length; i++) {
    	        	bookMap.put(i, phone_book[i]);
    	        }
    	    	for(int i =0; i< phone_book.length; i++) {
    	    		bookMap.remove(i);
    	    		for(int j=0; j < phone_book.length; j++) {
    	    			if(i==j) {continue;}
    	    			int n = bookMap.get(j).indexOf(phone_book[i]);
    	    			if(n == 0) {return false;}
    	    		}
    	    		bookMap.put(i, phone_book[i]);
    	    	}
    	    	return true;
    	    }

접근 방식은 HashMap에 Integer는 인덱스, String에는 전화번호가 들어가게 했으며

자기 자신은 제외를 하기 위해 remove put을 해줬는데 그냥 선택정렬 쓰면 된다 --..

그리고 indexOf를 써서 0일 경우 false를 반환하게 했는데 접두사 문제이기 때문에 반드시 0이 들어가야 한다.

효율성의 경우 System.out.println() 안빼고 돌려서 좀 많이 나오기도 했는데 통과한걸 보니 괜찮은듯

 

다른 사람 코드(좋은)

class Solution {
    public boolean solution(String[] phone_book) {
      for(int i=0; i<phone_book.length-1; i++) {
            for(int j=i+1; j<phone_book.length; j++) {
                if(phone_book[i].startsWith(phone_book[j])) {return false;}
                if(phone_book[j].startsWith(phone_book[i])) {return false;}
            }
        }
        return true;
    }
}