[프로그래머스] 완주하지 못한 선수

▪︎ 문제

---

프로그래머스 완주하지 못한 선수

▪︎ 알고리즘 설계

---

• Sorting / Loop 활용
  1. 두 배열을 정렬한다.
  2. completion list의 length 만큼 돌면서 participant에만 존재하는 한 명을 찾는다.
  3. 배열을 전부 다 뒤져도 답이 없다면, participant의 마지막 주자가 완주하지 못한 선수이다.
• Hash 활용
  1. key에 선수 이름, value에 count를 갖는 해시 맵을 만든다.
  2. completion에 존재하는 선수들의 해시를 뺀다.
  3. value가 남아있는 선수가 완주하지 못한 선수이다.

▪︎ 코드

---

• Sorting / Loop 활용

    import java.util.*;
      
    class Solution {
        public String solution(String[] participant, String[] completion) {
              
            Arrays.sort(participant);
            Arrays.sort(completion);
              
            int i = 0;
            for(; i < participant.length - 1; i++) {
                if(!(participant[i].equals(completion[i]))) {
                    break;
                }
            }
              
            return participant[i];
        }
    }
  

• Hash 활용1

    import java.util.*;
      
    class Solution {
        public String solution(String[] participant, String[] completion) {
            String answer = "";
              
            HashMap<String, Integer> map = new HashMap<>();
              
            for(String player : participant)
    	        map.put(player, map.getOrDefault(player, 0) + 1);
      	        
    	      for(String player : completion)
    	        map.put(player, map.get(player) - 1);
      	      
    			  for(String key : map.keySet()) { // map이 가지고 있는 key들을 하나의 배열로 담아 하나씩 꺼낼 수 있음
    				  if(map.get(key) != 0) {
    					  answer = key;
    					  break;
    					}
    				} 
      				
            return answer;
        }
    }
  

• Hash 활용2

    import java.util.*;
      
    class Solution {
        public String solution(String[] participant, String[] completion) {
            String answer = "";
              
            HashMap<String, Integer> map = new HashMap<>();
              
            for(String player : participant)
    		        map.put(player, map.getOrDefault(player, 0) + 1);
      	        
    	      for(String player : completion)
    		        map.put(player, map.get(player) - 1);
      	      
    	      // 반복을 쉽게해주는 하나의 클래스
    			  Iterator(Map.Entry<String, Integer>> iter = map.entrySet().iterator();
      			  
    			  while(iter.hasNext()) { // 여러 개의 객체들이 다음 객체가 있는 지를 확인
    					  Map.Entry<String, Integer> entry = iter.next(); // 다음 객체 entry 저장
    					  if(entry.getValue() != 0) { // 해당 entry의 value가 0이 아니라면
    						  answer = entry.getKey(); // 해당 key를 답에 저장
    						  break;
    						}
    				}
      				
            return answer;
        }
    }
  

▪︎ 시간복잡도

---

• Sorting / Loop 활용: O(N log N)
• Hash 활용: O(N)

▪︎ 틀린 이유

---

• 문자열 비교 시 == 사용
  • Java에서 ==는 문자열의 참조값을 비교하므로, 문자열 값 자체를 비교하는 equals()를 사용해야 한다.
• 이중 반복문 사용
  • 불필요한 이중 루프를 사용하면 시간복잡도가 O(N²)로 증가하여 비효율적이다.
• 마지막 주자 고려 누락
  • 완주자 배열의 길이는 참가자보다 항상 1 작으므로, 루프에서 차이가 없을 때 마지막 참가자를 반환해야 한다.
• 동명이인 처리 실패
  • 단순히 이름이 같은 경우 한 번만 삭제하는 방식은 동명이인을 제대로 처리하지 못한다.
  • 따라서 각 이름의 등장 횟수를 관리할 수 있는 해시맵 또는 정렬 비교가 필요하다.
• 정렬 및 해시맵 사용 발상 부족
  • 문제의 특성상 정렬 또는 해시맵을 이용하면 동명이인과 빠른 탐색 문제를 모두 해결할 수 있다.
    • 정렬 방식: 정렬 후 같은 이름이 연속해서 나오므로 순서대로 비교하면 됨.
    • 해시맵 방식: 동일한 이름이 등장할 때마다 카운트를 증가시켜 정확한 횟수를 관리할 수 있음

▪︎ 느낀점 / 기억할 정보

---

• 중복이 존재하는 데이터는 HashMap을 사용하여 key에 이름, value에 등장 횟수를 저장하고 관리하는 아이디어 생각할 수 있어야 한다.
• Java에서 ==는 참조 비교, equals()는 값 비교이다.
• Iterator와 Map.Entry 사용법 숙지
  • 해시맵의 keySet()을 순회하거나 entrySet()을 순회하면서 value 조건으로 값을 찾을 수 있다.