엉금엉금

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

서론 :  프로젝트를 진행중이어서, 꾸준히 문제 푸는건 부담감을 느끼고 있지만,, 그래도 아예 안풀면 많이 까먹는 것 같아서 시간을 내어 문제를 풀었습니다.

개인적으로 자바스크립트에서 Map과 Set을 잘 활용하지 못한다고 생각해서 해당 문제를 포스팅하게 되었습니다.

우선 제가 푼 방식은 

function solution(id_list, report, k) {
  const uniqueReport = Array.from(new Set(report));

  const memberCount = id_list.length; // 참여자수
  const uniqueReportCount = uniqueReport.length; // 중복없는 신고수

  const answer = Array(memberCount).fill(0);
  const nameIndex = {};

 // 이름을 인덱스 값으로 바꿔줄 객체 생성)
  for (let i = 0; i < id_list.length; i++) {
    nameIndex[id_list[i]] = i;
  }

  const reporterList = [];

  // 각각의 피신고자에 대한 신고자를 기록하는 배열 빈칸
  for (let i = 0; i < memberCount; i++) {
    reporterList.push([]);
  }

  // 신고자를 기록하기
  for (let i = 0; i < uniqueReportCount; i++) {
    const [reporter, reportee] = uniqueReport[i].split(' ');
    // console.log(reporter, reportee);
    reporterList[nameIndex[reportee]].push(reporter);
  }

// 신고대상을 분석하여 신고자가 k보다 많은 경우만 신고자에게 메일전송(answer배열값 증가)
  for (let i = 0; i < reporterList.length; i++) {
    if (reporterList[i].length >= k) {
      for (let j = 0; j < reporterList[i].length; j++) {
        answer[nameIndex[reporterList[i][j]]]++;
      }
    }
  }
  return answer;
}

1 .그간 경험으로 set과 map이 중복을 제거할 때 굉장히 용이하다고 생각을 하고 있었습니다. 따라서 우선 중복신고를 없애라는 가이드라인에 따라서 set을 통해서 uniqueReport를 만들었습니다.
2. 피신고자와 신고자를 구분하여 피신고자가 각각의 신고자를 기록하게 만들었습니다.

3. 이후 신고자의 숫자가 k이상이라 재제받는 경우만 anwer배열의 값을 증가시켜서 리턴했습니다.

이 과정에서 미리 nameIndex를 뽑는다던가,, anwer을 미리 0이 담긴 배열로 채우기, 등등 과정이 굉장히 길어졌다고 느꼈습니다.

우선  성능차이입니다.. 공간복잡도 뿐만 아니라 시간복잡도 면에서도 많이 뒤쳐졌네요 ㅠ

function solution(id_list, report, k) {
    let reports = [...new Set(report)].map(a=>{return a.split(' ')});
    let counts = new Map();
    for (const bad of reports){
        counts.set(bad[1],counts.get(bad[1])+1||1)
    }
    let good = new Map();
    for(const report of reports){
        if(counts.get(report[1])>=k){
            good.set(report[0],good.get(report[0])+1||1)
        }
    }
    let answer = id_list.map(a=>good.get(a)||0)
    return answer;
}

우선 저는 중복되는 신고값을 제거하는 과정에서 미리 신고자와 피신고자를 나눴네요.

이후에 Map 객체에 각각 bad (신고 횟수 ) . good(신고 성공한 횟수) 를 기록합니다.
이때 get메서드를 통하여서 만약 해당 신고자 혹은 피신고자가 존재한다면 +1 없으면 undefined인 값을 1로 변경해줍니다.

이후에 id_list에 대해서 map 메서드를 통해서 신고에 성공한 횟수를 기록해줍니다. 이때도 마찬가지로 존재 하지 않으면 undefined이기 떄문에 || 0 을 통해서 없는 경우 0을 할당해줍니다.

Map을 이용하니 키 벨류형식이라 가독성도 좋아지네요..

알고리즘을 풀면서 문제를 초기에 구상을 했을 때는, 더 빠른 방법이지 않을까 생각했는데, 직접해보니 오히려 추가 작업만 늘어나게 되었던 경우를 포스팅하려고 합니다.
//  https://school.programmers.co.kr/learn/courses/30/lessons/87389

위 문제는 나머지가 1이 되는 수를 찾는 문제입니다.

초기 구상 단계

1. 나머지가 1이되는 최소의 수를 구하는 것이기에, 차라리 n-1이 소수인지만 확인 
2. 그렇지 않다면  해당 수를 반환 .. 해당 수의 약수가 존재한다면 최소공약수를 반환
3. 범위는 타겟의 제곱근까지만 확인( 그 이상은 확인할 필요가 없으므로)
이라고 생각했다. 그렇기에 소수를 구하는 에란토스체를 사용하면 런타임을 최소화 할 수 있지 않을까 생각했습니다.

우선 간단하게 타겟 수의 제곱근보다 작은수들로 n-1을 나누어 보았습니다.

function solution2(n) {
  const min = n - 1;
  for (let i = 2; i < Math.sqrt(n); i++) {
    if (min % i === 0) {
      return i;
    }
  }
  return min;
}

이후 이전에 학습했던 에란토스체를 사용해서 나누어 보았습니다.

function solution2(n) {
  const min = n - 1;
  const prime = new Array(n + 1).fill(1);

  for (let i = 2; i < Math.sqrt(n); i++) {
    if (prime[i]) {
      if (min % i === 0) {
        return i;
      }
      // 배수값들 거르는 작업
      for (let j = i ** 2; j <= n; j += i) {
        if (prime[j]) prime[j] = 0;
      }
    }
  }
  return min;
}

오히려 더 느려졌네요.. 왜 그럴까요? 에란토스체를 소수를 판별하는 가장 빠른 방법인데?

결론부터 말하면 부가적인 작업이 오히려 많이 생겼기 떄문입니다.

문제의 목적은 사실 n-1의 최소공약수를 구하는 문제입니다.  n의 제곱근보다 작은 모든 소수를 구한 다음에 나눌 필요가 없는거죠. 

소수를 구하는 단계에서는 각각의 수가 소수인지 일일이 확인하는 것보다, 미리 소수의 배수들을 제외시키면 소수인지 판별하기 훨신 쉽습니다.

하지만 이 경우 n-1이 소수인지만 판별하면 되는데, 부가적인 작업이 오히려 더 많이 생긴 것 입니다.
그렇기에 오히려 간단한 첫 번쨰 코드의 성능이 가장 좋았던 것이죠.

추가적으로  위 코드에서는 Math.sqrt의 계산을  반복문 내에서 수행할 필요 없이, 반복문 밖에서 한 번만 계산하도록 최적화 할 수 있습니다.

function solution3(n) {
  const min = n - 1;
  const prime = new Array(n + 1).fill(1);
  const limit = Math.sqrt(n);
  for (let i = 2; i < limit; i++) {
    if (prime[i]) {
      if (min % i === 0) {
        return i;
      }
      // 배수값들 거르는 작업
      for (let j = i ** 2; j <= n; j += i) {
        if (prime[j]) prime[j] = 0;
      }
    }
  }
  return min;
}

따라서 첫 번째 정답도 가장 최적화를 한다면 아래 코드가 됩니다.

function solution(n) {
  const min = n - 1;
const limit =  Math.sqrt(n);
  for (let i = 2; i <limit; i++) {
    if (min % i === 0) {
      return i;
    }
  }
  return min;
}

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

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

프로그래머스에 있는 문제다.

소수의 정의는 자기 자신과 1을 제외한 다른 수로 나누어지지 않는 수이다.

초기에 생각한 방법은 루트값보다 작은 수로만 직접 나누어 보는 것이다.
루트값 이전까지 나누어지지 않았다면 이후의 값들 또한 나누어지지 않기 때문이다.

다만 이렇게 풀면 런타임 에러가 뜬다.

이를 해결하기 위한 방법이 에라토스테네스의_체이다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. 
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 

소수인 값들을 제외한 모든 수를 지우면서 진행하는 것이다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

이를 알고리즘으로 표현하면 아래와 같다.

function solution(nums) {
  const prime = new Array(nums + 1).fill(1);
  let count = nums - 1;
  for (let i = 2; i < Math.sqrt(nums); i++) {
    if (prime[i]) {

      for (let j = i ** 2; j <= nums; j += i) {
        if (prime[j]) count--, (prime[j] = 0);
      }
    }
  }
  console.log(count);
  return count;
}

우선 배열을 만들어서 값을 다 집어넣는다. (1에서 nums까지의 소수의 개수를 판별하는 문제임)
인덱스는 0부터 시작하기 떄문에 배열은 nums+1개로 만들고 fill함수를 통해서 전부다 1로 채워준다.

그리고 해당수의 제곱근보다 작은 수들에 대해서 확인을 한다.

배열에 있는 인덱스 값이 0이면 소수가 아니고, 1이면 최종적으로 소수이다. 하지만 1은 소수가 아니므로 count에서 미리 한 개를 뺀다.

예를 들어 10의 경우에는 i는 2부터 3까지만 실행된다 ( 10의 제곱근이 3.xxxx 이므로 )

이후 j를 통해서 i값의 제곱들만 거르기 시작한다. (이후 더 작은 j 값에서 자기보다 작은 값을 곱한 값을 걸렀기 때문이다.)
이후  i의 2배 3배 4배 형식으로 값을 확인하기 때문에 for문의 조건은 j+=i이다 

즉 i를 통해서 소수를 찾고 j를 통해서 해당 소수의 배수를 거르는 작업이다.

i가 2일때는 j에서 4를 거르고 이후 6 8 10을 걸러준다. ( 배열의 값을 0으로 만듬)
이후 3일 때는 9를 걸러준다. 
 최종적으로 배열이 11110101000 이 된다.  ( 0123 5 7의 값만 1이됨 )
이때 count는 거르는 작업에서 뺴줬기 떄문에 9개에서 5개를 뺸 4개가 되고. 1의 개수보단  배열의 2개가 적다(0과 1을 뺌)