[알고리즘] 프로그래머스 : 전화번호 목록

알고리즘 문제 출처 : programmers.co.kr/learn/courses/30/lessons/42577

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

 

내가 작성한 코드

처음에 작성했던 코드인데...

public class Solution {

	public boolean solution(String[] phone_book) {
		boolean answer = true;
		for(int i=0; i<phone_book.length; i++) {
			phone_book[i] = phone_book[i].replace(" ", "");
		}
		for(int i=0; i<phone_book.length-1; i++) {
			for(int j=i+1; j<phone_book.length; j++) {
				int minLen = Math.min(phone_book[i].length(), phone_book[j].length());
				if(phone_book[i].substring(0, minLen).equals(phone_book[j].substring(0, minLen))) {
					answer = false;
				}
			}
		}
		return answer;
	}
}

 

정확성은 통과했지만 효율성에서 시간 초과로 실패했다.

 

다시 도전! Arrays.sort()로 한번 정렬을 하면 이중 for문을 쓸 필요가 없다.({"119", "97674223", "1195524421"}이 {"119", "1195524421", "97674223"}로 정렬되기 때문) 여기에서 시간을 단축해보기로 했다.

import java.util.Arrays;

public class Solution {

	public boolean solution(String[] phone_book) {
		boolean answer = true;
		for(int i=0; i<phone_book.length; i++) {
			phone_book[i] = phone_book[i].replace(" ", "");
		}
		Arrays.sort(phone_book);
		for(int i=0; i<phone_book.length-1; i++) {
			int minLen = Math.min(phone_book[i].length(), phone_book[i+1].length());
			if(phone_book[i].substring(0, minLen).equals(phone_book[i+1].substring(0, minLen))) {
				answer = false;
				break;
			}
		}
		return answer;
	}
}

 

효율성 테스트를 통과했다

 

 

다른 사람들의 풀이를 봤더니 간단하게 String의 startsWith() 함수를 썼다... 왠지 허탈해지네 ㅋㅋㅋㅋㅋ

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