[프로그래머스 / HashMap] 완주하지 못한 선수 (java)

문제 보기

소요 시간

47분 소요

문제

1명 제외, 모든 선수가 마라톤 완주 : 100,000명 이하

• String [] participant : 마라톤 참여 선수 이름 목록 , n
• String [] completion : 마라톤 완주 선수 이름 목록, n-1

완주하지 못한 선수의 이름을 return , 참가자 중 동명이인이 있을 수 있다.

문제풀이

1. List 풀이 -> 시간 초과

10분 소요.

풀이 방식

1. 리스트에 completion 목록 넣기
2. 반복문
3. contains 조건문 통해 확인
4. 완주 선수 목록에 없으면 해당 인덱스의 원소 반환
5. 있으면, 중복을 고려해 완주 선수 목록에서 같은 이름 삭제
   -> O(n^2) , 시간 초과

2. HashMap

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String,Integer> completionTable = new HashMap<>();

        for( String x: completion) {
            if(!completionTable.containsKey(x)) completionTable.put(x,1);
            else {
                completionTable.replace(x,completionTable.get(x)+1);
            }
        }

        for(String x : participant) {
            if(!completionTable.containsKey(x) || completionTable.get(x) == 0) {
                answer = x;
                break;
            }
            else {
                completionTable.replace(x,completionTable.get(x)-1);
            }
        }
        return answer;
    }
}

풀이 방식

1. completionTable의 HashMap 테이블을 생성하여 completion의 원소 (이름)을 Key, 이름이 나온 횟수를 Value 값으로 설정한다.
2. 참여 선수 배열 participant를 순회하여 completionTable에 존재하는 key 값이 없거나, 해당 value 값이 0이면 해당 선수의 이름을 반환한다.
3. 0보다 큰 수의 value 값을 가진 key일 경우, value의 값을 1 감소한다.

성능 검사

O(N)