[JS]_daily coding #25

seul·2022년 6월 29일

Algorithm

목록 보기

24/31

코플릿 04_isSubsetOf

두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다.

number 타입을 요소로 갖는 임의의 배열 2개를 입력 받아서 boolean 타입을 리턴해야 한다.
base, sample 내에 중복되는 요소는 없다고 가정한다.

수도코드

sample요소가 base 배열에 포함되어있는지를 기록하는 count 변수를 선언하고 0으로 초기화
sample 배열의 요소를 순회하는 반복문 선언
base배열에 sample 배열의 요소들이 포함되어 있는 경우에는 count 값에 1을 더해준다.
반복문을 빠져나와서 count가 sample 길이와 같은 경우 true를 리턴한다.(sample 배열의 모든 요소가 base배열에 포함된 경우이므로)
그렇지 않은 모든 경우에는 false 리턴

코드

advanced 케이스를 생각하지 않고 일단 풀었다. 문제의 예시처럼 입력되는 배열의 길이가 짧은 경우에는 정상적으로 값을 반환하지만 실행시간이 초과되어서 테스트를 통과하지 못했다. 내가 작성한 코드는 sample 배열을 순회할때마다 includes()메서드를 통해서 base 배열을 순회하고 있기 때문에 이중 for문처럼 작동한다.

const isSubsetOf = function (base, sample) {
  let count = 0;
  for(let item of sample) {
    if(base.includes(item)) {
      count++;
    }
  }
  if(count === sample.length) return true;
  return false;
  
  // every() 메서드를 이용한 풀이_배열 안의 모든 요소가 주어진 판별 함수를 통과하는지 여부를 boolean으로 리턴
  // return sample.every((item) => base.includes(item));
};

다시 풀어보기!

레퍼런스 코드에는 입력된 배열을 각각 정렬한 다음 두 배열을 비교해주는 것 같은데, 잘 이해가 되지 않아서 다른 방법을 찾아봤다. 지금 듣고 있는 유데미 자바스크립트 알고리즘 강의 목차를 뒤지고, 구글을 뒤진 결과, 이 문제를 해시 유형으로 볼 수 있을 것 같았다.

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조. 해시 테이블은 각각의 key값에 해시함수를 적용해 배열의 고유한 인덱스를 생성하고 이 인덱스를 활용해서 값을 저장하거나 검색할 수 있다.

아직 해시 자료구조 자체에 대해서는 잘 이해가 되지 않지만, 문제 풀이에는 적용시켜 볼 수 있을 것 같았다. 비교대상인 길이가 긴 배열의 요소를 키로 하여 객체에 담아주고, 비교 주체인 배열의 요소를 키로 갖는 값이 있는지 확인하는 식으로 접근할 수 있다.

base 배열을 순회하면서 요소를 하나씩 새로운 객체에 담아준다. (key는 base 배열의 요소이고,value는 임의의 값)
sample 배열을 순회하면서 해당 객체에 sample 배열의 요소를 key로 갖는 value가 있는지 확인한다. 해당 요소를 가지고 있지 않다면 (undefined) sample배열은 base배열의 부분집합이 아니기 때문에 false를 리턴한다.
위 조건에 해당되지 않아서 for문을 통과하면 true를 리턴한다.

코드

const isSubsetOf = function (base, sample) {
  let obj = {}
  for(let item of base) {
    obj[item] = 1; // 임의의 값 
  }
  for(let item of sample){
    if(obj[item]=== undefined) {
      return false;
    }
  }
  return true
};

Map을 사용해서도 풀 수도 있다.

const isSubsetOf = function (base, sample) {
  let map = new Map()
  for(let item of base) {
    map.set(item, true);
  }
  for(let item of sample) {
    if(map.get(item)===undefined) {
      return false;
    }
  }
  return true
};

프로그래머스 알고리즘 문제 중에도 해시를 사용해서 풀 수 있는 문제가 있어서 풀어봤다.

프로그래머스 :(해시) 완주하지 못한 선수

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

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

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

수도코드

participant를 매핑할 빈 객체를 선언한다.
participant 배열을 순회하면서 선수 이름을 key로 1을 value로 담아준다.
2-1. 동명이인이 있는 경우가 있으므로 해당 key가 존재할 경우에 기존 value에 1을 더해서 재할당한다.
completion 배열을 돌면서 매핑한 객체에 선수이름을 key가 존재하는지를 검사하고, 존재하면 -1을 해준다.
완주 선수는 0을 value로 가지고, 그렇지 않은 선수는 1이상을 가지고 있다.
value가 1이상인 선수를 리턴한다.

코드

function solution(participant, completion) {
 let hashTable = {};
  for(let p of participant) {
    //이미 해당 키가 존재하는 경우에는 value에 +1 
    !hashTable[p] ? hashTable[p] = 1: hashTable[p] = hashTable[p] + 1;
  }
  for(let c of completion) {
    //매핑한 객체에 완주선수 이름이 존재하면 value에 -1 
    hashTable[c] ? hashTable[c] -= 1 : hashTable[c]
  }
  // 완주한 선수는 0을 value로 가짐, 그렇지 않은 경우는 1이상
  for(let p of participant) {
    if(hashTable[p]>=1) {
        return p
    }
  }
}