[알고리즘] 보석 찾기, 큰 수 찾기, 보이는 학생

💡 보석 찾기

여기 보석을 나타내는 문자열 jewels와 당신이 보유한 돌을 나타내는 stones가 있습니다. stones의 각 글자는 당신이 보유한 돌의 유형을 뜻합니다. 가지고 있는 돌 중에 보석인 돌은 몇 개인지 구하는 프로그램을 작성하세요. 단, 대소문자를 구분하므로 "a"와 "A"는 다른 유형의 돌로 간주됩니다.

leetcode 문제 링크

나는 일단 이 문제를 filter와 indexOf()를 사용해서 해결했다. stones의 각 문자가 jewels의 글자를 포함하고 있는지 확인하고, true인 경우만 새로운 배열로 만들어 그 배열의 길이를 재는 방식이다.

var numJewelsInStones = function (jewels, stones) {
return [...stones].filter(stone => jewels.indexOf(stone) !== -1).length
};

includes()를 사용할 수도 있다.

var numJewelsInStones = function(jewels, stones) {
   return [...stones].filter(stone => jewels.includes(stone)).length
}; 

그런데 같은 스터디의 T님이 해시를 사용해서 성능을 개선하는 풀이를 알려주셨다. 해시는 키-밸류를 가진 자료구조를 말한다. T님의 코드는 다음과 같다.

var numJewelsInStones = function(jewels, stones) {
    const increment = counter(stones);

	const result = [...jewels].map(jewel => increment.get(jewel) ?? 0);
    return sum(result); // jewel 이 없으면 0
};

function counter(arr){
    const result = new Map(); 
    for (const item of arr){
        result.set(item, (result.get(item) ?? 0) + 1);
    }
    return result;
}


function sum(arr){
    return arr.reduce((a,b) => a+b, 0);
}

코드 길이는 내가 작성한 코드가 훨씬 간결하지만, 런타임 속도의 경우 Map을 이용한 T님의 풀이가 빨랐다. (내 코드 84ms, T님 코드 64ms) 전달받는 매개변수가 크고 복잡해질수록 이 차이는 더욱 벌어질 테니까 확실한 성능의 격차가 있는 셈이다.

Set()을 이용한 풀이도 성능이 좋았다. (69ms)

var numJewelsInStones = function(jewels, stones) {
		const jewelSet = new Set(jewels);
    return [...stones].filter(stone => jewelSet.has(stone)).length;
};

이처럼 set을 사용하면 jewel이 길고 복잡해질수록 더욱 성능의 차이를 체감할 수 있다고 한다.

Set?

보통 Set은 중복을 제거하고 유일한 값을 남길 때 쓴다. Set이 중복을 허용하지 않기 때문이다. 예를 들자면 다음과 같다.

let a = [1,1,1,1,1,1,1,1,3,5,7,9];
let aSet = new Set(a);

이 경우 aSet은 중복된 1이 제거되고 1,3,5,7,9가 반환되는 것을 확인할 수 있다.

💡 큰 수 찾기

N(1<=N<=100)개의 정수를 입력받아, 자신의 바로 앞 수보다 큰 수만 출력하는 프로그램을 작성하세요.(첫 번째 수는 무조건 출력한다)

이 문제는 비교적 간단하게 해결했다. arr[i]와 arr[i-1]을 비교해서 arr[i]가 더 클 경우 answer 배열에 넣어주는 방식으로 풀었다.

function solution(arr) {
  let answer = [];
  answer.push(arr[0]);
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > arr[i - 1]) answer.push(arr[i]);
  }
  return answer;
}

💡보이는 학생

선생님이 N(1<=N<=1000)명의 학생을 일렬로 세웠습니다. 일렬로 서 있는 학생의 키가 앞에 서부터 순서대로 주어질 때, 맨 앞에 서 있는 선생님이 볼 수 있는 학생의 수를 구하는 프로그램을 작성하세요. (앞에 서 있는 사람들보다 크면 보이고, 작거나 같으면 보이지 않습니다.)

나는 이중for문으로 풀었는데, i와 j 각각 반복문을 돌기 때문에 이 풀이는 너무 비효율적이다. max 값을 설정하면 이중for문을 사용하지 않아도 해결할 수 있다. i가 전체 배열을 돌며 max보다 클 때만 answer의 카운트를 증가시키면 되기 때문이다. max값을 이용한 풀이는 다음과 같다.

function solution(arr) {
  let answer = 1,
    max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      answer++;
      max = arr[i];
    }
  }
  return answer;
}

answer의 초기값이 0이 아니라 1인 이유는 맨앞에 서있는 학생은 키와 상관없이 무조건 보이기 때문이다. for문 한 번으로 간단하게 해결되었다.