2020 카카오인턴쉽 [완주하지 못한 선수] Lv.1

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

오늘 사용할 맵의 가장 큰 특징은 실제 데이터를 key-value의 한 쌍으로 저장한다는 점입니다.

데이터를 정렬해서 풀 수도 있겠지만, 필자는 문제의 의도에 맞도록 해시를 사용해서 해결하도록 하겠습니다. 

코드를 작성하기 전에 어떻게 해결해 나갈 것인가에 대한 접근법을 먼저 설계해보자면 다음과 같습니다.

문제 단순화하기

-> participant의 요소는 completion요소보다 1개 많고, 하나 더 많은 그 값이 완주하지 못한 사람이구나. 

-> 동일한 저장소에 participant를 먼저 저장하고, completion을 하나씩 삭제하다가 남는 하나가 완주하지 못 한 사람이구나

위의 조건을 기반으로 알고리즘을 접근하겠습니다. 

 

 

0. 데이터를 저장할 해시 맵을 생성해줍니다.

1. participant 배열의 요소(참가자들의 이름)를

   ("이름", map.getOrDefault("이름",0)+1)의 형태로 해시 맵에 저장해줍니다. 

 

getOrDefault(Key, DefaultValue) 사용 방법

key             : 값을 가져와야 하는 요소의 키입니다.

defaultValue : 지정된 키에 대응되는 값이 없는 경우 반환되어야 하는 기본값입니다.

반환 값        : 찾는 key가 존재하면 해당 key에 매핑되어 있는 값을 반환하고, 그렇지 않으면 디폴트 값이 반환됩니다.

 

★ +1을 사용하는 이유 -> 가장 처음으로 해시맵에 값을 초기화하는 작업이기 때문에 모든 key값에 대해 value값이

1로 초기화됩니다. 단, 이때 동명이인이 존재한다면 그 이름에 매핑되는 value만 2로 변경됩니다.

해시 맵은 중복을 제거하는 것이 아니라, 저장할 때, 키의 중복을 허용하지 않습니다.

예를 들어, ("Java", 1)로 저장했다가, 키 값이 동일한 다른 값(중복된 키 값) ("Java", 2)이 저장하려고 하면, 해시 맵에는 ("Java", 1)과 ("Java", 2) 2개의 데이터가 저장되는 것이 아니라 ("Java", 2) 하나만 저장됩니다. 

즉, 중복된 키가 저장되려고 하면 가장 마지막에 저장되는 값이 이전의 값을 덮어쓰는 개념입니다.

 

이러한 개념을 이해하고 계신다면 위의 +1의 의미를 쉽게 이해하실수 있을 것 같습니다. 

만일 참가자 중에서 동명이인이 존재한다면 해시맵에는 하나의 키만 저장되지만 다른 키와는 value값이 다릅니다. 

다음과 같은 키 값을 해시맵에 저장한다고 가정해보겠습니다.

가장 처음으로 저장되는 것이므로 getOrDefault메서드로 인해 디폴트 값인 0이 반환되고 + 1을 통해서 모든 값이 1로 초기화될 것 같지만. 동명이인이 존재하기 때문에 그렇지 않습니다. 순서대로 한 명씩 저장해보겠습니다. 

 

(1) mislav저장

participant ->  "mislav", "stanko", "mislav", "ana"

Key          ->  "mislav"

Value        ->     1

 

(2) stanko저장

participant ->  "mislav", "stanko", "mislav", "ana"

Key          ->  "mislav", "stanko"

Value        ->     1          1

 

(3) mislav저장 [getOrDefault메소드로 인해 이미 저장된 키값인 "mislav"의 value 1을 반환하고 +1 하므로 value값이 2로 덮어씌워 집니다.]

participant ->  "mislav", "stanko", "mislav", "ana"

Key          ->  "mislav", "stanko"

Value        ->     2          1

 

(4) ana저장 

participant ->  "mislav", "stanko", "mislav", "ana"

Key          ->  "mislav", "stanko", "ana"

Value        ->     2          1          1

 

위의 저장예시를 보면 아시겠지만, 중복 키에 대한 제어 방법을 getOrDefault메서드로 해결할 수 있습니다. 

 

2. complement 배열의 요소(참가자들의 이름)를 키값으로 하는 value를 -1 시켜준 뒤 다시 저장합니다.(덮어씁니다.)

-> 두 배열의 요소는 모두 한 사람을 제외하고 같으므로 한 사람을 제외한 나머지는 모두 -1을 제외한 공통된 키값을 가질 것입니다.

-> 동명이인이 있다는 가정하에 다시 한번 위의 예시로 저장 절차를 확인해보겠습니다.

 

(1) stanko저장

completion ->  "stanko", "ana", "mislav"

Key           ->  "mislav", "stanko", "ana"

Value         ->     2          0         1

 

(2) ana저장

completion ->  "stanko", "ana", "mislav"

Key           ->  "mislav", "stanko", "ana"

Value         ->     2          0         0

 

(3) mislav저장 

completion ->  "stanko", "ana", "mislav"

Key           ->  "mislav", "stanko", "ana"

Value         ->     1          0         0

 

결과적으로 동명이인이던 사람을 제외한 나머지 모두는 0이 되었습니다.

 

 

3. KeySet을 사용하여 전체 Value 순회하기 (0이 아닌 값을 찾아라!)

해당내용은 다른 방법과 비교하면서 설명하겠습니다.

 

package Kakao;
 
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
 
class Solution1 {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        //맵에 중복없이 값을 저장해주기 위해서 hashmap을 사용합니다.
        Map<String, Integer> athletes = new HashMap<String, Integer>();
 
        for(String s : participant) {
            athletes.put(s, athletes.getOrDefault(s, 0)+1);
        }
 
        
        for(String n : completion) {
            athletes.put(n, athletes.get(n)-1);
        }
 
        
        for(String key : athletes.keySet()) {
            if(athletes.get(key) != 0) {
                answer = key;
                break;
            }
        }
 
        return answer;
    }
}
public class AthletesNotFinish {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Solution1 s = new Solution1();
        String [] participant = {"mislav", "stanko", "mislav", "ana"};
        String [] completion = {"stanko", "mislav", "ana"};
        
        System.out.println(s.solution(participant, completion));
        
    }
 
}
 

 

 

마지막 개선 루프에서 맵에 저장된 value값을 조회할 때, 필자가 제공한 방법말고 다른 방법 또한 소개하겠습니다. 이는 map의 메서드인 entryset()을 사용하여 set의 형태로 저장한 후 getKey(), geetValue메서드를 사용합니다.

이는 자주 사용하는 형태이므로 정리하겠습니다. 

 

위에서 필자가 사용한 KeySet을 사용한 방법과 비교해서 설명해보겠습니다. 

entrySet() 사용 방법

entrySet 메소드는 해시맵에 저장된 key, value 값을 결합된 형태로(=entry형태) Set에 저장하여 반환합니다. 

Set의 형태로 []내부에 값이 출력됩니다.

 

for(Map.Entry<String, Integer> finish : athletes.entrySet()) {
    if (finish.getValue() != 0) {
        answer = finish.getKey();
        break;
    }
}

 

위에서 필자가 작성한 방법은 해당 맵에 있는 전체 키의 집합을 KeySet의 메소드로 반환을 받습니다. 개선 루프를 사용해 집합의 요소를 하나씩 전달받고, 전달 받은 키값을 map.get()메서드의 인자로 사용해서 바로 해당 키의 매핑된 값을 반환합니다. 

이때 이 방법은 두 가지의 절차가 진행됩니다. 

1. 다음 Key값을 가져와야 합니다. 

ㄴ> [개선루프를 사용했기 때문에 keyset에 저장된 key값을 매개변수로 가져옵니다.]

2. 매 반복마다 가져온 키를 사용해 전체 맵을 순회해서 매핑된 값을 가져옵니다. 

ㄴ> [인자로 받는 것은 오직 "Key"이므로 키를 받았을 때마다 해당 키와 매핑되어 있는 값을 매 반복마다 별도로 찾아야 하는 작업을 수행해야 합니다.]

 

이 방법은 맵에서 key만 필요한 경우에는 효과적이지만, 이 문제를 풀기 위해선 키와 값을 둘 다 한번에 받아와야 하기 때문에 이후에 설명하는 방법이 조금 더 효율적입니다.

 

예를 들어, 맵에 100,000 쌍의 데이터가 저장되어 있는데, keyset으로 키를 받아서 값을 조회하려고 합니다. 

만일 내가 찾고자 하는 값이 맵의 가장 마지막에 저장된다면 어떻게 될까요? 

keyset을 사용한 방법은 매 반복마다 전체 맵을 탐색한다고 했습니다.

 

결론적으로 내가 찾고자 하는 값이 맵의 마지막에 모여 있다면,

매 반복마다 모든 맵을 끝까지 탐색해야 합니다. 

100,000개의 key값을 받고, key 값을 받을때마다 해당 키와 매핑된 value값을 탐색하면서 찾는 겁니다.

이 과정은 별도의 반복문으로 구성하지 않아도 map.get(key)의 메소드 내부에서 자체적으로 탐색을 진행합니다. 

 

 

하지만 entrySet을 사용해서 키와 값을 set의 형태[key, value]로 받아온다면, 내가 찾고자 하는 값이 맵의 마지막에 모여있다고 하더라도, 한 번의 반복으로 해당 키와 값을 한 번에 탐색할 수 있습니다.

 

for(Map.Entry<String, Integer> finish : athletes.entrySet()) 

위의 코드가 약간 익숙하지 않게 다가올 수 있습니다만, 기본적인 개선 루프 사용법입니다. 

entrySet안에 저장되어 있는 요소의 데이터 타입을 Map.Entry<String, Integer>로 설정해준 것 뿐입니다.

 

즉, 매번 받아오는 데이터가 key-value의 쌍으로 받아오기 때문에 매 반복마다 전체 맵을 순회할 필요가 없고, 

한 번의 순회만으로 찾고자 하는 값에 접근할 수 있습니다.

 

key에 대한 value값을 매핑할 때, getValue() 메서드를 사용해서 내가받은 set형태의 데이터에서 key값을 가지고 별도의 맵 탐색 과정없이 value값만 추출할수 있습니다.

(데이터를 이미 매핑된 한 쌍의 데이터로 받아왔기 때문입니다.)

 

만일, 추출한 value 값이 0이 아니라면 다시 한 번 getKey()메소드를 사용해서 내가 받은 Set형태의 데이터에서 key값만 추출해서 값을 가져올 수 있습니다.

(데이터를 이미 매핑된 한 쌍의 데이터로 받아왔기 때문입니다.)

 

위와 같은 예시를 들자면, 값을 받을 때 100,000쌍의 [key-value]중 1쌍씩 받습니다. 

내가 받은 한 쌍의 key와 value를 getKey()와 getValue() 메서드를 활용해서 조회하고 조건에 만족하지 않는다면, 다음 쌍을 받는 형식으로 단 한번의 탐색으로 찾고자 하는 value값을 찾을 수 있습니다.

 

처리해야 할 데이터가 많다면 keySet()메서드를 사용한 방법보다 비교적으로 더 좋은 효율성을 기대할 수 있는 방법입니다.  

문제 및 자료 출처 : https://programmers.co.kr/learn/courses/30/lessons/42576