[Java] 완주하지 못한 선수

allzeroyou·2025년 1월 18일
0

Java-Algorithm

목록 보기
2/26
post-thumbnail

participant 의 배열 중 1명 빼고 모든 선수가 완주함.
이때 완주 선수 배열은 completion.
크게 정렬 vs 해시맵 사용으로 문제 풀이 방식이 나뉜다.
나는 보자마자 이름-참가자수 로 저장하는 해시맵 방식을 떠올렸다.
다만 java 알고리즘 풀이를 익혀가는 과정이니, 정렬 방식도 정리했다.

1. 정렬) Arrays.sort() 활용

    import java.util.Arrays;
    
    // 1.
    // 정렬 후 comple의 참여자 수만큼 돌면서 part에만 있는 참여자 이름 출력
    
    class Solution {
        public String solution(String[] participant, String[] completion) {
            String answer = "";
            
            // 1. 정렬
            Arrays.sort(participant);
            Arrays.sort(completion);
            
            // 2. 두 배열이 다른 이름을 찾는다
            int i =0; // break 후 바로 return 해주기 위한 전역변수화! ⭐️
            for (; i<completion.length; i++){
                if(!participant[i].equals(completion[i]))
                    break;
            }
            return participant[i];
        }
    }

2. HashMap 활용

    import java.util.*;

    // 2.
    // key-value로 저장
    // par - com을 해서 value가 0이 아닌 선수 이름 출력

    class Solution {
        public String solution(String[] participant, String[] completion) {
            String answer = "";

            // 1. hashmap 만들기(par)
            HashMap<String, Integer> map = new HashMap<>();
            for(String player: participant)
                // getOrDefault: 없으면 1, 있으면 기존 + 1
                map.put(player, map.getOrDefault(player, 0)+1);

            // 2. map에서 com의 이름을 뺀 후, value가 0이 아닌 선수 이름 출력
            for(String player: completion)
                // 선수 이름을 가져오되(get), val -1 한 값을 넣어준다(put)
                map.put(player, map.get(player)-1);

            // keySet() -> map의 key만을 가져오는 배열
            for(String key: map.keySet()){
                if (map.get(key)!=0){
                    answer = key;
                    break; // 찾으면 종료(최적화)
                }
            }
            return answer;
        }
    }

이 코드의 알고리즘은 다음과 같이 작동

1. participant 배열의 모든 선수를 HashMap에 추가하고, 각 선수의 등장 횟수를 계산합니다.
2. completion 배열의 선수들을 HashMap에서 빼줍니다 (값을 1씩 감소).
3. 마지막으로 HashMap을 순회하며 값이 0이 아닌 (즉, completion에 없는) 선수를 찾아 반환합니다.

이 방법은 O(n) 시간 복잡도로 효율적으로 문제를 해결!

HashMap의 주요 내장 함수

1. put(K key, V value)
    - 지정된 키와 값을 HashMap에 추가합니다.
    - 이미 키가 존재하면 기존 값을 새 값으로 대체합니다.
    - 예: `map.put(player, map.getOrDefault(player, 0)+1);`
2. getOrDefault(Object key, V defaultValue)
    - 지정된 키에 매핑된 값을 반환하거나, 키가 없으면 기본값을 반환합니다.
    - 예: `map.getOrDefault(player, 0)`
3. get(Object key)
    - 지정된 키에 매핑된 값을 반환합니다. 키가 없으면 null을 반환합니다.
    - 예: `map.get(player)`
4. keySet()
    - HashMap의 모든 키를 포함하는 Set을 반환합니다.
    - 예: `for(String key: map.keySet())`

코드에는 없지만 유용한 메서드

1. containsKey(Object key)
    - HashMap에 지정된 키가 포함되어 있는지 확인합니다.
2. size()
    - HashMap에 포함된 키-값 쌍의 수를 반환합니다.
3. remove(Object key)
    - 지정된 키와 연관된 값을 제거합니다.

3. entrySet().iterator() 활용

⭐️ iterater 아니고 iterator 주의

위 로직과 동일, 단 key를 순회할때, KeySet 대신 EntrySet을 활용함.
EntrySet은 반복문에서 성능이 더 좋지만, Iterator 클래스에 대한 이해 필요.
가령, hasNext() 메소드나 next() 메소드 등 알고있어야 풀이 가능.

    // 3.
    // key-value로 저장
    // par - com을 해서 value가 0이 아닌 선수 이름 출력
    // entrySet 활용

    import java.util.*;

    class Solution {
        public String solution(String[] participant, String[] completion) {
            String answer = "";

            // 1. hashmap 만들기(par)
            HashMap<String, Integer> map = new HashMap<>();
            for(String player: participant)
                // getOrDefault: 없으면 1, 있으면 기존 + 1
                map.put(player, map.getOrDefault(player, 0)+1);

            // 2. map에서 com의 이름을 뺀 후, value가 0이 아닌 선수 이름 출력
            for(String player: completion)
                // 선수 이름을 가져오되(get), val -1 한 값을 넣어준다(put)
                map.put(player, map.get(player)-1);

            // 반복문에서 성능이 더 좋은 entrySet 활용
            Iterator<Map.Entry<String, Integer>> iter = map.entrySet().iterator();

            while(iter.hasNext()){
                Map.Entry<String, Integer> entry = iter.next();
                if(entry.getValue()!=0){
                    answer=entry.getKey();
                    break;
                }
            }

            return answer;
        }
    }
profile
모든 건 zero 부터, 차근차근 헛둘헛둘

0개의 댓글