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

본 풀이는 java 언어를 사용하였습니다.

문제 보러가기

 

풀이

해당 문제는 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. 라는 조건이 있기 때문에,
for 문으로 순회하면서 풀면 시간 초과로 실패하게 된다.

따라서 이 문제는 해시 문제로 효율성까지 생각하면서 코드를 작성해야한다.

 

마라톤 경기에 참여한 선수를 HashMap 에 모두 넣어 준다.

여기서 주의할 점은 중복되는 이름이 있을 수 있기 때문에, 이 부분을 잘 체크해주어야 한다.

HashMap 의 key 는 경기에 참여한 선수 이름, value 는 해당 이름의 인원 수 이다.

Map<String, Integer> map = new HashMap<>();

for (String name : participant) {
    if (map.containsKey(name)) { // 동일한 이름 인 선수가 있는 경우
        map.put(name, map.get(name) + 1); // 인원 수 1 증가
        continue;
    }
    map.put(name, 1); // 아니라면 인원 수 1명으로 지정
}

 

그 후 완주한 선수들이 담긴 completion 를 순회하면서 map 에 있는 이름을 조회하여, 인원 수를 1 빼준다.

만약 인원 수가 존재하지 않는다면, map 에서 해당 이름을 제거해준다.

(참고 : completion 은 완주한 선수들이 담긴 배열이므로, 참여한 선수들을 모아놓은 map 안에 무조건 이름이 존재한다.
따라서 이름이 존재하는지 체크 로직을 추가 할 필요가 없다.)

for (String name : completion) {
    map.put(name, map.get(name) - 1);
    if (map.get(name) == 0) {
        map.remove(name);
    }
}

 

위의 과정을 거치면 map 안에는 완주하지 못한 선수 이름 1 명만 남기 때문에, 결국 for 문을 1번만 수행하게 된다.

String answer = "";
for (String name : map.keySet()) {
    answer = name;
}
return answer;

 

전체코드

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> map = new HashMap<>();
        for (String name : participant) {
            if (map.containsKey(name)) {
                map.put(name, map.get(name) + 1);
                continue;
            }
            map.put(name, 1);
        }

        for (String name : completion) {
            map.put(name, map.get(name) - 1);
            if (map.get(name) == 0) {
                map.remove(name);
            }
        }

        String answer = "";
        for (String name : map.keySet()) {
            answer = name;
        }
        return answer;
    }
}

 

회고

해시 문제는 오랜만에 풀어보는 것 같은데, 문제를 읽다보니 효율성 처리를 해야겠다는 생각이 들어서 HashMap 으로 풀었는데
다행히 한번에 통과했다.

Level 1 단계 문제라서 그런지 쉽게 풀 수 있었다.

효율성을 생각해야하는 함정 문제가 꽤 있기 때문에 문제를 잘 읽고 예외 상황이 없는지 잘 생각하여 풀어야 한다.