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

ssjeu·2022년 5월 17일

Algorithm

목록 보기

6/14

문제 설명

완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한조건

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

📝 문제 풀이

문제 분석

참여한 선수의 수는 1명 이상 100,000명 이하 → 시간복잡도 고려! 이중 for문은 Timeout이 날 것, 단순 정답을 출력하기보다는 효율성의 문제 생각 필요

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주 → 한 명만 골라내면 됨

Solution 1)

function solution(p, c) {
    const total = p.length;
    var ans = '';
    
    p.sort();
    c.sort();
    
    for(let i=0; i<total; i++){
        if(p[i] !== c[i]){
            ans = p[i];
            return ans;
        }
    }
}

- sort() 함수

sort() 함수를 이용해 두 array를 정렬한 뒤, 순서대로 비교
단순 for문으로는 시간복잡도가 최대인 것을 정렬을 통해 줄여주기
순서가 일치하지 않을 경우, 해당 participant가 completion 명단에 없다는 의미이므로 해당 participant를 return
형변환하여 비교하지 않도록 !== 연산자 사용

Solution 2)

function solution(p, c) {
    p.sort();
    c.sort();
    while (p.length) {
        let pp = p.pop();
        if (pp !== c.pop()) return pp;
    }
}

- pop() 함수

배열에서 마지막 요소를 제거하고 그 요소를 반환

처음에 pop() 함수로 문제 풀이를 하였지만 sort를 하지 않아 오류 발생
-> 정렬 진행 후 배열의 뒤에서부터 인자를 비교하여 다른 값일 때 해당 값을 return
pop() - JavaScript

Solution 3)

function solution(participant, completion) {
 	participant.sort();
    completion.sort();
 	let answer = participant.find((runner,index)=> runner !== completion[index]);
  	return answer;  
}

- find() 함수

배열에서 특정 값을 찾는 조건을 callback 함수를 통해 전달하여, 조건에 맞는 값 중 첫번째 값을 리턴

두 배열을 처음부터 순서대로 비교해 값이 달라지는 시점에 해당 값을 return
arr.find(callback(element[, index[, array]])[, thisArg])
- callback(element, index, array) 함수
element : 현재 처리중인 배열의 element
index : 현재 처리중인 배열의 index (optional)
array : find() 가 호출된 배열 (optional)