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

Heejun Kwon·2021년 6월 19일

Java hash 알고리즘 프로그래머스 해시

알고리즘 풀이

목록 보기

9/11

프로그래머스 연습문제
프로그래머스 레벨2 - 전화번호 목록

🔎 문제

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

🚫 제한조건

phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.

💻 입출력 예

📄🤔 코드 및 풀이과정

🔹 1번

public 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;
}

🔸 1번 풀이

처음 코드는
우선 배열을 Arrays.sort로 정렬하였다.

문자열 특성상 오름차순으로 정렬할 경우
["119", "97674223", "97", "1195524421", "11", "10"] 가
["10", "11", "119", "1195524421", "97", "97674223"] 이 된다.

정렬을 하면 1개의 for문으로
i+1번 인덱스의 값이 i번 인덱스의 값으로 시작하는지
startsWith로 체크한 뒤, 한번이라도 체크에 걸린다면 false를 반환
걸리지 않는다면 true를 반환하여 문제를 해결했다.

처음부터 이렇게 깔끔하게 해결할 수 있었으면 좋을텐데
처음에는 2개의 for문을 중첩으로 사용하고,
substring이나 indexOf를 사용해 문제를 해결하려고 했었다.

처음 시도한 방법을 사용하면, 문제는 쉽게 해결할 수 있다.
다만 제한사항에서 입력되는 배열의 길이가 100만까지도 가능하도록 주어져
중첩 for문을 사용 시 최악의 경우 100만 * 100만으로 1조번 반복할 수 있다.
이로 인해 처음 중첩 for문을 사용한 코드는 정확성 부분에서 통과했지만
효율성에서 통과하지 못했다.

어떤 방법을 쓰더라도 중첩 for문을 없애고 하나의 for문만으로 처리하지 않으면
통과하지 못할 것 같아 여러가지 궁리를 하다 문자열의 정렬을 떠올렸다.

정수 문자열들을 정렬할 경우 위에서 본 것처럼
첫 자리의 숫자가 적은 순으로,
자리의 숫자가 같다면 다음 자리의 숫자가 적은 순으로,
자릿수가 더 짧은 순으로 정렬되는 특징이 있어
반복문을 한번만 돌면서 n번째 값과 n+1번째 값만 확인하면 되기 때문에
반복 횟수를 현저히 줄일 수 있다.

그리고 substring이나 indexOf으로도 접두어 체크는 가능하지만
문제를 푸는 중 배운 기억이 있던 startsWith를 사용하여 코드를 간결하게 했다.

이런 방식으로
케이스에 따라 0.20ms ~ 17.15ms 의 처리시간으로 통과했다.

하지만 이 문제의 카테고리는 "해시"로
문제의 의도대로라면 해시를 활용해 문제를 해결해야 한다.

처음 풀 때는 해시와 관련된 컬렉션의 활용법을 잘 못해서 이런 방식을 택했는데,
문제의 의도대로 풀지 않는다면 학습 효과가 거의 없으리라 생각해
해시와 관련된 컬렉션들을 공부하고, 다시 시도해보았다.

🔹 2번

public static boolean solution(String[] phone_book) {
	
	HashMap<String, Integer> hm = new HashMap<>();
	
	for (int i = 0; i < phone_book.length; i++) {
		hm.put(phone_book[i], null);
	}
			
	for (int i = 0; i < phone_book.length; i++) {
		for (int k = 0; k < phone_book[i].length(); k++) {
			if (hm.containsKey(phone_book[i].substring(0, k)) ) {
				return false;
			}
		}
	}
	return true;
}

🔸 2번 풀이

이번엔 HashMap을 사용해 배열을 HashMap에 옮겨 담은 뒤
배열에 담긴 값을 for문으로 하나씩 가져와서
가져온 전화번호의 첫번째 문자가 HashMap에 있는지 확인하고
있다면 해당 전화번호의 접두사가 되는 전화번호가 존재하는 것이니 false를 반환,
아니라면 두번째 문자까지의 문자열이 HashMap에 있는지 확인하고
있다면 해당 전화번호의 접두사가 되는 전화번호가 존재하는 것이니 false를 반환,
아니라면 위와 같은 과정을 반복해 전화번호의 길이-1까지의 문자열이
HashMap에 존재하는지 확인한다.

전화번호의 길이까지 반복할경우 무조건 true가 나오기 때문에
전화번호의 길이 -1까지 하여 접두사 체크를 해야한다.

Hash 컬렉션들의 장점은
특정 값을 찾을 때 모든 인덱스를 찾아야 하는 배열과 달리
해쉬 함수에 의해 변환된 키 값이 인덱스가 되기 때문에
contains나 containsKey 메서드로 특정 키를 찾을 때
모든 공간을 찾지 않고 바로 찾아올 수 있어 단순 배열보다 검색에서 매우 유리하다.

처음에는 HashSet 컬렉션을 활용해서 문제를 풀었었는데,
HashSet의 내부에서 HashMap 객체를 생성해놓고
contains 메서드를 호출 시 HashMap 객체의 containsKey를 호출하도록 하여
중간에 한번 거쳐가는 구조기 때문에
HashMap을 바로 사용하는 것보다 느리다는 것을 알게 되어 수정했다.

이런 방식으로
케이스에 따라 0.7ms ~ 16.05ms의 처리시간으로 통과했다.