해시 (1) 완주하지 못한 선수

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

풀이과정

• sort를 통해 문자열 정렬->participant와 completion의 원소를 하나씩 비교해서 participant에서 틀린 부분을 return한다

• Arrays.sort(participant); 를 시도했으나 안됨 -> import java.util.*;을 빼먹었다..(바보)

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

? 정렬을 통해서 문제를 해결했지만, 이 문제의 의도는 해시를 사용하는 것이다.

해시에 대해 공부를 좀 더 해야할 것 같다.

해시맵 HashMap

자료 출처: https://wikidocs.net/208

사용 예

HashMap<String, String> map = new HashMap<String, String>();
map.put("people", "사람");
map.put("baseball", "야구"); // (key,value) 형태로 사용한다.
map.get("people");			// get메소드로 value를 얻을 수 있다.
map.containsKey("people");	// map에 해당 키가 있는지 조사하고 결과 리턴(true/false)
map.remove("people");		// map의 항목을 삭제하는 메소드. 해당 아이템 삭제 후 value를 리턴한다.
map.size();					// map의 개수를 리턴

Map의 가장 큰 특징은 순서에 의존하지 않고 key로 value를 가져온다.

• LinkedHashMap : 입력된 순서대로 데이터가 출력된다
• TreeMap : 입력된 key의 정렬된 순서 순으로 데이터가 출력된다.

풀이과정 - 2

• HashMap을 이용해서 풀어본다.
• Key는 participant의 이름, value는 해당 이름을 가진 사람 수
• completion배열의 이름 수대로 value를 감소시킨다-> 완료 후 value가 0이 아닌 key를 return

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> map=new HashMap<String, Integer>();
        int value;
        for(String s:participant){
            if(!map.containsKey(s)){
                map.put(s, 1);
            }else{
                value=map.get(s)+1;
                map.put(s, value);
            }
        }
        for(String s:completion) {
                value=map.get(s)-1;
                map.put(s, value);
        }
        for(String s:participant){
            if(map.get(s)!=0)
                answer = s;     
        }
        
        return answer;
    }
}