[프로그래머스 42576번] 완주하지 못한 선수

문제

번호

완주하지 못한 선수 (프로그래머스 42576번)

내용

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

언어

JAVA

 

---

풀이

처음 시도한 코드

처음에는 이중 for문으로 작성하였다. 답을 도출해내는데는 성공했으나 효율성에서 0점... 장렬히 탈락하였다.

for(int i = 0 ; i < participant.length ; i++) {
  for(int j = 0 ; j < completion.length ; j++) {
      if(participant[i].equals(completion[j])) {
          participant[i] = completion[j] = "";
          break;
      }
  }
  if(participant[i] != "") {
      answer = participant[i];
  }
}

return answer;

 

해결방법

2중 for문을 사용할 경우 무조건 $O(n^2)$ 이기 때문에 효율성은 안될 것이다. 결국 반목문을 사용하지 않거나 최대 한번만 사용하는 방식이어야 했다.

비교를 해야하기 때문에 for문을 사용하지 않을 수는 없다. 그렇기에 한번만 사용하여 알파벳 순으로 정렬한 후에 비교하는 방법을 선택하였다.

코드 설명

1. 먼저 <pre>Arrays.sort()</pre>을 통해 <pre>participant</pre>와 <pre>completion</pre>을 정렬한다.
2. 정렬된 array는 미완주자가 전까지는 양쪽 모두 순서가 같게된다.(이름은 동일하기 때문)
3. 두 개의 array의 같은 위치를 비교를 하다가 달라지는 순간이 미완주자이다.
4. <pre>comletion</pre>의 길이가 <pre>participant</pre>보다 작기 때문에 <pre>i</pre>의 최대는 <pre>completion.length</pre>로 한다.
5. <pre>participant</pre>의 마지막 원소가 미완주자일 경우를 대비하여 <pre>if</pre>문을 통해 탐색한다.

 

---

코드

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(!participant[i].equals(completion[i])) {
        answer = participant[i];
        break;
      }
    }

    if(answer == "") {
      answer = participant[participant.length-1];
    }

    return answer;
  }
}

 

생각해보기

만약 길이가 1이상 차이난다면?

새 변수 <pre>number</pre>을 선언하고 <pre>for</pre>안의 <pre>if</pre> 조건을 <pre>!participant[i+number]~</pre>로 두면 될 것이다.