[99클럽 코테 스터디] 5일차 TIL - 완주하지 못한 선수

Hoxy?·2024년 7월 26일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99클럽 코테 스터디

목록 보기

5/42

오늘의 학습 키워드

완주하지 못한 선수

공부한 내용 본인의 언어로 정리하기

import java.util.*;

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

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

오늘의 회고

배열을 비교하려면 순서대로 정렬을 해놓는게 맞을 것 같아
출전한 선수와 완주한 선수를 오름차순으로 정렬을 하는 것으로 시작했다.

처음에는 2중 for문을 이용해서 출전 선수의 Index(0)의 선수와 완주한 선수 전체를 비교해서 같은 값이 없다면 반환 해주면 된다고 생각했고 코드를 작성하다 전체를 비교하니 일치하지 않았던 선수들이 이름이 대량으로 추가 되는 것을 발견했고 즉시 방향을 틀었다.

그래서 나온 코드가 이것이다.

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

완주한 선수는 출전한 선수보다 같거나 작을 수 밖에 없으므로 i의 값은 완주한 선수보다 작아야한다. 그러므로 최대 반복 횟수는 완주한 선수의 수만큼만 진행 되어야 한다.

만약 각 반복에서 출전한 선수와 완주한 선수의 이름을 비교해서 두 값이 다르다면 완주하지 못한 선수는 participant[i]를 의미하고, 따라서 이 값을 바로 반환한다.

만약 for문에서 불일치하는 요소를 찾지 못했다면, 마지막 참가자가 완주를 하지 못했음을 의미하므로 participant[]의 마지막 요소를 반환한다.

return participant[completion.length];

내가 participant.length - 1을 사용하지 않은 이유는 완주하지 못한 선수는 단 1명이라고 명시되어 있기 때문에 결국 완주한 선수는 (참가한 선수 -1)이 되어서 그렇다.

AI 코드리뷰

이 코드는 마라톤 참가자 중 완주하지 못한 한 명을 찾는 알고리즘을 구현한 것으로 보입니다. 코드를 리뷰해 드리겠습니다.
전반적인 접근 방식:

참가자(participant)와 완주자(completion) 배열을 정렬합니다.
두 배열을 순차적으로 비교하여 불일치하는 첫 번째 요소를 찾습니다.

코드 분석:

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

이 부분에서 두 배열을 정렬합니다. 정렬을 통해 두 배열의 요소들을 순서대로 비교할 수 있게 됩니다.

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

for문 부분 자세한 설명:

반복문은 completion 배열의 길이만큼 반복합니다. completion배열은 participant 배열보다 길이가 1 작습니다.

각 반복에서 participant[i]와 completion[i]를 비교합니다.

만약 두 값이 다르다면 (!participant[i].equals(completion[i])), 이는 participant[i]가 완주하지 못한 선수임을 의미합니다. 따라서 이 값을 바로 반환합니다.

만약 모든 요소가 같다면, 반복문은 끝까지 실행됩니다.

return participant[completion.length];

만약 for문에서 불일치하는 요소를 찾지 못했다면, 이는 마지막 참가자가 완주하지 못했음을 의미합니다. participant 배열의 마지막 요소를 반환합니다.

이 알고리즘의 시간 복잡도는 정렬에 의해 결정되며, O(n log n)입니다. 여기서 n은 참가자의 수입니다.

개선 가능한 점:

이 방법은 효과적이지만, 정렬에 추가적인 시간과 공간이 필요합니다.
HashMap을 사용하면 O(n) 시간 복잡도로 문제를 해결할 수 있습니다.

전반적으로 이 코드는 간결하고 이해하기 쉬우며, 주어진 문제를 효과적으로 해결합니다.

시간 복잡도 개선 코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> participantMap = new HashMap<>(); //각 참가자의 등장 횟수를 저장
        
        // 각 참가자의 등장 횟수를 세기
        for (String player : participant) {
            participantMap.put(player, participantMap.getOrDefault(player, 0) + 1);
        }
        
        // 완주한 선수마다 횟수를 감소시키기
        for (String player : completion) {
            participantMap.put(player, participantMap.get(player) - 1);
            if (participantMap.get(player) == 0) {
                participantMap.remove(player);
            }
        }
        
        // 맵에 남아있는 선수가 완주하지 못한 선수
        return participantMap.keySet().iterator().next();
    }
}

장점:
1. 시간 복잡도: O(n), 여기서 n은 참가자의 수입니다. 모든 참가자와 완주자를 각각 한 번씩만 순회합니다.
2. 정렬이 필요 없어 추가적인 공간 복잡도가 줄어듭니다.
3. 대량의 데이터에 대해 더 효율적으로 동작합니다.

단점:
1. 약간의 추가 메모리가 필요합니다(HashMap을 위한 공간).
2. 코드가 조금 더 복잡해질 수 있습니다.

이 개선된 버전은 특히 참가자 수가 많은 경우에 더 효율적으로 동작할 것입니다.
시간 복잡도가 O(n log n)에서 O(n)으로 개선되었기 때문입니다.

내일 공부할 것 :

AI가 개선해준 코드는 내가 처음에 전체 선수에서 완주한 선수만 제거하고 남은 선수를 반환시키면 되겠라고 생각한 것과 유사해 보이지만 코드나 문법을 어떻게 사용해야 할지 몰라 포기하고 변경하게 되었다. 더 다양한 문법에 대해 공부할 필요성이 매우 크다.

HashMap, Stream 등 최근에 자주 보였지만 몰라서 사용하지 못한 문법에 대해서 공부하는 시간이 필요하겠다.