[프그스] Lv.1/해시/완주하지 못한 선수

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

 

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

• Participant 배열로는 N명의 참가자의 이름이 들어있고, Completion 배열에는 N-1명의 완주자들이 있다.
• 그 한 명을 찾으면 되는 아주 간단한 문제이다
• 두가지 배열이 있는데 participant에는 있고, completion에는 없는 것을 찾는다!

🧩확장 for문 for(타입 변수명 : 배열명or컬렉션){  }

방법1. Sorting/Loop 사용하기

sort(정렬)를 해주고 completion의 길이만큼 participant와 다 비교 해본다.

0번인덱스에 있는 선수들이 같은지, 1번인덱스에 있는 선수들이 같은지 .. 보다가

어느순간부터 선수가 달라진다 이 때 participant에는 있는 선수가 완주를 못하였구나 하고 알 수 있다.

 

그런데 ! 예외처리가 있다!

알파벳 순서상 마지막에 오는 선수(sorting되어져있는 마지막 선수)가 완주를 못했을 경우에는 비교가 안됀다.

completion의 길이만큼 비교하기 때문에 (participant의 길이 = completion+1 길이)

 

Java에서 sorting하기 = Arrays.sort() / import java.util.Arrays;

1. 두 배열을 정렬(sorting)한다.

Arrays.sort(participant);

Arrays.sort(completion);

2. 두 배열이 다를 때까지 찾는다.

for(int i =0;i<completion.length;i++){

   if(!participant[i].equals(completion[i]))

       return participant[i];

 

------------↓예외처리를 위한 코드 수정↓------------

int i = 0;

for(;i<completion.length;i++){

   if(!participant[i].equals(completion[i]))

       break; //그때 그 i 값을 

return participant[i]; //return

 

3. 여기까지 왔다면 마지막 주자가 완주하지 못한 선수이다.(예외처리)

즉 두 배열을 다 비교해서 못찾았다는 것은 알파벳순서상 (sorting된 순서상) 마지막에 있는 선수가 완주하지 못한 것을 알 수 있다.

return participant[i];

import java.util.Arrays;

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

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

 

 

🧩[map] getOrDefault ( key, defaultValue )

: 찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 메서드

map.getOrDefault(player,0) 

→ map에서 player라는 키를 가진 값을 가져다달라는 의미,

만약에 map에 player라는 키가 아직 없다면, 0을 가져달라는 의미이다.

방법2. hash 사용하기

hash =  키와 밸류의 조합(map)

participant에서 각 key의 value값을 1로 할당을 해놓고

completion에서 각 key의 value값을 하나씩 빼주면 

value가 0이 아닌 선수를 찾으면 정답이 되겠다!

 

1.Hashmap을 import해준다

import java.util.HashMap

 

2.Hashmap을 만든다(participant배열을 기반으로)

HashMap<String,Integer> map = new HashMap<>();

2-1. participant에 있는 모든 선수의 이름을 더해준다.

for(String player : participant) player를 하나씩 꺼내올텐데

map.put(player, map.getOrDefault(player,0)+1)

이 때 map에 키='player', 밸류=이전값의 증감값 을 넣어준다. (동명이인이 있을 수 있기 때문에)

                                 이 때는getOrDefault함수를 쓰면 좋다.

map.getOrDefault(player,0) → map에서 player라는 키를 가진 값을 가져다달라는 의미이다.

만약에 map에 player라는 키가 아직 없다면, 0을 가져달라는 의미이다.

 

3.Hashmap을 꺼내온다(completion배열을 기반으로)

이것또한 마찬가지로 map에 값을 넣어줄테넫

이떄는 get만 써도 될것

기존에 있던값에서 -1해서 다시 map에 넣어라

map.put(player, map.get(player)-1);

 

4. 남은 value가 0이 아닌 마지막 주자를 찾는다.

keyset = 맵이 가지고있는 key를 하나씩 꺼내서 하나의 배열로 담아준다.

//System.out.printlnt(map.keySet()); // [leo,eden, kiki]

그배열에서 하나씩 꺼내서 key에 담아서 비교하려고한다

for(String key : map.keySet()){

if(map.get(key))

}

 

출처: 

https://coding-grandpa.tistory.com/entry/프로그래머스-완주하지-못한-선수-해시-Lv-1 [개발자로 취직하기]

https://www.youtube.com/watch?v=_2yD46UxSso&list=PLlV7zJmoG4XI9VguUVNMu3pCjssb4aR_0