[Programmers/프로그래머스] #1. 완주하지 못한 선수

[문제]

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 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
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

---

언어 : java

[1] 문제 파악

입출력 예를 보면 parcitipant의 경우 단어들이 무질서하게 나열되있지만 completion의 경우 단어가 오름차순으로 정렬되있는 것을 확인할 수 있다.

또한 3번째 행의 예를 보면 parcitipant의 경우 'mislav'의 경우 2개가 있지만 completion의 'mislav' 는 1개가 있으므로 한개를 제외한 mislav가 반환되는 것을 확인 할 수 있다.

[2] 나의 풀이

프로그래머스의 코딩 테스트는 단순히 결과만 나왔다고 해서 합격할 수 없다. 

알고리즘의 복잡도, 즉 '시간복잡도' 라는 것을 고려해 줘야 한다.

이 시간복잡도를 최소한으로 하기 위해선 for문을 사용시 이중이상의 for문의 사용을 지양해야 한다.

맨 처음 문제를 받았을 시 '한개를 기준으로 하나하나 비교해가야지' 라는 생각이 들 것이다. 

그렇게 한다면 시간복잡도가 높아져 테스트에 합격할 수 없다.

이러한 문제를 풀 시에 많이들 접근하는 방법이 Arrays.sort를 이용해 배열을 오름차순으로 정렬 후,

값이 같지 않은 값을 리턴하는 방법을 많이 쓴다.

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        //1. 배열을 오름차순으로 정렬
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        //2. 정렬 후 값을 비교해 리턴
        for(int i=0; i<participant.length;i++)
        {
           if(i==(participant.length)-1&& answer.length() == 0)           
               answer= participant[i];
           else {
                if(!(participant[i].equals(completion[i])))                
                {   answer=participant[i]; 
                    return answer;
                }
           }                   
        }
        return answer;
    }
}

for문 안에 if문이 있는데 이는 1행의 예와 같이  completion의 값을 다돌고 participant의 마지막 값을 확인할 때 나는 boundaryexception을 방지하고자 넣어준 코드이다.

answer에 담긴값이 없을 경우 participant의 마지막 열값을 answer에 대입해주는 코드이다.

본인이 만들었지만 솔직히 틀린 코드라고 적어주고싶다. 위의 입출력 예제와 같이 participant와 completion의 배열길이의 차이가 1이 날경우에는 상관없지만  2이상으로 차이날 경우...

저코드는 틀린 코드가 된다.

프로그래머스의 예제가 배열길이의차이가 1정도밖에 안나는 예제밖에 없어 저 코드가 합격된거 같다.

이 글을 보고 도전하시는 분들은 테스트케이스를 추가하셔서 2이상 차이가 날경우 return 하게 만드시는 도전을 해봤으면 좋겠습니다.