완주하지 못한 선수

딱히 할게 없을때는 알고리즘 문제를 풀면서 시간을 보내보도록 하려구 합니다.

프로그래머스에서 나온 문제들을 하나씩 풀면서 알고리즘을 공부하겠습니다.

알고리즘을 잘 못하기때문에 쉬운거부터 하나씩 풀어가면서 문제를 풀어보도록 하죠!

(참고로 Java를 사용합니다.)

[문제 Lv.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는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

[문제 풀이]

import java.util.*;

class Solution {

    public String solution(String[] participant, String[] completion) {

        String answer = "";        

        Arrays.sort(participant);   //참가자를 이름 순으로 정렬 합니다.

        Arrays.sort(completion);  //완주자를 이름 순으로 정렬 합니다.

        /*참가자와 완주자를 배열 0부터 하나씩 비교합니다. */

         for(int i=0; i<completion.length; i++) { 

        if(participant[i].equals(completion[i])==false) {  

        answer=participant[i];  //만약 참가자 배열[i] 완주자 배열[i]이 동일하지 않은 위치가 완주하지 못한 선수

        break;

        }else

    answer = participant[i+1];  // 완주하지 못한 선수가 정렬시 참가자 배열에서 마지막에 위치한 경우

        }     

        return answer;

    }

}

실행 시간은 O(n)