고득점Kit > 해쉬 > 완주하지 못한 선수

완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

 

입출력 예

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

 

입출력 예 설명

예제 #1"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

어떻게 풀까?

문제 카테고리가 해쉬 인것으로 보아 해쉬를 이용해서 풀어야 할것 같다.

항상 참가자가 완주자 보다 많기 때문에 참가자에서 완주자를 빼고 남은 참가자를 구하는 문제로 판단된다.

동명이인이 존재하기 때문에 HashSet을 사용하기에는 적합하지 않다. 즉, HashMap을 이용해야 한다.

동명이인이 존재하기 때문에 이름을 키로 사용하기에도 

participant(참가자) 를 반복문 돌려서 completion(완주자) 에 있는지 확인하고, 있으면 패스, 없으면 새로운 배열에 추가하여 최종적으로 새로운 배열을 반환한다.

 

풀이

package aristata.programmers.d20210606;

import java.util.Arrays;
import java.util.HashMap;
import java.util.concurrent.atomic.AtomicReference;

public class 완주하지못한선수 {

    public static void main(String[] args) {
        Solution sol = new Solution();

        // TestCase1
        String[] parti1 = {"leo", "kiki", "eden"};
        String[] compl1 = {"eden", "kiki"};
        String answer1 = "leo";
        String result1 = sol.solution(parti1, compl1);
        boolean isPass1 = answer1.equals(result1);
        String message1 = "TestCase1 >>> answer1 = '" + answer1 + "', result1 = '" + result1 + "' >>> " + isPass1 + "!!!";
        System.out.println(message1);

        // TestCase2
        String[] parti2 = {"marina", "josipa", "nikola", "vinko", "filipa"};
        String[] compl2 = {"josipa", "filipa", "marina", "nikola"};
        String answer2 = "vinko";
        String result2 = sol.solution(parti2, compl2);
        boolean isPass2 = answer2.equals(result2);
        String message2 = "TestCase2 >>> answer2 = '" + answer2 + "', result2 = '" + result2 + "' >>> " + isPass2 + "!!!";
        System.out.println(message2);

        // TestCase3
        String[] parti3 = {"mislav", "stanko", "mislav", "ana"};
        String[] compl3 = {"stanko", "ana", "mislav"};
        String answer3 = "mislav";
        String result3 = sol.solution(parti3, compl3);
        boolean isPass = answer3.equals(result3);
        String message3 = "TestCase3 >>> answer3 = '" + answer3 + "', result3 = '" + result3 + "' >>> " + isPass + "!!!";
        System.out.println(message3);
    }


    static class Solution {
        public String solution(String[] participant, String[] completion) {
            // AtomicReference 클래스는 멀티쓰레드 환경에서 동시성을 보장합니다.
            AtomicReference<String> answer = new AtomicReference<>("");

            // HashMap 생성
            HashMap<String, Integer> map = new HashMap<>();

            // 참가자를 map 에 추가한다. 이때 동명이인일 경우 값을 + 1 한다.
            Arrays.stream(participant)
                    .forEach(it ->
                        map.put(
                                it,
                                map.getOrDefault(it, 0) + 1 // 기존의 map 에서 key 로 value 를 찾아 1을 더한 값을 새 value 로 저장한다.
                        )
                    );

            // 완주자를 map 에서 찾아 값을 -1 한다.
            Arrays.stream(completion)
                    .forEach(it ->
                            map.put(
                                    it,
                                    map.get(it) - 1
                            )
                    );

            // 완주하지 못한 자를 map 에서 찾아 반환한다.
            map.forEach((key, value) -> {
                if (value > 0) {
                    answer.set(key);
                }
            });

            return answer.get();
        }
    }
}

 

결과

---

보충 공부

Map 인터페이스

• Map 인터페이스는 key - value를 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는데 사용된다.
• 키는 중복될 수 없지만 값은 중복을 허용한다.
• Map 인터페이스를 구현한 클래스에는 Hashtable, HashMap, LinkedHashMap, SortedMap, TreeMap 등이 있다.
• 자주 사용하는 Map 인터페이스의 메소드
  • Set entrySet() : Map에 저장되어 있는 key-value 쌍을 Map.Entry 타입의 개체로 저장한 Set을 반환한다.
  • Set keySet() : Map 에 저장된 모든 key 객체를 반환한다. 이때 key 는 중복을 허용하지 않기 때문에 Set 타입으로 반환된다.
  • Collection values() : Map에 저장된 모든 value 객체를 반환한다. 이때 value 는 중복을 허용하기 때문에 Collection 타입으로 반환된다.
  • Object get(Object key) : 지정한 key 객체에 대응하는 value 객체를 찾아 반환한다.
  • Object put(Object key, Object value) : Map 에 key-value 를 저장한다.
  • Object remove(Object key) : 지정한 key 객체와 일치하는 key-value 객체를 삭제한다.

출처: 남궁성 자바의 정석 3판, 582p

Map.Entry 인터페이스

• Map.Entry 인터페이스는 Map 인터페이스의 내부 인터페이스 이다.
• Map 에 저장되어 있는 key-value 쌍을 다루기 위해 정의해 놓았다.
• 자주 사용하는 Map.Entry 인터페이스의 메소드
  • Object getKey() : Entry 의 key 객체를 반환한다.
  • Object getValue() : Entry 의 value 객체를 반환한다.
  • Object setValue() : Entry 의 value 객체를 지정된 객체로 바꾼다.

출처: 남궁성 자바의 정석 3판, 583p

HashSet

• HashSet은 중복된 요소를 저장하지 않는다.
• HashSet은 저장순서를 유지하지 않으므로 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야 한다.
• 자주 사용하는 HashSet 생성자 및 메소드
  • HashSet(): HashSet 객체를 생성한다.
  • boolean add(Object o): 새로운 객체를 추가한다. 성공하면 true, 실패하면 false
  • boolean addAll(Collection c): 주어진 컬렉션에 저장된 모든 객체들을 추가한다. 합집합
  • Iterator iterator(): Iterator 를 반환한다.
  • boolean remove(Object o): 지정된 객체를 HashSet 에서 삭제한다.
  • boolean removeAll(Collection c): 주어진 컬렉션에 저장된 객체와 동일한 것들을 HashSet 에서 삭제한다. 차집합
  • boolean retainAll(Collection c): 주어진 컬렉션에 저장된 객체와 동일한 것만 HashSet 에 남기고, 나머지를 삭제한다. 교집합
  • Object[] toArray(): 저장된 객체들을 객체배열의 형태로 변환한다.

출처: 남궁성 자바의 정석 3판, 631p

HashMap

• HashMap 은 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다.
• 해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.
• 키(key)는 컬렉션 내의 키(key) 중에서 유일해야 한다.
• 값(value)은 키(key)와 달리 데이터의 중복을 허용한다.
• 자주 사용하는 HashMap 생성자 및 메소드
  • HashMap(): HashMap 객체를 생성한다.
  • Object get(Object key): 지정된 키의 값객체를 반환한다. 못찾으면 null을 반환한다.
  • Set keySet(): HashMap에 저장된 모든 키가 저장된 Set을 반환한다.
  • Object put(Object key, Object value): 지정된 키와 값을 저장한다.
  • Object remove(Object key): 지정된 키로 저장된 key-value 를 HashMap 에서 삭제한다.
  • Object replace(Object key, Object value): 지정된 키의 값을 지정된 객체(value)로 대체한다.
  • Collection values(): HashMap 에 저장된 모든 값을 컬렉션의 형태로 반환한다.

출처: 남궁성 자바의 정석 3판, 644~645p