완주하지 못한 선수

자바의 정석 1권을 공부한 후에 2권을 공부하려고 계획하고 있었는데 스프링과 알고리즘도 어느정도 공부해 놓고 시간이 혹시 남는다면 보는게 좋을 것 같다는 생각이 들었다. 약 2주동안 알고리즘을 공부했었는데 공부한 내용을 포스팅하지는 못했다. 그래서 같은 로직의 문제를 풀 때 똑같은 실수를 반복하고는 했었다. 이래서 기록이 중요하다고 하는 것 같다.

문제 설명

마라톤 대회에서 참가자 명단과 완주자 명단을 보고 완주하지 못한 선수를 찾아내는 문제이다. 참가자 중 딱 한명만이 완주를 못했고 그 한 명의 참가자를 찾아내야 한다. 그리고 또 한가지 조건은 참가자 중 동명이인이 있을 수 있다.

내 풀이

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public String solution(String[] participant, String[] completion) {
        ArrayList<String> users = new ArrayList<>(Arrays.asList(participant));
        for (String c : completion) {
            for (String u : users) {
                if (c.equals(u)) {
                    users.remove(u);
                    break;
                }
            }
        }
        return users.get(0);
    }
}

• ArrayList를 만들어서 참가자 명단을 저장했다. 그 후에 반복문 두개를 사용해서 완주자 명단 한명 한명에 대하여 참가자 명단 중 같은 같은 사람이 있으면 명단에서 제거하고 반복문을 탈출하도록 break문을 사용했다. break문을 사용하지 않으면 동명이인이 있을 경우 두명 다 제거되기 때문이다.

• 정확성 테스트에서는 정상적으로 작동했지만 효율성 테스트에서 모두 시간초과로 실패했다. 알고리즘 과목을 배우지 않고 바로 알고리즘 문제를 풀어서 그런지 효율적으로 코드를 짜는 방법을 잘 모르겠다. 인터넷 검색 결과로는 반복문을 남발하게 되면 시간이 오래 걸린다고 한다. 결국 다른 사람의 풀이를 참고해서 다시 코드를 짜게 되었다.

다른 사람의 풀이

import java.util.Arrays;

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

• Array.sort 메소드를 사용해서 참가자 명단과 완주자 명단을 정렬했다. 그 후에 완주자명단의 인덱스를 반복문으로 돌려서 참가자 명단과 완주자 명단의 같은 인덱스끼리 비교하도록 했다. 다른 이름이 나오면 그 이름을 리턴하도록 했다. 이렇게 하면 참가자 명단의 마지막 사람은 비교를 못하게 되므로 else 문을 사용해서 모두 이름이 같으면 마지막 사람을 리턴하도록 했다.

• 반복문을 한 개만 사용해서 매우 간결하고 직관적으로 코드를 잘 짠 것 같다. 내가 알기로는 sort메서드도 반복문이 사용된다고 하는데 그럼에도 내가 짠 이중 반복문보다는 시간을 덜 잡아먹는듯 하다.