[Java] 프로그래머스 : 완주하지 못한 선수(Hash)

https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

 

 

HashMap

 ·  데이터 관리/유지 자료구조

 ·  Map 인터페이스를 구현한 대표적인 Map 컬렉션

 ·  ArrayList는 내부 인덱스를 이용하여 한번에 검색이 되기에 빠른 속도를 보장하나

   데이터 추가/삭제시 데이터가 밀려 많은 시간이 소요되므로 이를 극복하기 위해 제시된 방법이 Hash

 ·  Hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도

 ·  Hash Table : key(인덱스), value(hash 값)

       key : key값은 중복되지 않음 > 같은 key값을 넣으면 이전 값은 사라지고 나중에 넣은 값만 남음

       value : key로 매핑했을 때 나오는 값

// 생성
HashMap<String,Integer> hash = new HashMap<String,Integer>();

hash.put(key, value);		// 추가(생성할때 넣은 타입으로 추가)
hash.remove(1);			// key값이 1인 hash 제거
hash.clear();			// 모든 값 삭제
hash.get(1);			// key값이 1인 value 가져오기
hash.getOrDefault("A", 0);	// Key값이 A에 해당하는 Value를 가져오고, 아닐 경우 Default를 0으로 지정
hash.keyset();			// Key값을 다 받아옴
hash.entryset();		// map에서 정의된 key값과 value값을 다 가져옴

 

 

문제

 

*  해시를 사용하지 않은 코드

참가자와 완주자를 오름차순으로 정렬하여 for문을 돌려가며 순서대로 비교하였을때

이름이 같지 않는 순번의 참가자쪽은 완주하지 못한 사람.

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

 

 

* 해시를 사용한 코드

https://goodthinking.tistory.com/m/51 참고

import java.util.HashMap;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        HashMap<String, Integer> hash = new HashMap<>();
        
        // runner가 participant 수 만큼 반복
        for(String runner : participant){
            // HashMap key값이 runner와 일치하면 
            // put을 통해 runner > String, hash.get(runner) + 1 > Integer로 추가
            // 불일치하면 1의 값만 남기고 넘어가게된다.
            if(hash.containsKey(runner)){
                hash.put(runner, hash.get(runner) + 1);
            }else {
                hash.put(runner, 1);
            }
        }
        
        // 다시 for문으로 goal을 completion만큼 반복하며 -1 추가
        for(String goal : completion){
            hash.put(goal, hash.get(goal)- 1);
        }
        
        // for문으로 다시 runner를 반복하면서 runner 가 0이 아닌경우 완주하지 못한 선수로
        // 인지하고 answer에 대입합니다
        for(String runner : participant){
            if(hash.get(runner) != 0){
                answer = runner;
            }
        }
        
        return answer;
    }
}