항해 99 - 완주하지 못한 선수

[ 문제 ]

수많은 마라톤 선수들이 마라톤에 참여하였습니다.

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 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"

 

[ Input / Output 예시 ]

participant	completion	Output
["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)

(내 풀이 - 1)

처음에는 가장 단순한 방법으로 문제를 풀었다.

completion 배열의 원소들을 for문으로 반복하면서 participant 배열의 요소를 삭제했다.

이 방법은 결국 for문이 중첩되어있기 때문이어서 그런지 효율성 검사에서 탈락했다 ㅠㅠ

 

풀이 (2)

(내 풀이 - 2)

열심히 생각하다가 꺼낸 두 번째 방법

두 배열을 정렬하여 같은 인덱스 자리에 다른 요소 찾기!

이 방법은 바로 통과했지만 뭔가 찜찜함이 남아서 다른 사람의 풀이를 보았다.

 

풀이 (3)

(프로그래머스 풀이)

이 문제가 해시 문제라는 것을 왜 깨닫지 못했을까...?? 진짜 바보같구...ㅠ

내가 Map 이라는 자료형을 너무 신경쓰지 않은 탓인가?? 알고리즘 공부를 너무 안했더니 hash 자료라는 걸 아예 잊었다.

해시 함수란 간단히 말해서 key-value 형식을 통해 데이터의 저장 및 검색을 아주 빠르게 처리해주는 구조이다.

JS에서는 Map() 자료 구조를 말한다.

해시 함수는 key값이 자료형에 있어서 자유롭기 때문에 데이터를 처리하는 과정에서라면 사용할 수 있지만 대체적으로 문자열을 key 값으로 가지는 문제일 때 많이 사용한다.

 

여기서는 이 Map()을 활용해서 particitpant의 요소일 때는 배열에 1을 더해주고, completion의 요소일 때는 1을 빼준다.

1을 더하고 빼는 과정에서 완주했다면 value가 0이 될 것이고, 완주하지 못했다면 1이 그대로 남아있을 것이다.

 

[ 코드 ]

// 풀이 (1)
// completion의 요소를 꺼내서 for문으로 돌린다. 
// .indexOf를 활용하여 particitpant 배열에서 삭제할 인덱스를 찾고 splice를 통해 삭제한다.
const solution1 = function (participant, completion) {
    // completion의 요소를 꺼내어 for문으로 반복
    completion.forEach(person => {
        // 참가자 배열에서 완주한 요소의 index를 이용하여 제거
        participant.splice(participant.indexOf(person), 1)
    });
    // 완주하지 못한 사람은 무조건 1명이므로 [0]
    return participant[0];
}

console.log(solution1(["mislav", "stanko", "mislav", "ana"], 
                      ["stanko", "ana", "mislav"]))


// 위의 경우는 시간 초과로 실패다. 다시 생각해보자.

// 풀이 (2)
// .sort()를 한 후 일치하지 않는 부분을 찾아 반환하자.
const solution2 = function (participant, completion) {
    // 각 배열을 정렬한다.
    participant.sort();
    completion.sort();

    // 0 이상 participant의 길이 미만만큼 for문 반복
    for (let i=0 ; i < participant.length ; i++){
        // 정렬을 했기 때문에 같은 위치의 요소가 다른 것만 찾으면 완료
        if (participant[i] !== completion[i]) return participant[i];
    }
}

console.log(solution2(["mislav", "stanko", "mislav", "ana"], 
                      ["stanko", "ana", "mislav"]))

// indexOf를 매 경우 반복하는 것보다 처음에 정렬을 한 후 for문을 돌리는 것이 효율적이다.


// 풀이 (3)
// 해시 함수 : key-value 형식을 통해서 데이터의 검색과 저장을 아주 빨리 할수 있게 하는 자료구조
// 해시 함수의 가장 큰 특징은 key의 값이 다양한 자료구조가 가능하다는 점이다.
// JS에서는 Map 자료구조가 있다.
// 사람의 이름을 통해 완주 여부를 판단하기 때문에 해시 구조를 활용했다.
const solution3 = function (participant, completion) {
    // Map 선언
    const map = new Map();

    // 각 요소에 따라 participant일 땐 +1, completion은 -1해준다.
    for (let i=0 ; i<participant.length ; i++){
        let part = participant[i];
        let comp = completion[i];

        map.set(part, (map.get(part) || 0) + 1);
        map.set(comp, (map.get(comp) || 0) - 1);
    }

    // participant에만 요소가 있다면 1을 빼주지 않았으므로 value값이 1일 것이다.
    for (let [key, value] of map) {
        if (value > 0) return key;
    }
}

console.log(solution3(["marina", "josipa", "nikola", "vinko", "filipa"], 
                        ["josipa", "filipa", "marina", "nikola"]))