[algo] 완주하지 못한 선수 - 해시

완주하지 못한 선수

모든 알고리즘은 로컬에서 테스트 하면서 진행한다. (구조가 다를 수 있음)

1. 풀이

package com.company;
import java.util.*;
public class Main {
        public static String solution(String[] participant, String[] completion) {
            String answer = "";
            Arrays.sort(participant);
            //배열 생긴대로 출력해볼때 함
            //System.out.println(Arrays.deepToString(completion));
            Arrays.sort(completion);
            int i = 0;      //a
            for (i = 0; i < completion.length; i++) {
                if (!participant[i].equals(completion[i])) {
                    System.out.println(participant[i]);
                    return participant[i];
                }
            }
            return participant[i];
        }
    public static void main(String[] args) {
        String[] participant = {"11", "22", "33"};
        String[] completion = {"11", "33"};
        solution(participant, completion);
    }
}

Arrays.sort() 를 이용해서 정렬하여 앞에서 부터 차례대로 비교해보면 일치하지 않는 사람들 return 할 수 있다.

2. Hash란?
먼저 해시란 데이터를 이용하여 속도를 높일 수 있는는 key, value의 형태의 Map 인터페이스의 한 종류이다.
key는 값이 중복되어서는 안되며, value는 중복을 허용한다. 데이터들을 해시함수를 걸쳐서 해시테이블에 넣음으로서 인덱싱된 키를 가지고 데이터를 비교하기 때문에 비교속도가 빠르다고 할 수 있다.

<생성자와 메서드 정리표>

기본적으로 맵을 선언하고 HashMap을 불러온다. Map map = new HashMap()
데이터 저장은 map.put(11,"aa")
데이터 불러오기는 map.get(11)

3. 최종 풀이
   해시맵에 key에는 참가자의 이름, value에는 완주여부를 나타내어 표현하는데 participate 명단에 들어와있다면 +1 completion명단에 있으면 -1을 해주어 최종적으로 마라톤을 완주한 사람은 0 완주하지 않은 사람은 1로 구분되어진다.

package com.company;
import java.util.*;
public class Main {
        public static String solution(String[] participant, String[] completion) {
            String answer = "";
            Map<String, Integer> map = new HashMap<String, Integer>();
            for(String part: participant) {
                map.put(part, map.getOrDefault(part, 0) + 1);
                System.out.println(map.toString());
            }
            for(String comp: completion) {
                map.put(comp, map.getOrDefault(comp, 0) - 1);
                System.out.println(map.toString());
            }
            for (String key : map.keySet()) {
                if (map.get(key) != 0){
                    answer += key ;
                }
            }
            return answer;
        }
    public static void main(String[] args) {
        String[] participant = {"11", "22", "33"};
        String[] completion = {"11", "33"};
        solution(participant, completion);
    }
}

getOrDefault() 는 key값이 없다면 입력시 설정한 default값을 반환해주는 함수다.
keySet()은 모든key를 가져오게 되어 [11, 22, 33] 이런형태이고
entrySet()은 key, value 다 가져와 [11=0, 22=1, 33=0] 이런 형태이다.

출력해보면
{11=1}
{11=1, 22=1}
{11=1, 22=1, 33=1}
{11=0, 22=1, 33=1}
{11=0, 22=1, 33=0}

22
이렇게 깔꼼하게 공통되지 않는 부분만 1로 나오게되어 value값이 1인것만 return 하게된다!