participant 의 배열 중 1명 빼고 모든 선수가 완주함.
이때 완주 선수 배열은 completion.
크게 정렬 vs 해시맵 사용으로 문제 풀이 방식이 나뉜다.
나는 보자마자 이름-참가자수 로 저장하는 해시맵 방식을 떠올렸다.
다만 java 알고리즘 풀이를 익혀가는 과정이니, 정렬 방식도 정리했다.
Arrays.sort()
활용 import java.util.Arrays;
// 1.
// 정렬 후 comple의 참여자 수만큼 돌면서 part에만 있는 참여자 이름 출력
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
// 1. 정렬
Arrays.sort(participant);
Arrays.sort(completion);
// 2. 두 배열이 다른 이름을 찾는다
int i =0; // break 후 바로 return 해주기 위한 전역변수화! ⭐️
for (; i<completion.length; i++){
if(!participant[i].equals(completion[i]))
break;
}
return participant[i];
}
}
HashMap
활용 import java.util.*;
// 2.
// key-value로 저장
// par - com을 해서 value가 0이 아닌 선수 이름 출력
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
// 1. hashmap 만들기(par)
HashMap<String, Integer> map = new HashMap<>();
for(String player: participant)
// getOrDefault: 없으면 1, 있으면 기존 + 1
map.put(player, map.getOrDefault(player, 0)+1);
// 2. map에서 com의 이름을 뺀 후, value가 0이 아닌 선수 이름 출력
for(String player: completion)
// 선수 이름을 가져오되(get), val -1 한 값을 넣어준다(put)
map.put(player, map.get(player)-1);
// keySet() -> map의 key만을 가져오는 배열
for(String key: map.keySet()){
if (map.get(key)!=0){
answer = key;
break; // 찾으면 종료(최적화)
}
}
return answer;
}
}
이 코드의 알고리즘은 다음과 같이 작동
1. participant 배열의 모든 선수를 HashMap에 추가하고, 각 선수의 등장 횟수를 계산합니다.
2. completion 배열의 선수들을 HashMap에서 빼줍니다 (값을 1씩 감소).
3. 마지막으로 HashMap을 순회하며 값이 0이 아닌 (즉, completion에 없는) 선수를 찾아 반환합니다.
이 방법은 O(n) 시간 복잡도로 효율적으로 문제를 해결!
HashMap의 주요 내장 함수
1. put(K key, V value)
- 지정된 키와 값을 HashMap에 추가합니다.
- 이미 키가 존재하면 기존 값을 새 값으로 대체합니다.
- 예: `map.put(player, map.getOrDefault(player, 0)+1);`
2. getOrDefault(Object key, V defaultValue)
- 지정된 키에 매핑된 값을 반환하거나, 키가 없으면 기본값을 반환합니다.
- 예: `map.getOrDefault(player, 0)`
3. get(Object key)
- 지정된 키에 매핑된 값을 반환합니다. 키가 없으면 null을 반환합니다.
- 예: `map.get(player)`
4. keySet()
- HashMap의 모든 키를 포함하는 Set을 반환합니다.
- 예: `for(String key: map.keySet())`
코드에는 없지만 유용한 메서드
1. containsKey(Object key)
- HashMap에 지정된 키가 포함되어 있는지 확인합니다.
2. size()
- HashMap에 포함된 키-값 쌍의 수를 반환합니다.
3. remove(Object key)
- 지정된 키와 연관된 값을 제거합니다.
entrySet().iterator()
활용⭐️ iterater 아니고 iterator 주의
위 로직과 동일, 단 key를 순회할때, KeySet 대신 EntrySet을 활용함.
EntrySet은 반복문에서 성능이 더 좋지만, Iterator 클래스에 대한 이해 필요.
가령, hasNext() 메소드나 next() 메소드 등 알고있어야 풀이 가능.
// 3.
// key-value로 저장
// par - com을 해서 value가 0이 아닌 선수 이름 출력
// entrySet 활용
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
// 1. hashmap 만들기(par)
HashMap<String, Integer> map = new HashMap<>();
for(String player: participant)
// getOrDefault: 없으면 1, 있으면 기존 + 1
map.put(player, map.getOrDefault(player, 0)+1);
// 2. map에서 com의 이름을 뺀 후, value가 0이 아닌 선수 이름 출력
for(String player: completion)
// 선수 이름을 가져오되(get), val -1 한 값을 넣어준다(put)
map.put(player, map.get(player)-1);
// 반복문에서 성능이 더 좋은 entrySet 활용
Iterator<Map.Entry<String, Integer>> iter = map.entrySet().iterator();
while(iter.hasNext()){
Map.Entry<String, Integer> entry = iter.next();
if(entry.getValue()!=0){
answer=entry.getKey();
break;
}
}
return answer;
}
}