오늘은 프로그래머스 "완주하지 못한 선수" 라는 문제를 풀면서 알아낸 것을 쓰는 시간을 가져보겠습니다.
우선 문제를 설명하자면
참가자는 동명이인이 있을 수 있고 결과적으로 완주하지 못한 단 1명을 찾으면 되는 문제입니다.
저는 처음에 이렇게 풀었습니다.
function solution(participant, completion) {
let answer = '';
completion.map(i => {
const idx = participant.findIndex(par => par === i);
participant.splice(idx, 1);
})
answer = participant.join("");
return answer;
}이 풀이의 핵심은 참가자의 명단에서 완료자와 비교한 후 인덱스를 구하고 그 인덱스에 맞는 참가자를 참가자 명단에서 삭제하는 것입니다.
결론을 말하자면 답은 맞았지만 효율 테스트에서 떨어졌습니다.
그 이유를 생각해보니 이 문제의 카테고리는 해시입니다.
해시
해시란 특정한 배열의 인덱스나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 츶을 수 있도록 하는 것이다.
간단하게 말해서 내가 찾고자 하는 것을 인덱스를 이용해서 바로 참조하는 것이라고 이해하면 쉬울 것 같다.
(더 찾아보니까 제가 말한건 Direct Addressing Table 이라는 개념 같아요. 이것 말고도 다른 개념이 존재해요!)
그래서 저는 이것 말고 다른 답은 어떤지 하는 궁금증에 찾아보았습니다.
그리고 대부분의 답안이 아래와 같았습니다.
function solution(participant, completion) {
participant.sort(); //참가자 배열 정렬
completion.sort(); //완주자 배열 정렬
for(var i=0;i<participant.length;i++){
if(participant[i] !== completion[i]){
//인덱스 0부터 순차적으로 두 배열 비교
return participant[i];
//비완주자가 참가자 배열에 나올 경우 출력
}
}
}위를 보니까 participant와 completion의 배열을 모두 sort() 를 이용해 정렬 후 비교연산을 진행하였습니다.
그런데 여기서 저는 어디가 해시 인지 도무지 모르겠습니다.
그래서 더 해시 다운 답안이 있을 까 찾던 중 Map() 을 이용한 답을 발견하고 그에 대해 정리하고자 합니다.
Map
우선 MDN에서는 Map을 이렇게 정의합니다.
Map 객체는 키-값 쌍을 저장하며 각 쌍의 삽입 순서도 기억하는 콜렉션입니다. 아무 값(객체와 원시 값)이라도 키와 값으로 사용할 수 있습니다.
정의를 보니까 무언가 해시를 위해 태어난 함수인가? 라는 생각도 했습니다.
간단한 Map 예제를 보면서 더 이해를 해보겠습니다.
const map = new Map(); // Map 객체를 생성합니다.
map.set("name", "Lee") // ket: value 형식
map.set("age", "18")
> Map(2) {"name" => "Lee", "age" => "18"} // 굉장히 반가운 => 표현
map.forEach((value, key, mapObject) => {
console.log(`value: ${value} key: ${key} mapObject: {mapObject}`);
})
// Lee name Map...
// 18 age Map...
// for..of 문법으로 순회
// Why? continue, break. return 같은 루프 기능을 못쓰기 때문
for (let item of map) { // 키와 벨류가 들어있는 배열
console.log(`${item[0]} : ${item[1]}`); // name: Lee
}set, forEach 외에도 기본 Map의 프로토타입 메소드는 많습니다. 살짝 맛만 본것이죠.
다시 문제로 돌아가서 Map 객체를 이용해 문제를 풀어보죠
function solution(participant, completion) {
let completeMap = new Map();
for(const person of completion) {
const mapItem = completeMap.get(person);
completeMap.set(person, mapItem ? mapItem + 1 : 1);
}
for(const person of participant) {
const mapItem = completeMap.get(person);
if(!mapItem) {
return person;
} else {
completeMap.set(person, mapItem - 1)
}
}
}첫 번째 for문을 돌면서 completeMap에 참가자이름: +1 하는 식으로 값을 넣는다.
두 번째 for문을 돌 때는 completeMap에 완주자이름: -1 하는 식으로 값을 뺀다.
결국 누군가는 값이 없거나 0일 것이고 이 값을 반환하면 성공이다.
오늘 간단하게 프로그래머스 문제도 풀고?(약간 내 코드로 못 푼것에 한을 느낀다..) 다른 사람 코드도 보면서 한 참 작년의 내가 떠오른다.
개발자가 되겠다면서 엄청 열심히 그리고 꾸준히 했지만 최근에 게임에 빠져서 공부도 많이 안했다.
그런데 내 친구의 권유로 게임도 끊고 규칙을 정해서 살고 있다.
게임 하나 끊었는데 시간이 남아돌고 잠도 더 많이 잔다.
분명 나같은 사람이 많을 것이다. 게임은 적게하면 좋지만 나 처럼 하루의 반을 날리는 사람이라면 끊길 권유한다. 더 좋은 삶이 기다리고 있기 때문이다.
