[코딩테스트연습] 완주하지 못한 선수
- 최종코드
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
ArrayList<String> participantList = new ArrayList<String>(Arrays.asList(participant));
ArrayList<String> completionList = new ArrayList<String>(Arrays.asList(completion));
Collections.sort(participantList);
Collections.sort(completionList);
for(int i = 0 ; i < completionList.size() ; i++) {
if(!completionList.get(i).equals(participantList.get(i))){
return answer = participantList.get(i);
}
}
//for문에서 답이 나오지않은 경우, 배열의 마지막 참가자가 곧 완주하지 못한선수
answer = participantList.get(participantList.size()-1);
return answer;
}
}
- 중간코드
import java.util.Arrays;
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(!completion[i].equals(participant[i])){
return answer = participant[i];
}
}
//for문에서 답이 나오지않은 경우, 배열의 마지막 참가자가 곧 완주하지 못한선수
answer = participant[participant.length-1];
return answer;
}
}
- 실패코드
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
for(String n : participant) {
if(!isComplete(n, completion)) {
answer = n;
break;
}
}
return answer;
}
public boolean isComplete(String s, String[] c) {
for(int i = 0 ; i < c.length ; i++) {
if(s.equals(c[i])) {
c[i]=""; //동명이인 선수 방지
return true;
}
}
return false;
}
}
- 최종코드와 중간코드의 테스트 결과
- 막혔던점 & 해결방법
- 실패코드로는 정확성 테스트에서 통과하였으나 효율성 테스트에서 실패하였다. participant배열과 completion배열이 아주 큰 경우 이중 for문으로 인해 시간 복잡도는 O(n²)이므로 시간 초과가 된 것이다. 이를 해결하기 위해 이중 for문을 제거하고 completion의 길이가 participant의 길이보다 1 작으므로, 각각의 배열을 정렬한 후 같은 위치의 값을 비교하여 일치하지 않는 경우를 찾도록 수정하였다.
- 중간코드로 효율성 테스트를 통과하였으니 여기서 멈추어야겠지만, 좀 더 시간을 줄일 수 있는 방법에 대해 고민하였다. Arrays클래스의 기본 제공 sort() 메소드는 Dual-Pivot Quicksort방식으로 정렬을 하므로 평균 O(nlog(n))의 시간복잡도를 가지며 최악의 경우 O(n²)이 된다. 반면 Collections클래스의 기본 제공 sort() 메소드는 Timsort방식으로 삽입 정렬과 합병정렬을 결합하여 만든 정렬방식이다. Timsort의 시간복잡도는 평균 O(nlog(n)) 이며 최악의 경우도 O(nlog(n))이다. 정렬방식의 변경을 통해 좀더 나은 효율성을 확보하였다.
- 아쉬운점
효율성 테스트에서 보듯 정렬방식의 변경으로는 최대 약30%에 불과한 속도 향상이 있었다. 좀 더 공부를 하여 더 나은 방식으로 더 많은 시간을 단축시켜보고싶다.
Author And Source
이 문제에 관하여([코딩테스트연습] 완주하지 못한 선수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lastella/코딩테스트연습-완주하지-못한-선수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)