⚠️JAVA 언어를 사용합니다.
간단해 보이는데 너무 헤매서 가져왔다.
🔒문제
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
입출력 예
| participant | completion | return |
| ["leo", "kiki", "eden"] | ["eden", "kiki"] | "leo" |
| ["marina", "josipa", "nikola", "vinko", "filipa"] | ["josipa", "filipa", "marina", "nikola"] | "vinko" |
| ["mislav", "stanko", "mislav", "ana"] | ["stanko", "ana", "mislav"] | "mislav" |
🗝️정답
import java.util.Arrays;
class Solution {
public String solution(String[] participant, String[] completion) {
Arrays.sort(participant);
Arrays.sort(completion);
int i;
for(i=0; i<completion.length; i++){
if(!participant[i].equals(completion[i])){
break;
}
}
return participant[i];
}
}
💡풀이해석
- 참가한 선수 문자열 배열에서 완료한 선수 배열을 뺀 나머지 딱 한명만 찾으면 되므로 정렬한 뒤, 같은 인덱스일 떄 두 배열의 값이 달라지는 순간을 찾으면 된다.
// 기초 작업
- Arrays.sort() : 두 배열 모두 정렬해준다.
- int i : 만약 반복문이 끝나도 달라지는 값을 값지 못하면 참가한 선수 배열의 맨 마지막 인덱스에 있는 것이므로 반복문을 나온 뒤 처리해주어야 한다. (outofindex 예외때문에 더 작은 길이만큼만 반복문 사용해야됨) 때문에 인덱스 사용 범위를 메소드 전체로 해준다.
//반복하며 다른 값 찾기
- for(i=0; i<completion.length; i++) : 더 작은 길이만큼 즉, 완료한 선수 배열의 길이 만큼만 반복한다.
- if(!participant[i].equals(completion[i])) : 같은 인덱스인 두 배열의 값이 달라지는 순간 반복문 종료 즉, 인덱스의 카운팅을 멈춤
//반환
- return participant[i] : 값이 달라진 인덱스에 있는 참가자 반환
✏️자기 분석
진짜 간단한건데 생각을 잘못해서 뻘짓한 문제.
첫 번째 풀이
import java.util.LinkedList;
import java.util.Arrays;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
LinkedList<String> retire = new LinkedList<>(Arrays.asList(participant));
for (int i = 0 ; i < completion.length ; i++) {
if (retire.contains(completion[i])) {
retire.remove(completion[i]);
}
}
answer = retire.get(0);
return answer;
}
}처음엔 리스트에 참가자를 다 넣은 다음 완료한 사람을 하나씩 제거하려고 했다. 특히 문제 분류에 해시라고 되어있어서 제네릭을 써야되는 줄 알았다;;
시간이 너무 오래걸렸다.
두 번째 풀이
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public String solution(String[] participant, String[] completion) {
Arrays.sort(participant);
Arrays.sort(completion);
int start=0, len=completion.length, i=len/2;
for(String s: completion)
System.out.print(s+" ");
System.out.println();
for(String s: participant)
System.out.print(s+" ");
while(true){
System.out.println(len);
if(participant[i].equals(completion[i])){
System.out.println("same "+i);
if(len==1)
return participant[i+1];
start = i;
}else{
System.out.println("dif "+i);
if(len==1)
return participant[i];
}
len = len/2;
i = start+len/2;
}
//return "";
}/*
for(String s: completion)
System.out.print(s+" ");
System.out.println();
for(String s: participant)
System.out.print(s+" ");
List<String> comp = new ArrayList<> ();
for(String s: completion)
comp.add(s);
for(String s: participant){
if(!comp.contains(s))
return s;
else
comp.remove(s);
}
return answer;
}*/
}밑에 주석이 첫 번째 풀이에 대한 미련이다. 즉, 뻘짓한 흔적. 그냥 남기고 싶었다..ㅋ
처음부터 정답에 있는대로 도전해봤으면 이런 뻘짓도 안했을 터인데..
한번 시간제한을 보고 나니 하나씩 비교했다가 마지막 인덱스까지 가면 시간이 너무 오래 걸릴까봐 범위를 절반씩 줄여가며 검사를 하려고 했다. 풀이는 대충 다음과 같다.
- 두 배열을 정렬한 뒤, 배열 길이의 중간 인덱스에 있는 두 문자가 같다면, 서로 달라지는 순간은 중간 인덱스보다 뒤에 있을 것이다. 그럼 뒤쪽 인덱스부터 맨 끝까지의 범위 중 중간값을 비교한다.
- 중간 인덱스의 두 문자가 다르다면, 앞쪽에 서로 달라진 순간이 있는 것이고 완주하지 못한 선수가 중간 인덱스의 값보다 앞쪽에 있다.
- 이렇게 번위를 절반씩 줄여가며 달라진 순간을 찾는다.
나름 이름도 있는 탐색 방법이다. (이름이 뭔진 기억나지 않음) 때문에 테스트 케이스는 잘 통과했지만, 채점에는 실패했다. 이유는 위와 같은 상황 때문.
동명이인에 대한 예외를 생각하지 못했다. 동명이인이 2명일 수는 있다고 생각했으나, 저렇게 많은 동명 이인이 있다면 달라진 순간이 앞쪽에 있음에도 불구하고 중간 값이 같으므로 뒤쪽의 범위에서 찾게된다. 당연히 영원히 찾지 못할 것이다.
세 번째 풀이(정답)
역시 하나씩 비교하다보니 시간이 조금 걸리긴 하지만, 효율성이 나쁘진 않나보다.
🚩결론
1. 예외 처리 확실히하기 == 문제 잘 읽기
2. 다양한 생각과 방식으로 푼 것은 좋다.
3. 하지만, 너무 복잡하게 생각하지 말자. 특히 분류에 너무 연연하지 말자.
