[코딩테스트-JAVA]완주하지 못한 선수 풀이 - 초보도 이해하는 풀이(프로그래머스)

안녕하세요

인포돈 입니다.

프로그래머스 완주하지 못한 선수 풀이입니다. 

* 참고사항
 - 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"

 

실패 코드 1

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        boolean[] check = new boolean[participant.length];
        
        for(int i = 0 ; i < completion.length ; i++){
           Loop1 : for(int j = 0 ; j < participant.length ;j++){
                if(!check[j]&&completion[i].equals(participant[j])){
                    check[j]=true;
                    break Loop1;
                }
            }
        }
        
        for(int i = 0 ; i < participant.length ; i ++){
            if(!check[i])
                answer = participant[i];
        }
        
        
        
        return answer;
    }
}

실패 코드 1의 경우 반복문에 LOOP1 : 을 통해서 반복문을 되돌아오는 방법을 사용하였습니다. 정확도는 다 통과를 하였지만, 효율성에서 0점을 받아서 무엇이 문제인지 생각해볼 필요가 있었습니다.

 

기본적인 생각은 아마 중첩 반복문을 이용하여 시간이 초과된 것으로 생각이 됩니다.

 

실패 코드 2

import java.util.*;


class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        ArrayList<String> list = new ArrayList<>(Arrays.asList(participant));
        
        for(int i = 0 ; i < completion.length ; i++){
            list.remove(completion[i]);
        }
        
        answer=list.get(0);
        
        return answer;
    }
}

실패 코드 2의 경우 ArrayList를 이용해서 해당 값을 삭제한 후 남은 값을 반환해 주는 방식을 이용했습니다. 해당 방식은 반복문을 1번만 사용한다고 생각하고 작성하였지만, 찾아보니 ArrayList의 시간 복잡도가 O(n)이 되어, 결론적으로는 중첩 반복문과 같은 시간 복잡도를 가지게 된다고 볼 수 있습니다.

 

성공 코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Arrays.sort(participant);
        Arrays.sort(completion);
        int i;
        for (i = 0; i < completion.length; i++) {
            if(!participant[i].equals(completion[i])) {
                return participant[i];
            }
        }
        return participant[i];
    }
}

마지막 성공 코드는 바로 배열 정렬을 활용한 방법 해당 코드는 각 배열을 정렬한 후에 같지 않은 값을 가지면, 해당 값을 반환해주는 코드입니다.

 

뭐 배열 정렬은 기본적으로 O(nlog n) ~ O(n^2)의 시간 복잡도를 갖게 되는데, 아마 테스트 밴치에는 n^2까지 가는 테스트가 없기에 효율성 측면에서 만점을 받을 수 있었다고 생각합니다.

 

시간적인 측면으로 볼 때는 앞서 실패 코드 2에서 ArrayList대신 LinkedList를 활용하면, 더욱 효율적인 면을 보일 수 있습니다. 

---

participant, completion배열 정렬

-> 정렬한 배열들을 반복문을 통해 비교한 후 다르면, 해당 문자열 반환

(해당 알고리즘이 가능한 이유는 정렬을 통해서 달라지는 지점이 해당 선수가 완주하지 못했음을 알리기 때문이다.)

---

STEP1 반복문 LOOP 설정 방법

        for(int i = 0 ; i < completion.length ; i++){
           Loop1 :  for(int j = 0 ; j < participant.length ;j++){
                if(!check[j]&&completion[i].equals(participant[j])){
                    check[j]=true;
                    break Loop1;
                }
            }
        }

LOOP1 : 는 아주 간단한 중첩 반복문 기법으로 break와 주로 같이 쓰이며, 대게 break는 해당 반복문을 나가게 됩니다. 뭐 굳이 LOOP1을 사용하지 않아도 되지만, Loop1을 활용하여 2중 for문을 한 번에 탈출이 가능하기 때문에 학습을 위해 사용해 보았습니다.

 

여기서 Loop1은 사용자 설정에 따라 다르게 지정할 수 있습니다.

 

STEP2 ArrayList vs LinkedList 메서드 시간 복잡도

ArrayList 메서드 시간 복잡도

add : O(1)

remove : O(n)

get : O(1)

Contains : O(n)

iterator.remove : O(n)

 

LinkedList 메서드 시간 복잡도

add : O(1)

remove : O(1)

get : O(n)

Contains : O(n)

iterator.remove : O(1)

 

다시 생각해보면 실패 코드 2에서 LinkedList를 활용하여 remove를 해주면, 효율성을 어느 정도 만족할 거라 생각합니다.

 

STEP 3 배열 정렬

뭐... 배열 정렬은 너무 유명하고 간단해서 import를 통해 Arrays를 추가해 주시고, Arrays.sort(배열)을 넣어주시면 자동으로 정렬이 됩니다. 여기서 기억하셔야 할 점은 시간 복잡도가 O(nlog n) ~ O(n^2)의 값을 갖게 되고 최악의 경우 n^2이 되어 2중 포문과 같은 시간 복잡도를 가지는 것을 기억하셔야 합니다.

 

더 나아가 배열 정렬에서 이용되는 정렬 방법은 퀵 정렬을 이용한다고 생각하시면 됩니다.