[Java] 해시 - 전화번호 목록 (Lv2)

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

프로그래머스

 

 

✔ 입출력 예시

전화번호 목록 입출력 예시

 

 

💡 포인트

1️⃣ 한 번호가 다른 번호의 접두어인 경우가 있다면 false를 return 해야함

      👉 어떤 번호가 다른 어떤 번호의 시작이라면 false를 return

 

 

1️⃣ 첫번째 시도

❓ 풀이과정

     👉 String클래스의 startsWith() 메서드 이용하기
     👉 phone_book 배열을 Arrays.sort()로 정렬한 뒤 반복문을 이용하여 startsWith()로 앞뒤 비교하기

❗ 결과

     👉 테스트 통과 

Arrays.sort()와 starsWith()를 활용한 소스코드 결과

 

✔ 소스코드

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"};
		String[] phone_book = {"819232312", "976", "119552", "2"};
		
		System.out.println(solution(phone_book));
	}

	private static boolean solution(String[] phone_book) {
		
		Arrays.sort(phone_book);
		// 확인
		// System.out.println(Arrays.toString(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;
	}

}

앞에서 Arrays.sort()로 정렬을 한번 해주었기 때문에

String[] phone_book = {"119", "97674223", "1195524421"}; 👉 String[] phone_book = {"119", "1195524421", "97674223"};

위와 같이 정렬이 되므로 앞뒤로만 startsWith()로 비교를 해도 충분히 답을 구할 수 있었다.

 

 

2️⃣ 두번째 시도 (2022.10.07)

Hash에 대한 문제였으므로 Hash로 한번 더 도전해보았다.

❓ 풀이과정

     👉 HashSet 이용하기

     👉 HashSet에 phone_book에 있는 원소들을 모두 집어 넣은 후 2중 for문을 이용하여 각 phone_book의 원소와

           HashSet에 있는 모든 key값들과 비교

     👉 HashSet에 있는 Key와 비교할때 각 phone_book의 원소들을 최소 한글자(첫글자)부터 최대 HashSet의 원소의

           길이까지만 substring()을 이용하여 잘라서 비교

❗ 결과

     👉 테스트 통과

HashSet을 이용한 결과

 

 

✔ 소스코드

import java.util.HashSet;

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"};
		String[] phone_book = {"819232312", "976", "119552", "2"};
		
		System.out.println(solution(phone_book));
	}

	private static boolean solution(String[] phone_book) {
		
		HashSet<String> hash = new HashSet<>();
		
		for (int i = 0; i < phone_book.length; i++) {
			hash.add(phone_book[i]);
		}
		
		for (String num : phone_book) {
			for (int j = 1; j < num.length(); j++) {
				if(hash.contains(num.substring(0, j))) {
					return false;
				}
			}
		}
		
		return true;
	}

}

 

 

처음에는 HashSet을 이용한 풀이는 2중 for문을 사용하여 더 오래걸릴 것이라 생각했다.

테스트 결과 HashSet을 이용한 풀이가 배열을 이용한 문제풀이보다 훨씬 시간이 짧게 걸림을 알 수 있었다.

자료구조의 중요성을 다시 생각해보는 문제였다🔥