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

문제 내용

마라톤 참가자 중에서 완주를 하지 못한 1명을 찾아라

마라톤 참가자 (participant) 와 마라톤 완주자 (completion) 이 주어짐.

 

예를 들어,

참가자 (participant)	완주자 (completion)	return
["홍길동", "김아무개"]	["홍길동"]	"김아무개"

이렇게 "홍길동" 만 완주에 성공하였으므로 "김아무개" 를 return 하면 된다.

---

전체 코드

function solution(participant, completion) {
    let index = 0; // 1
    
    participant.sort(); // 2 
    completion.sort(); // 3
    
    // 4
    for (index; index < completion.length; index++) {
        
        // 5
        if (participant[index] != completion[index]) {
            break;
        }
    }
    
    return participant[index];
}

1. 먼저 participant 와 completion 을 비교할 index 를 설정한다.
2. participant 를 정렬한다.
3. completion 을 정렬한다.
4. index 에서 시작해서 completion.length 전 까지 반복을 한다.
5. 만약 participant[index] 와 completion[index] 가 같지  않다면 반복문을 종료한다.

 

 코드의 예를 들면,

participant	completion
["호구마츄", "라라랜드", "김아무개"]	["김아무개", "호구마츄"]

이렇게 값이 들어온다고 가정하자.

 

먼저 비교를 할 index 를 생성한다.

let index = 0;

그리고 participant 와 completion 을 정렬한다.

여기서 정렬하는 이유는 마라톤 선수들의 이름이 뒤죽박죽이기 때문이다.

    participant.sort(); // 2 
    completion.sort(); // 3

정렬을 하게 되면

["김아무개", "라라랜드", "호구마츄"]

["김아무개", "호구마츄"]

이렇게 된다. (오름차순, 내림차순 상관 없음)

 

반복문을 진행한다.

    // 4
    for (index; index < completion.length; index++) {
        
        // 5
        if (participant[index] != completion[index]) {
            break;
        }
    }

index = 0 일때,

participant[index] ("김아무개") 는 completion[index] ("김아무개") 와 같으므로 그대로 5번에 해당하지 않는다.

 

index = 1 일때,

participant[index] ("라라랜드") 는 completion[index] ("호구마츄") 와 같으므로 5번에 해당된다.

그러므로 break (반복문 종료)

 

현재 index 는 1로 설정되었다.

 

    return participant[index];

 

마지막으로 participant[1] ("라라랜드") 를 return 하며 함수를 종료한다.

---

결론

참가자와 완주자를 정렬하는데 O(n log n) 의 시간과 반복문 진행하는데 O (n) 의 시간이 걸린다.

따라서 O (n log n) 인데 참여한 선수 (n) 가 100,000 명이므로 코드 진행에 무리가 없다.

 

 

출처 : 프로그래머스 해시 완주하지 못한 선수 (Level 1)
https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수