[프로그래머스] 완주하지 못한 선수 (Lv. 1, JavaScript)

📝 문제 설명

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

프로그래머스

• 목표: 마라톤에 참여한 선수들 중 완주하지 못한 선수의 이름을 반환해야 한다.
• 핵심 조건
  • 단 한 명의 선수를 제외하고는 모든 선수가 완주를 했다.
  • 참가자의 이름에 동명이인이 있을 수 있다.

---

🔍 풀이 과정 (나만의 풀이 전략)

주어지는 인풋은 전체 참가자 명단 participant 와 완주한 참가자 명단 completion 이다.

첫 번째 방법

그렇다면 전체 참가자 명단에서 완주한 참가자 명단의 이름을 제외하면 되지 않을까?

function solution(participant, completion) {
    var answer = '';
    completion.forEach((comp) => {
        participant.splice(participant.indexOf(comp), 1);
    })
    answer = participant[0]
    return answer;
}

완주한 참가자 수 배열을 순회하면서 참가자 수 배열에서 완주한 사람의 인덱스를 indexOf를 통해 알아내어 splice(완주한 사람 인덱스, 1명) 을 통해 participant 배열에서 제외하도록 한다.

이렇게 되면 최종적으로 완주하지 못한 1명만 남은 participant 배열이 된다.

두 번째 방법

function solution(participant, completion) {
    let answer = ''
    const newMap = new Map();
    
    participant.forEach((part) => {
        if (!newMap.get(part)) {
            newMap.set(part, 1)
        } else {
            newMap.set(part, newMap.get(part) + 1)
        }
    })
    
    completion.forEach((comp) => {
        if (newMap.get(comp)) {
            newMap.set(comp, newMap.get(comp) - 1)
        }
    })
    
    newMap.forEach((value, key) => {
        if (value === 1) {
            answer = key;
            return ;
        }
    })
    return answer;
}

해당 문제가 해시 자료구조에 관한 문제이므로 map 객체를 활용하여 문제를 해결하고자 한다.

우선 전체 참가자 배열을 순회하면서 newMap 객체에 set 하는데 이미 map 객체에 있다면 value를 1 증가시키고 없다면 1로 set 하도록 한다. 이렇게 하면 map 객체에 { 참가자이름, 인원수 } 같은 형태로 저장된다.

 

다음으로는 완주한 참가자 배열을 순회하면서 newMap 객체에서 완주한 사람의 이름이 존재하는지 확인하고 존재한다면 value를 1 감소하도록 한다. 이렇게하면 최종적으로 map 객체에는 value가 1인 참가자 한명만이 남게 되고 해당 참가자가 완주하지 못한 마지막 1명이 되므로 answer를 구할 수 있게 된다.

 

위 두 가지 방법은 정확성 테스트에서는 통과할 수 있었으나, 효율성 테스트에서 통과할 수 없었다.

첫 번째 방법은 모든 효율성 테스트 케이스를 시간 초과로 통과하지 못했고, 두 번째 방법은 1-2 효율성 테스트 케이스만 통과하고 나머지 3개 테스트 케이스는 시간 초과로 통과하지 못했다.

세 번째 방법

마지막 answer를 구하는 방법을

    participant.forEach((part) => {
        if (newMap.get(part) > 0) {
            answer = part;
            return ;
        }
    })

participant 배열을 순회하는 방식으로 수정했을 때 효율성 테스트를 통과하는 모습을 보였다.

🛠️ 트러블슈팅

총 세 가지 방법을 시도해보았는데, 위에서 언급한대로 첫 번째, 두 번째 풀이의 경우 정확성 테스트는 통과하였으나, 효율성 테스트에서 시간 초과로 실패하게 되었다. 시간 복잡도 관점에서 분석해보면 왜 실패했는지 확실하게 알 수 있었다.

1. completion.forEach : 완주자 명단만큼 순회하므로 O(N)의 시간 복잡도
2. participant.indexOf(comp) : 마찬가지로 전체 명단에서 특정 참가자의 인덱스를 알아내기 위해 전체를 순회하므로 O(N)
3. participant.splice(...) : splice의 경우 배열의 특정 요소를 삭제하면 나머지 뒤의 요소들을 앞으로 당기는 작업이 필요하기 때문에 삭제하려는 요소가 배열의 끝이라면 O(1)의 시간 복잡도이지만, 요소가 중간에 위치할 경우 O(N)의 시간 복잡도를 가지게 된다.

결과적으로 전체 시간 복잡도를 계산해보면 N * (N + N) = 2N^2 → O(N^2)의 시간 복잡도를 가지게 된다.

배열 자체를 순회하는건 2, 3번째 방법 동일하나 splice의 시간복잡도가 최대 O(N)일 수 있어 효율성 면에서 가장 안 좋은 풀이 방법이 되었던 것으로 보인다.

 

다음으로 두 번째 풀이의 경우에는

동일하게 participant나 completion배열을 순회하는 것은 같으나 forEach 내부에서 map 객체의 메서드인 set과 get을 사용하였는데, 이는 내부적으로 해시 테이블을 사용하기 때문에 O(1)의 시간 복잡도를 가집니다.

그럼에도 불구하고 시간 초과로 실패한 이유는 무엇일까?

 

마지막 세 번째 풀이와의 차이점은

Map.forEach 의 경우 Map 객체에 저장된 모든 키-값(Entry)를 꺼내와야한다. 다만 participant.forEach의 경우 단순 배열의 값을 순회하여 Map.get(part)로 확인하기 때문에 비교적 더 빠르기 때문이다.

 

문제 제출 후 성능을 더 최적화하는 방법에 대해 알아 보았다.

코드 상에서 answer를 찾을 경우 return을 통해 break를 시도하도록 작성하였는데,

forEach의 경우에는 return을 만나더라도 멈추지 않고 끝까지 모든 데이터를 확인한다.

이러한 방법을 시도하기 위해서는 forEach 보다는 for… of나 기본 for문을 사용하거나 아니면 forEach 문에서 try catch문을 통해 예외처리를 하는 방법 혹은 some나 every 메서드를 사용하는 방법이 있다고 한다.

---

💻 코드 (Code)

function solution(participant, completion) {
    let answer = ''
    const newMap = new Map();
    
    participant.forEach((part) => {
        if (!newMap.get(part)) {
            newMap.set(part, 1)
        } else {
            newMap.set(part, newMap.get(part) + 1)
        }
    })
    
    completion.forEach((comp) => {
        if (newMap.get(comp)) {
            newMap.set(comp, newMap.get(comp) - 1)
        }
    })
    
    participant.forEach((part) => {
        if (newMap.get(part) ) {
            answer = part;
            return ;
        }
    })
    
    return answer;
}

최적화된 코드

function solution(participant, completion) {
    let answer = ''
    const newMap = new Map();
    
    participant.forEach((part) => {
        if (!newMap.get(part)) {
            newMap.set(part, 1)
        } else {
            newMap.set(part, newMap.get(part) + 1)
        }
    })
    
    completion.forEach((comp) => {
        if (newMap.get(comp)) {
            newMap.set(comp, newMap.get(comp) - 1)
        }
    })
    
    participant.some((part) => {
        if (newMap.get(part) > 0) {
            answer = part;
            return true;
        }
        return false;
    })
    
    return answer;
}

---

❓ 꼬리 질문 및 복습 (Self-Q&A)

복습

배열 탐색

• Array.prototype.indexOf(item)
  • 배열에서 주어진 요소를 찾을 수 있는 첫 번째 인덱스를 반환하고, 찾을 수 없는 경우 -1을 반환합니다.
  • 작동 원리는 배열의 0번 인덱스부터 끝까지 하나씩 대조해 봅니다.
  • 시간 복잡도는 O(N)
• Array.prototype.splice(start, deleteCount, [item1, item2, …])
  • 배열의 특정 지점에서 요소를 삭제하거나 추가합니다. start는 삭제하거나 추가할 배열의 인덱스, deleteCount는 삭제할 요소의 개수를 의미합니다. 0 이하라면 제거하지 않고 생략한다면 start부터 모든 요소를 제거합니다.
  • item은 배열에 추가할 요소를 지정합니다.
  • 작동 원리는 배열의 중간 요소를 제거하거나 추가할 경우 빈자리를 채우기 위해 뒤에 있는 요소가 모두 이동을 해야합니다.
  • 따라서 시간 복잡도는 O(N)

Map 객체

Map 객체는 키-값 쌍과 키의 원래 삽입 순서를 기억합니다.

• set(key, value): 데이터를 저장합니다.
• get(key): 데이터를 가져옵니다.
• has(key): 데이터가 있는지 확인합니다.

내부적으로 해시 테이블 자료 구조를 사용하기 때문에 시간 복잡도는 O(1)입니다.

꼬리질문

Q: Map은 내부적으로 데이터를 어떻게 저장하기에 인덱스가 없어도 값을 바로 찾을 수 있을까?

Q: 일반 Object와 Map의 성능 차이는 언제 발생할까? 데이터의 개수가 많을 때 Map이 유리한 이유는?

Q: 첫 번째 풀이(배열 수정)와 두 번째 풀이(Map 생성) 중 메모리를 더 많이 사용하는 것은 무엇일까?

---

💬 마무리하며

이번 문제를 해결하면서도 마주했던 문제점은 제가 JS 기본 문법들에 대해 너무 머리속에 든게 없구나 였습니다. splice 메서드, 나 indexOf 메서드, map 객체에 대해서 잘 알지 못하여 방법론 자체를 생각하는데 너무나 오랜 시간이 걸리고 생각하더라도 이를 구현하는데 애를 먹는 등 문제가 생겼고, 추가로 각 메서드들에 대한 시간 복잡도에 대해 알고 있지 못하니 시간 초과가 발생하는 문제 역시 발생했습니다.

 

문제를 해결하면서 여러 고민이 생기는 것 같습니다. 기본 JS 문법에 대해 어느정도 학습하고 문제를 푸는게 좋을까? 아니면 지금처럼 문제를 학습하면서 박치기하면서 학습하는게 좋을까? 고민이 필요한 문제 같다고 느꼈습니다.