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

1. 문제

---

수많은 마라톤 선수들이 마라톤에 참여하였습니다.

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에
    한명은 완주하지 못했습니다.

 

 

2. 초기 아이디어

---

• 참여자의 이름이 완주자 명단에 있는경우 완주자 명단에서 삭제.
• 참여자의 이름이 완주자 명단에 없는 경우 해당 완주자 이름 return.
• 이렇게 되면 이름이 중복되어도 처리가 가능하다.

 

 

3.  구현

---

• 완주자 명단에서 참여자가 있는지 어떻게 찾을 것인지..?
  • ArrayList의 contains() 활용

 

 

 

4. 코드

---

import java.util.ArrayList;
import java.util.Arrays;

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

        ArrayList<String> participants = new ArrayList<>(Arrays.asList(participant));
        ArrayList<String> completions = new ArrayList<>(Arrays.asList(completion));

        for (String p : participants) {
            if (completions.contains(p)){
                completions.remove(p);
            }else {
                return  p;
            }
        }
        return "";
    }
}

 

 

5. 결과

---

• 되긴 하는데 효율성이 꽝이다.

 

 

 

6. 코드 개선

---

• 이 문제는 "해시"를 활용하는 것이다.
• "해시"를 활용하자.
• hashMap에 이름별 count를 집어넣자.
  • key : 이름
  • value : count 수 -> 동명 이인이면 count = 2
• 위의 방식과 유사하게 이번에는 참여자에서 완주자를 빼주자.
• 참여자 이름이 완주자 명단에 있는 경우 count를 1뺀다.
• 루프를 다 돌고 count가 여전히 1이상인 경우는 참여자 이름이 완주자 명단에 없다고 볼 수 있음.
• 동명 이인인 경우 완주자 명단에 두 번 나와야 하지만 한 번만 나오는 경우 count가 1이 됨.
• getOrDefault(key, defaultValue) : key에 해당하는 value가 있으면 가져오고 없으면 defaultValue 반환.

import java.util.HashMap;

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

        HashMap<String, Integer> participants = new HashMap<>();

        //중복이름 count
        for (String player : participant) {
            participants.put(player, participants.getOrDefault(player, 0)+1);
        }

        //참여자 명단에서, 완주 명단에 있는사람 count-1
        for (String c : completion) {
            if (participants.containsKey(c)){
                Integer cnt = participants.get(c);
                participants.put(c, cnt-1);
            }
        }

        //참여자 명단에서 count가 1 이상인 경우 미완주자.
        for (String p : participants.keySet()) {
            if (participants.get(p) > 0){
                answer =  p;
            }
        }

        return answer;
    }
}

 

 

7. 결과

---

• 테스트 통과와 더불어 효율성도 증가되었다.

 

 

8. 정리

---

• HashMap의 장점??
  • 자료를 찾는 시간이 빠르다.
  • HashMap은 애초부터 검색을 위한 자료구조이다.
  • key & value pair로 자료를 관리하기 때문에 key 에 해당하는 value를 찾는데 빠름.
  • 반면 ArrayList는 선형 구조로 i 번 째 자료를 찾는데 최적화 되어있음.
  • 즉 첫번째 코드의 경우 처음부터 순서대로 값을 비교하기 때문에 효율성이 떨어졌다고 할 수 있음.
• getOrDefault(key, defaultValue) : key에 해당하는 value가 있으면 가져오고 없으면 defaultValue 반환
• 즉 특정 data를 빠르게 찾아야 한다? -> HashMap을 사용하는걸 고려하자.

 

 

9. GitHub : coding_test

---

GitHub - bsh6463/coding_test