전화번호 목록

프로그래머스에서 제공하는 문제들 중 해시함수를 연습하기 위한 문제를 풀었다.

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42577

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

 

문제 설명

문제 설명 및 예시

---

풀이 과정

앞 입력값의 접수사가 뒤 값들 중 한군데라도 존재한다면 true를 반환하도록 해야 하는데 정확하게 어떤 값을 이용해야 문제를 이상 없이 해결할 수 있을 지 고민을 많이 되었다.

startsWith메소드를 사용한 초반의 오류 상황

---

처음에는 문자열로만 할 수도 있을 거라는 생각에 startsWith메소드를 사용해봤으나, 오류가 발생했다. 이에 대한 원인을 생각해본 결과 comp변수를 변화시켜 바로 다음 배열요소만 비교하고 배열 끝까지 검색하지 않고 다음 요소로 이동했기 때문에 발생했던 문제임을 알 수 있었다.

String comp = phoneBook[0];

for (int i = 1; i < phoneBook.length; i++) {
    //아래의 조건문은 요소 i와 i - 1끼리만 비교 후 다음 요소로 이동하는 문제가 발생한다.
    if (phoneBook[i].startsWith(comp))
        return flase;
    comp = phoneBook[i];
}
...

 

한 번의 반복문이였던 것을 두 번의 이중 반복문으로 수정하자 기본 예제는 정상적으로 해결되었다. 하지만 추가 예제 8번과 9번에 오류가 발생하여 완전한 코드는 아니라는 것을 알 수 있었다.

---

생각에 유연함이 사라져버려 이 이상 문자열로 좋은 결과를 낼 수 없을 것이라고 판단이 들어 해시 맵을 활용하는 방식으로 선회하였다.

이전 문제와 같이 for문을 두 번 사용해 맵에 저장하는 과정과 다시 검색하는 과정의 두 단계를 설계했으며, HashMap은 <String, String>으로 작성하여 키에 대한 값들을 비교하고자 했다.

HashMap<String, String> map = new HashMap<>();

for (int i = 0; i < phoneBook.length; i++) {
   map.put(phoneBook[i], phoneBook[i]); 
}

map.remove(phoneBook[0]);

 

처음에는 첫 인덱스를 검색할 때부터 같은 값끼리 비교를 수행해 잘못된 결과가 나오게 되는 불상사를 제거하고자 map에 요소를 전부 넣은 후 인덱스0의 요소를 지우려 했으나, 그냥 반복문의 시작 인덱스를 1부터 시작하면 간단하다는 사실을 깨닫고 수정 방향을 틀었다.

해시 맵을 이용할 때도 결국 답을 찾고자 한다면 이중 반복문을 사용해야 한다는 결론이 나오게 되었다. 이러면 문자열로 문제를 풀었을 때와 다름이 없기 때문에 과연 옳은 방향인지 고민이 많이 되었지만, 이미 진행했던 것이니 끝까지 작성을 완료한 후 결과를 확인해보자는 마음으로 작성을 멈추지 않았다.

해시 맵을 통해 문제를 해결하는 방식은 영 감이 잡히지 않았으며 또한 아까와 같이 8, 9번 예제가 틀렸다는 결과를 받게 되었다. 이를 통해 내가 스스로 생각했던 방법은 처음부터 잘못되었다는 결론을 내게 되었고 지금까지와는 다른 방법을 생각해보기 위해 모든것들을 지우고 처음부터 다시 생각을 진행했다.

Arrays.sort(phoneBook);

for (int i = 1; i < phoneBook.length; i++)
    if (phoneBook[i].startsWith(phoneBook[i - 1])
        return false;
...

 

문득 입력된 문자열 배열은 정렬이 되지 않은 상태이니 정렬을 한 후 비교를 하게 된다면 인접한 요소들끼리만 비교하면 되기 때문에 더 빠른 검색이 가능할 것이라는 생각이 떠올랐다. 이를 토대로 위 방식처럼 코드를 작성해보니 반복문도 한 번만 사용하게 되며 예시 8, 9도 정상 해결이 되는 좋은 코드가 나오게 되었다.

 

최종 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class PhoneNumberList {
	public static void main(String[] args) {
		init();
	}
	
	static void init() {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = "";
		StringTokenizer st;
		int index = 0;
		
		try {
			input = br.readLine();
			st = new StringTokenizer(input);
			String[] phoneBook = new String[st.countTokens()];
			while (st.hasMoreTokens())
				phoneBook[index++] = st.nextToken();
			
			bw.write(String.valueOf(solution(phoneBook)));
			bw.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	static boolean solution(String[] phoneBook) {
		Arrays.sort(phoneBook);
		
		for (int i = 1; i < phoneBook.length; i++)
			if (phoneBook[i].startsWith(phoneBook[i - 1]))
				return false;
		
		return true;
	}
}

---

 

채점 결과