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

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

1. 코드

import java.util.*;
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.isBlank())
            answer = participant[participant.length - 1];
        return answer;
    }
}

2. 설명

Arrays.sort(participant);
Arrays.sort(completion);

문제를 해결하기 전 우선 정렬을 진행합니다.

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

만약 정렬이 된다면 index 위치에서 비교하면 동일해야하는데 만약 동일하지 않으면 해당 index의 참가자가 완주하지 못한 참가자입니다.

if(answer.isBlank())
    answer = participant[participant.length - 1];

참가자 목록이 완주자 목록에 비해서 1만큼 더 많기에 완주하지 못한 참가자를 반복문 내에서 찾지 못했다면 마지막 참가자 목록에 있는 참가자가 완주하지 못한 참가자입니다.

3. 정리

1. 효율성 검사를 하는 문제이기에 시간 복잡도가 O^2인 방식으로 문제를 해결하면 실패이다.
2. 효율성 검사가 없더라도 최대한 효율적으로 문제를 해결해보자.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges