완주하지 못한 선수(효율성 실패)

코딩 테스트의 문제 완주하지 못한 선수를 풀어보았다.

 

programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

package Unfinished_player;
import java.util.ArrayList;
class Solution2 {
    //효율성 0점..... 10만명의 마라토너를 모두 비교하기에는 list의 효율이 구리다. 매번 값을 지우고 당기고 해야되서
    public String solution(String[] participant, String[] completion) {
        ArrayList<String> unfinished = new ArrayList<String>();     
        
        for(String in : participant) {
            unfinished.add(in);
        }
        
        for(int i=0;i<completion.length;i++) {
            
            int count=0;
            
            for(int j=0;j<completion.length;j++) {
                
                if(participant[i].equals(completion[j])) {
                    unfinished.remove(0);
                    completion[j]=null;
                    break;    
                }
                count++;
            }
            if(count==completion.length) break;
        }
        
        String answer = unfinished.get(0);
        
        return answer;
    
    }
}
public class player2 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String []participant = {"mislav", "stanko", "mislav", "ana"};
        String []completion ={"stanko", "ana", "mislav"};
        String []participant2 = {"marina", "josipa", "nikola", "vinko", "filipa"};
        String []completion2 ={"josipa", "filipa", "marina", "nikola"};
        Solution2 a = new Solution2();
         System.out.println(a.solution(participant, completion));
        
    }
 
}
 

ArrayList를 사용해서 participant배열의 value를 저장시키고 완주한 선수들을 비교해서 remove 명령어로 지웠더니

 

정확성 측면에서는 100점이지만 효율성 측면에서는 0점을 맞았다. 

 

그럴만도 한게 문제에서 보면 참가자들은 최대 10만명까지 있는데 arraylist는 중간에 value를 지우면 이후 데이터는 빈

 

곳을 채우기 위해서 앞으로 당겨지기 때문에 만약 index 3의 데이터가 완주한 선수라면 99997개의 데이터가 왼쪽으로

 

이동해야 할 것이다. 이는 알고리즘에서 Time complexity를 증가 시키기 때문에 돌아가지만 좋지못한 코드가 된다.

 

만약 전자사전에서 zoo를 검색하는데 오랜시간이 걸린다면 아무도 그 사전을 이용하지 않을 것이다. 자바는 Time

 

complexity를 줄이는 방안으로 순서에 구애받지 않는 hash를 구현해놨다. 이를 활용해서 문제를 다시 풀어보자.