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

사용 언어: Python3, Java

문제

완주하지 못한 선수

나의 풀이

Python3

from collections import defaultdict

def solution(participant, completion):
    dic = defaultdict(int)
    for x in participant:
        dic[x] += 1
    for x in completion:
        dic[x] -= 1
    
    for x in dic.items():
        if x[1] != 0:
            return x[0]
    
    return ''

• 테스트 케이스: 통과
• 제출 결과: 통과

Java

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {

        HashMap<String, Integer> hm = new HashMap<String, Integer>();
        
        for (int i=0; i<participant.length; i++) {
            hm.put(participant[i], hm.getOrDefault(participant[i], 0) + 1);
        }
        for (int i=0; i<completion.length; i++) {
            hm.put(completion[i], hm.getOrDefault(completion[i], 0) - 1);
        }
        
        for (HashMap.Entry<String, Integer> entry : hm.entrySet()) {
            if (entry.getValue() != 0) {
                return entry.getKey();
            }
            // System.out.println(entry.getKey() + ":" + entry.getValue());
        }
        
        return "";
    }
}

• 테스트 케이스: 통과
• 제출 결과: 통과

다른 풀이

Java - Sorting / Loop를 활용한 solution

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        
        // 1. 두 배열을 정렬한다.
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        // 2. 두 배열이 다를 때까지 찾는다.
        int i = 0;
        for(; i<completion.length; i++) {
            if (!participant[i].equals(completion[i])) {
                break;
            }
        }
        
        // 3. 위에서 break 당하지 않고 마지막까지 다 돌았다면 마지막 주자가 완주하지 못한 선수이다.
        return participant[i];
    }
}

• 테스트 케이스: 통과
• 제출 결과: 통과
• 주의
  if (!completion[i].equals(participant[i])) 로 제출 시 실패한다!
  

Java - Hash를 활용한 solution

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        // 1. HashMap을 만든다. (participant)
        HashMap<String, Integer> hm = new HashMap<>();
        for (String p : participant) {
            hm.put(p, hm.getOrDefault(p, 0) + 1);
        }
        
        // 2. HashMap을 뺀다. (completion)
        for (String c : completion) {
            hm.put(c, hm.get(c) - 1);
        }
        
        // 3. hm에서 value가 0이 아닌 사람을 찾는다.
        for (String key: hm.keySet()) {
            if (hm.get(key) != 0) {
                return key;
            }
        }
        return "";
    }
}

• keySet() 보다 entrySet()이 훨씬 빠르다!
• 3번에서 keySet()이 아닌 entrySet()을 사용하면 탐색 속도가 더욱 빠르다고 한다.

  import java.util.HashMap;
  import java.util.Iterator;
  import java.util.Map;
  // 3. hm에서 value가 0이 아닌 사람을 찾는다.
  Iterator<Map.Entry<String, Integer>> iter = hm.entrySet().iterator();
  while (iter.hasNext()) {
    Map.Entry<String, Integer> entry = iter.next();
    if (entry.getValue() != 0) {
        return entry.getKey();
    }
  }
  

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기