22-12-15 코딩테스트 해쉬#1 (완주하지 못한 선수)

해쉬와 정렬을 활용한 완주하지 못한 선수 찾기

Soring

 

+문제 분석

1. Soring
   두 list를 sorting 한다.
2. 비교
   completion list의 length 만큼 돌면서 participant에만 존재하는 한 명을 찾는다.
3. 마지막 주자
   list를 전부 다 뒤져도 답이 없다면, participant의 완주하지 한 선수이다.

import java.util.Arrays;

class Solution04{
    public String solution(String[] participant, String[] completion){
        String answer="";
        // 1. 두 배열을 정렬한다.
        Arrays.sort(participant);
        Arrays.sort(completion);

        // 2. 두 배열이 다를 때까지 찾는다.
        int i=0;
        for(; i<completion.length;i++){
            if(!participant[i].equals(completion[i])){
                break;
            }

        }

        // 3. 여기까지 왔다면, 마지막 주자가 완주하지 못한 선수다.

        return participant[i];
    }

    public static void main(String[] args) {
        String[] part={"leo","kiki","eden"};
        String[] comp ={"eden","kiki"};
        Solution04 sol = new Solution04();
        System.out.println(sol.solution(part, comp));
    }
}

Hash

• 키와 벨류의 조합, 예)전화번호부 = 철수(키): 전화번호(벨류)
  

  

1. Hash 만들기
   Key에 선수의 이름을, Value의 conut를 갖는 Hash Map을 만든다.
2. Hash 빼기
   completion에 존재하는 선수들의 Hash를 뺀다.
3. 마지막 주자
   Value가 남아있는 선수가 완주하지 못한 선수이다.

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

class Solution04{
    public String solution(String[] participant, String[] completion){
        String answer="";
        // 1. hash map을 만든다 (participant)
        HashMap<String, Integer> map = new HashMap<>();
        for(String player : participant){
            //getOrDefault : 여러사람이 존재할 경우 쓰기좋은 함수
            //               이 맵에서 플레이어 라는 키르 가진 값을 가져와라
            //               이 맵에 플레이어가 없다면 0을 달라. 또한 벨류값을 지정 
            map.put(player, map.getOrDefault(player, 0)+1);
        }


        // 2. hash map을 뺀다. (completion)
        for(String player : completion){
            map.put(player, map.get(player)-1);
        }
        // 3. value가 0이 아닌 마지막 주자를 찾는다.
        // keySet() 사용

        // map.keySet() : 이 맵이 가지고 있는 키 값을 하나씩 가지고 온다.
        // for(String key : map.keySet()){
        //     if(map.get(key)!=0){
        //         answer=key;
        //         break;
        //     }
        // }

        // Iterator 사용
        // 반복을 쉽게 해주는 하나의 클래스
        Iterator<Map.Entry<String, Integer>> iter= map.entrySet().iterator();

        // 여러개의 iter라는 객체에서 다음 객체가 존재하냐 안하냐 확인
        while(iter.hasNext()){
            Map.Entry<String,Integer> entry = iter.next();
            if(entry.getValue()!=0){
                answer=entry.getKey();

                break;
            }
        }


        return answer;


    }

    public static void main(String[] args) {
        String[] part={"leo","kiki","eden"};
        String[] comp ={"eden","kiki"};
        Solution04 sol = new Solution04();
        System.out.println(sol.solution(part, comp));
    }
}