[프로그래머스 / JavaScript] Lv.1 완주하지 못한 선수 (ft. js의 Map 알아보기)

 

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

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

"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

 

입출력 예 #2

"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

 

입출력 예 #3

"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한 명은 완주하지 못했습니다.

 

 

 

---

내가 작성한 답안

맨 처음 작성한 답안 (02/17)

function solution(participant, completion) {
	// 각 배열에 들어있는 이름을 순차적으로 정렬한다.
    participant.sort();
    completion.sort();
    
    // for문을 돌면서 두 배열의 이름이 맞지 않을 경우 해당 이름을 return한다.
    for(let i = 0; i < participant.length; i++) {
        if(participant[i] !== completion[i]) {
            return participant[i];
        }
    }
}

 

답은 맞췄으나, 시간 복잡도의 효율성 측면에서 100점 만점이 나오지 않았다. 해당 문제는 해시 카테고리의 문제이므로 Map을 이용해야 한다는 조언을 듣고 오늘 다시 풀어보았다.

 

 

 

---

Map을 사용해야 하는 이유

for과 map은 서로 다른 목적과 특징을 가지고 있기 때문에 직접적으로 비교하기는 어렵다. for는 데이터를 순회하거나 특정 연산을 수행할 때 사용하며, Map은 key-value를 보다 효율적으로 관리/검색할 때 사용하기 때문이다.

 

다만 Map을 사용하는 경우는 일반적으로 특정 연산에 대해 더 나은 시간 복잡도를 제공할 수 있다. 아래는 Map이 효율성 측면에서 더 나은 이유이다.

 

 

1. 검색 속도

Map은 해시 맵(Hash Map, 쉽게 말해서 Key-Value의 구조!)의 구조를 사용하여 데이터를 저장하므로 특정 키로 값을 검색할 때 빠른 검색 속도를 제공한다. 해시 맵은 일반적으로 평균 O(1)의 시간 복잡도를 가지며, key의 해시 값을 계산해 원하는 값을 바로 찾을 수 있다.

 

 

2. 중복 key 처리

Map은 중복된 키를 허용하지 않는다. 중복된 키를 삽입하려고 하면 기존의 값이 덮어 씌워진다. 따라서 데이터의 중복을 방지할 수 있다.

 

 

3. 순서 보장

Map은 key-value 쌍을 삽입한 순서대로 보장한다. 따라서 데이터의 순서가 중요할 경우 Map을 사용하면 데이터를 순서대로 처리할 수 있다.

 

 

4.  원시 타입 및 객체 타입 모두 사용 가능

Map은 key로 원시 타입뿐만 아니라 객체, 함수 등 다양한 데이터 타입을 사용할 수 있다.

 

 

5. 반복과 관련된 효율성

Map은 for...of나 forEach 메서드를 사용해 효율적으로 순회할 수 있다. for 루프를 사용할 때보다 보다 간결하게 코드를 작성할 수 있다.

 

 

 

---

Map의 사용법과 주요 특징

정의

Map은 key-value 쌍을 저장하고 관리하는 자료구조이다.

 

 

Map와 Object(객체)의 차이

Map은 객체와 유사하지만, key의 데이터 타입이나 원시 값 등 다양한 값을 key로 사용할 수 있다는 차이점을 보인다. 예를 들어 객체 내에서는 key로 문자열만 사용할 수 있는 반면, Map은 다양한 데이터 타입을 key로 사용할 수 있다.

 

 

Map의 장점

Map 사용 시 데이터를 쉽게 추가, 조회, 수정, 삭제할 수 있으며, 순서가 보장되는 순회(iteration)도 가능하다.

 

 

Map의 주요 메서드와 프로퍼티

// 1. Map 생성하기
new Map();

// 2. 값 추가하기 (key를 이용해 value를 저장)
map.set(key, value);


// 3. 값 조회하기 (key가 존재하지 않으면 undefined 반환)
map.get(key);


// 4. 값 수정하기
map.set(key, newValue);


// 5-1. 값 삭제하기
map.delete(key);

// 5-2. 모든 값 삭제하기
map.clear();


// 6. Map 크기 확인하기
map.size;


// 7. Map 순회하기
for (const [key, value] of map) {
	console.log(`key: ${key}, value: ${value}`);
}


// 8. 특정 key 존재 여부 확인하기 (존재하면 true, 아니면 false)
map.has(key);


// 9. 모든 key 또는 value 가져오기
const keyArr = Array.from(map.keys());
const valueArr = Array.from(map.values());


// 10. 모든 key-value 쌍 가져오기
const allArr = Array.from(map.entries());

 

 

 

---

Map을 이용해 다시 풀어본 답안

const solution = (p, c) => {
	// Map을 생성한다.
    const map = new Map();
    
    
    // participant를 순회를 돌면서, 
    for (let i = 0; i < p.length; i++) {
    	// 이미 map안에 participant[i]값이 있을 경우 그 값을,
        // 없을 경우 0 + 1을 한 값을
        // key: participant[i], value: participant[i]값 또는 1 의 형식으로
        // map 안에 값을 만들어 넣는다.
        map.set(p[i], (map.get(p[i]) || 0) + 1);
        
        // 위와 동일하게 key: completion[i], value: completion[i]값 또는 -1의 형식으로
        // map 안에 값을 만들어 넣는다.
        // 이때, completion[i]의 값이 없는 값(participant의 길이 -1이므로) 일 경우
        // key는 undefined, value는 -1이 되어 map 안에 값이 들어간다.
        map.set(c[i], (map.get(c[i]) || 0) - 1);
    }
        
    // participant와 completion의 값은 1명 빼고 모두 동일하므로,
    // 동일한 이름들의 value는 +1, -1이 되어 0,
    // 일치하지 않는 길이에 대해서는 undefined: -1,
    // 일치하지 않는 이름(완주하지 못한 선수)는 1이 된다.
    // 왜? map.set(c[i], (map.get(c[i]) || 0) - 1); 부분에서
    // 그 이름이 없어 -1 처리를 하지 못했으므로!
    
    // 따라서 for문으로 map을 순회하며 0보다 큰 값의 name을 추출한다.
    // 이때, undefined: -1이 있으니 0보다 큰 값으로 빼내야 올바른 값을 출력할 수 있다.
    for (const [name, value] of map) {
        if (value > 0) return name;
    }
}

 

 

 

 

---

[참고 자료]

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

프로그래머스