프로그래머스_해시_완주하지 못한 선수 (JAVA)

기초적인 문제로 개념 자체는 엄청 쉬운데 최적화된 로직 구성이 어려운 것 같습니다. 간단히 participant 배열 안에 있는 문자열 중 completion 배열 안에 포함되지 않는 문자열 1개가 있으니 잘 찾아봐라라는 문제입니다. participant에는 중복 문자열이 존재할 수 있습니다.

 

문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예입출력 예 설명 예제 #1 leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다. 예제 #2 vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다. 예제 #3 mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

 

 

가장 간단히 해결할 수 있는 방법은 두 배열을 같은 기준으로 정렬한 뒤 0번 인덱스부터 하나씩 비교해서 두 값이 다른 순간이 나오면 participant에는 있고 completion에는 없는 문자열이므로 해당 문자열이 정답이 되도록 하는 것입니다.

import java.util.Arrays;
class Solution {
    public String solution(String[] participant, String[] completion) {

        Arrays.sort(participant);
        Arrays.sort(completion);

        String answer = null;
        int i = 0;
        while (i < completion.length) {
            if (!participant[i].equals(completion[i])) {
                answer = participant[i];
                return answer;
            }
            i++;
        }

        return participant[i];

    }
}

 

 

자바에서 제공하는 sort() 메소드는 매우 낮은 시간복잡도를 가지는 알고리즘으로 구성된만큼, 위의 코드도 크게 문제는 없을 것 같습니다. 시간도 그리 오래 걸리지 않구요. 

 

하지만 해당 문제처럼 단순한 형태가 아니라 조금만 변형돼서 나와도 위의 방법은 사용하지 못할 수 있습니다. 따라서 이 문제의 카테고리인 해시(Hash) 사용을 익혀두는 것이 좋을 듯합니다.

 

 

---

 

 

* 문제 유형

  - 다량의 문자열 비교가 필요한 경우

 

이 문제는 결국 엄청 많은 문자열을 어떻게 효율적으로 비교할 것인지에 대한 것이라고 볼 수 있습니다. 그리고 문자열 정렬 알고리즘 중 하나인 라빈카프 알고리즘에서 다뤘듯이, 해싱(Hashing)은 문자열을 빠르게 검색하고 비교할 수 있도록 해주는 기법입니다. 물론 다른 용도로도 많이 사용됩니다.

 

[JAVA/- 기본 문법] - 컬렉션 프레임워크(컬렉션 API)_Map 계열 [2/4]

 

직접 문자열을 해싱할 수도 있겠지만 이미 잘 만들어져있는 컬렉션의 HashMap을 사용하도록 하겠습니다. HashMap은 Key값을 해싱해 찾기 좋게 분류해둡니다. 여기서는 배열 안의 문자열을 해싱해야하니 Key에 문자열을 넣으면 자동으로 해싱돼서 저장된다는 의미입니다. 

 

Key값이 배열의 문자열니, Value는 문자열의 갯수로 설정해줍니다. 먼저 participant 배열의 값을 HashMap에 저장하면서 만약 현재 map 안에 해당 문자열이 없다면 디폴트로 설정된 0에 1을 더해주고, 있다면 해당 value값에 1을 다시 더해줍니다. 이렇게하면 각각의 문자열이 몇 개가 있는지 저장됩니다. 

 

얼핏보면 map에 하나를 put 할 때마다 map 안에 같은 문자열이 있는지를 검색해야하니 느릴 것 같지만, 해싱 기법의 특성 상 검색 및 문자열 비교가 매우 빠르기 때문에 일반적인 방법보다 훨씬 빠릅니다.

 

- getOrDefault(key, defaultValue) : map에서 찾는 Key가 없다면 defaultValue를 리턴함

 

저도 처음 보는 메소드인데 위 메소드가 없으면 반복문을 돌려서 직접 key를 찾아보고 있을 경우와 없을 경우를 나눠 처리해야하지만 이 작업을 자동으로 해주는 기능입니다. 위에서 설명한 로직은 아래와 같이 작성할 수 있습니다.

	public static String solution(String[] participant, String[] completion) {

		String answer = "";
		HashMap<String, Integer> map = new HashMap<>();

		// participant 배열의 모든 값을 해시 맵에 넣어줌
		for (String part : participant) {

			// key = 문자열, value = 현재 맵에 저장된 문자열 갯수에 + 1
			map.put(part, map.getOrDefault(part, 0) + 1);
		}

 

 

그리고 이제 두 번째 배열의 문자열을 다시 Hashmap에 넣어주면서 이번엔 value를 하나씩 빼줍니다. 이렇게 하면 결국 두 배열에서 차이가 나는 문자열만 value가 1이 될 것이고 나머지는 모두 0이 되겠죠. 나중에 문제가 더 복잡해지면 추가적인 로직을 좀 더 짜주면 될 듯합니다.

	/* 해시 - 완주하지 못한 선수 */
	public static String solution(String[] participant, String[] completion) {

		String answer = "";
		HashMap<String, Integer> map = new HashMap<>();

		// participant 배열의 모든 값을 해시 맵에 넣어줌
		for (String part : participant) {

			// key = 문자열, value = 현재 맵에 저장된 문자열 갯수에 + 1
			map.put(part, map.getOrDefault(part, 0) + 1);
		}

		// completion 배열의 모든 값을 해시 맵에 넣어줌
		for (String comp : completion) {
			
			// 같은 문자열을 찾아 value의 값을 -1해줌
			map.put(comp, map.get(comp) - 1);
		}

 

 

---

 

 

이제 HashMAp에서 Value값이 0보다 큰 녀석을 찾아서 해당 key값을 리턴해주면 됩니다. 여기서 인터넷의 답안들을 조금 수정할 필요가 생깁니다. 아래는 인터넷에서 많이 보이는 코드입니다. HashMap의 Key로 구성된 Set을 하나 얻어서 순환시키는 거죠. 순환하면서 해당 key가 가진 value를 검색(get)합니다. 

		for (String key : hm.keySet()) {
			if (hm.get(key) != 0) {
				answer = key;
			}
		}

 

 

위 코드가 문제가 되는 이유는 해시맵의 구조를 보면 이해할 수 있습니다. 해시맵은 내부적으로 VO 객체와 같이 Key와 Value값을 저장하는 Entry라는 객체를 사용해 데이터를 저정합니다.

 

 

 

keySet() 메소드를 실행해 Key값으로 이루어진 Set을 받아 순회하는 것까지는 별 상관이 없습니다. 하지만 그 이후 다시 get(key)를 해버리면 Set과 관계없이 다시 HashMap으로 가서 해당 Key가 가진 Value를 찾는 작업을 계속 반복하게 된다는 의미입니다.

 

 

 

 

해싱 기반이라 검색이 빨라서 크게 문제가 안될 수 있지만 기본 API에서는 이런 경우를 방지하기 위해 더 좋은 기능을 제공해줍니다. Key값만 Set으로 가져오는게 아니라 위의 Entry 객체 자체를 Set으로 가져오는 것이죠.

 

- entrySet() : 엔트리 객체로 이루어진  Set를 리턴

 

 

 

이렇게 Entry 객체를 Set으로 받으면 이제 더 이상 HashMap에서 데이터를 찾을 필요 없이 순서대로 value값을 확인하면 됩니다. 갯수가 많아질 수록 차이가 벌어질 것 같습니다. 문제 구조 상 딱 한 개만 있으므로 찾고 나면 바로 break 되도록 해줍니다.

		for (Entry<String, Integer> entry : map.entrySet()) {
			if (entry.getValue() > 0) {
				answer = entry.getKey();
				break;
			}
		}

 

 

---

 

 

* 전체코드

package pojoPrj;

import java.util.HashMap;
import java.util.Map.Entry;

public class Hash {

	public static void main(String[] args) {

		System.out.println(solution(new String[] { "mislav", "stanko", "mislav", "ana" },
				new String[] { "stanko", "ana", "mislav" }));
	}

	/* 해시 - 완주하지 못한 선수 */
	public static String solution(String[] participant, String[] completion) {

		String answer = "";
		HashMap<String, Integer> map = new HashMap<>();

		// participant 배열의 모든 값을 해시 맵에 넣어줌
		for (String part : participant) {

			// key = 문자열, value = 현재 맵에 저장된 문자열 갯수에 + 1
			map.put(part, map.getOrDefault(part, 0) + 1);
		}

		// completion 배열의 모든 값을 해시 맵에 넣어줌
		for (String comp : completion) {

			// 같은 문자열을 찾아 value의 값을 -1해줌
			map.put(comp, map.get(comp) - 1);
		}

		for (Entry<String, Integer> entry : map.entrySet()) {
			if (entry.getValue() > 0) {
				answer = entry.getKey();
				break;
			}
		}
		return answer;
	}
}