블로그 메뉴

    Tonkatsu
    Developer Lee
    Tonkatsu
    전체 방문자
    오늘
    어제
    • 분류 전체보기 (52)
      • Frontend (7)
        • React (3)
        • JavaScript (3)
        • HTML\CSS (1)
        • etc (0)
      • Backend (0)
        • Python\Django (0)
        • etc (0)
      • CS (32)
        • Algorithm\Coding Test (19)
        • Computer Science (8)
        • devops (5)
        • etc (0)
      • Languages (5)
        • Javascript (5)
        • Python (0)
        • etc (0)
      • 비상다반 (3)
      • 학원 (4)

    인기 글

    태그

    • CSS
    • 프로그래머스
    • CS
    • javascript
    • 네트워크
    • js
    • Git
    • Push
    • fetch
    • 코테
    • HTML
    • BFS
    • 백준
    • merge
    • 리트코드
    • leetcode
    • 코딩테스트
    • 프론트엔드
    • DFS
    • 자바스크립트

    최근 댓글

    최근 글

    티스토리

    hELLO · Designed By 정상우.
    Tonkatsu

    Developer Lee

    프로그래머스 : 소수 찾기-javascript
    CS/Algorithm\Coding Test

    프로그래머스 : 소수 찾기-javascript

    2021. 12. 20. 17:55

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

     

    코딩테스트 연습 - 소수 찾기

    1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상

    programmers.co.kr

    문제 설명

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

    소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
    (1은 소수가 아닙니다.)

    제한 조건
    • n은 2이상 1000000이하의 자연수입니다.
    입출력 예
    n result
    10 4
    5 3
    입출력 예 설명

    입출력 예 #1
    1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

    입출력 예 #2
    1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

     

    풀이

    n이 굉장히 크기 때문에 O(n^2)의 일반적인 2중 반복문으로는 시간초과가 나버린다.

    따라서 에라토스테네스의 체를 이용하여 문제를 푸는 것이 좋다.

     

    function solution(n) {
      let arr = Array.from(Array(n + 1).fill(true)).fill(false, 0, 2);
    
      for (let i = 2; i * i <= n; i++) {
        if (arr[i]) {
          for (let j = i * 2; j <= n; j += i) {
            arr[j] = false;
          }
        }
      }
      return arr.filter((x) => x).length;
    }

     

    조금이라도 시간을 줄이기 위해서 배열을 true로만 채웠는데, 실제 소수를 구하기 위해서는 true 대신 index로 fill을 하면 된다.

     

    저작자표시 (새창열림)

    'CS > Algorithm\Coding Test' 카테고리의 다른 글

    프로그래머스 : 다리를 지나는 트럭-javascript  (0) 2021.12.22
    프로그래머스 : H-index-javascript  (2) 2021.12.20
    백준 : 7576-javascript  (0) 2021.12.18
    백준 : 11650-javascript  (0) 2021.12.17
    백준 : 2178-javascript  (0) 2021.12.12
      'CS/Algorithm\Coding Test' 카테고리의 다른 글
      • 프로그래머스 : 다리를 지나는 트럭-javascript
      • 프로그래머스 : H-index-javascript
      • 백준 : 7576-javascript
      • 백준 : 11650-javascript
      Tonkatsu
      Tonkatsu
      한 번 뿐인 인생 편하게 살고싶지만 그러려면 열심히 살아야 되니까 열심히 살려고 노력은 하지만 편하게 사는 사람

      티스토리툴바