[프그스] Lv.1/해시/완주하지 못한 선수
https://programmers.co.kr/learn/courses/30/lessons/42576
코딩테스트 연습 - 완주하지 못한 선수
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수
programmers.co.kr
- 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