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

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

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

✔ 입출력 예시

전화번호 목록 입출력 예시

 

 

💡 포인트

1️⃣ 각 전화번호의 길이는 1 이상 20이하이다.

2️⃣ 같은 전화번호가 중복해서 들어있지 않는다.

3️⃣ 각 전화번호의 접두사를 확인한다.

4️⃣ 효율성을 따져야한다.

 

1️⃣ Comparator와 2중 for문을 이용한 첫번째 시도

❓ 풀이과정

1️⃣ Comparator를 이용하여 배열의 원소를 길이별로 정렬

2️⃣ 정렬한 배열의 원소를 2중 for문을 이용하여 길이가 짧은 원소와 길이가 긴 원소를 짧은 길이의 원소만큼만 길이를 잘라서 두 문자열이 동일한지 비교

3️⃣ 2️⃣의 두 문자열이 동일한 원소가 있다면 false를 반환, 그렇지 않다면 true를 반환

 

✔ 소스코드

import java.util.Arrays;
import java.util.Comparator;

public class Solution { // 전화번호 목록

	public static void main(String[] args) {
//		String[] phone_book = {"119", "97674223", "1195524421"};
		String[] phone_book = {"97674223", "119", "1195524421"};
//		String[] phone_book = {"123","456","789"};
//		String[] phone_book = {"12","123","1235","567","88"};
		
		System.out.println(solution(phone_book));
	}

	private static boolean solution(String[] phone_book) {		
    
		// 길이 짧은 순으로 정렬
		Arrays.sort(phone_book, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				
				return o1.length() - o2.length();
			}
		});
		
		for (int i = 0; i < phone_book.length-1; i++) {
			for (int j = i+1; j < phone_book.length; j++) {
				if(phone_book[i].equals(phone_book[j].substring(0, phone_book[i].length()))) {
					return false;
				}
			}
		}

		return true;
	}

}

 

 ❗ 실행 결과

효율성 테스트 3,4번 시간초과

시간 초과... 이전에 알고리즘 스터디를 하면서 알게된 점인데 알고리즘 실행 시간에 있어 가장 영향을 많이 주는 것은 for문의 중첩 유무라는 것을 알게 되었다. 그래서 for문을 줄일 수 있는 방법을 고민해보기로 하였다.

 

 

2️⃣ startsWith()와 단일 for문을 이용한 두번째 시도

❓ 풀이과정

1️⃣ 배열을 문자 순으로 정렬

2️⃣ 단일 for문을 이용하여 앞의 원소와 뒤의 원소를 비교

3️⃣ 뒤의 문자열이 앞의 문자열로 시작하는 원소가 있다면 false를 반환, 그렇지 않다면 true를 반환

 

✔ 소스코드

import java.util.Arrays;

public class Solution { // 전화번호 목록

	public static void main(String[] args) {
//		String[] phone_book = {"119", "97674223", "1195524421"};
		String[] phone_book = {"97674223", "119", "1195524421"};
//		String[] phone_book = {"123","456","789"};
//		String[] phone_book = {"12","123","1235","567","88"};
		
		System.out.println(solution(phone_book));
	}

	private static boolean solution(String[] phone_book) {		
		Arrays.sort(phone_book);

		for (int i = 0; i < phone_book.length-1; i++) {
			if(phone_book[i+1].startsWith(phone_book[i])) {
				return false;
			}
		}

		return true;
	}

}

 

❗ 실행 결과

정답!

단일 for문을 이용하니까 바로 정답!!! 정답을 맞춘 후 다른 사람들의 코드를 구경하던 와중에 정답자 중 2중 for문을 이용하였는데도 풀린 사람들이 있어서 궁금해서 2중 for문을 다시 도전해보았다.

 

 

3️⃣ startsWith()와 2중 for문을 이용한 세번째 시도

❓ 풀이과정

1️⃣ 배열을 문자 순으로 정렬

2️⃣ 2중 for문을 이용하여 배열의 각 원소들을 모두 비교

3️⃣ 뒤의 문자열이 앞의 문자열로 시작하는 원소가 있다면 false를 반환, 그렇지 않다면 true를 반환

 

✔ 소스코드

import java.util.Arrays;

public class Solution { // 전화번호 목록

	public static void main(String[] args) {
//		String[] phone_book = {"119", "97674223", "1195524421"};
		String[] phone_book = {"97674223", "119", "1195524421"};
//		String[] phone_book = {"123","456","789"};
//		String[] phone_book = {"12","123","1235","567","88"};
		
		System.out.println(solution(phone_book));
	}

	private static boolean solution(String[] phone_book) {
		
		Arrays.sort(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+1].startsWith(phone_book[i])) {
					return false;
				}
			}
		}
		return true;
	}

}

 

❗ 실행 결과

실패...😢

2중 for문을 쓰자마자 또다시 효율성 테스트 3,4번에서 시간초과로 실패한 것을 볼 수 있었다. 

문제 하단의 알림

프로그래머스 '전화번호 목록' 문제 하단의 알림을 보면 테스트 케이스가 변경되었다는 말이 있는데, 이전에는 2중 for문을 써도 통과가 되었지만 지금은 되지 않는것 같다.

 

처음 작성했던 코드보다 훨씬 간결하고 쉽게 풀렸던 문제여서 조금 허무했지만 오늘도 한문제를 해결했다는 점에서 뿌듯함을 느낄 수 있는 하루의 마무리였다👍