programmers.co.kr/learn/courses/30/lessons/42576
코딩테스트 연습 - 완주하지 못한 선수
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수
programmers.co.kr
참가자 배열 String[] participant, 완주자 배열 String[] completion이 주어진다.
참가자들 중 완주하지 못한 선수가 1명 존재할 때 이 선수의 이름을 반환하는 문제.
해시 태그로 분류되었지만 정렬만으로도 풀 수 있다.
풀이 1.
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
Arrays.sort(participant);
Arrays.sort(completion);
for(int i = 0; i < completion.length; i++) {
if(!participant[i].equals(completion[i])) {
answer = participant[i];
break;
}
// completion의 마지막까지 전부 같다면 남은 한 명이 정답
if(i == completion.length - 1) {
answer = participant[i + 1];
}
}
return answer;
}
}Arrays.sort()를 사용해 두 배열을 모두 정렬한 후 원소들을 차례로 비교한다.
다른 원소가 등장하는 순간 그 놈이 정답. 반복 종료.
마지막 원소까지 모두 같다면 participant에 남은 마지막 원소가 정답.
풀이 2.
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
Map<String, Integer> hm = new HashMap<String, Integer>();
// 참가자 수만큼 value 증가
for(String p : participant) {
// 동명이인을 고려해야한다
if(hm.get(p) == null) {
hm.put(p, 1);
}else {
hm.put(p, hm.get(p) + 1);
}
}
// 완주자 수만큼 value 감소
for(String c : completion) {
hm.put(c, hm.get(c) - 1);
}
// value가 1인 key가 정답
for(String key : hm.keySet()) {
if(hm.get(key) == 1) {
answer = key;
break;
}
}
return answer;
}
}HashMap 사용한 풀이.
참가자 수만큼 Map.entry의 value를 1씩 증가시킨다. 이때 동명이인 존재하는 경우까지 고려해야한다.
그 후 완주자 수만큼 value를 1씩 뺀다.
value가 1인 key가 완주하지 못한 선수.
'알고리즘 문제 > 프로그래머스' 카테고리의 다른 글
| [PG] 기능 개발 JAVA (0) | 2020.12.28 |
|---|---|
| [PG] 주식 가격 JAVA (0) | 2020.12.28 |
| [PG] 베스트 앨범 JAVA (0) | 2020.12.28 |
| [PG] 위장 JAVA (0) | 2020.12.27 |
| [PG] 전화번호 목록 JAVA (0) | 2020.12.27 |