You Nicholas

가고 가고 또 가면 알게되고, 행하고 행하고 또 행하게 되면 이루게 된다.

1 분 소요

1. 문제

[level 2] 숫자 블록 - 12923

문제 링크

성능 요약

메모리: 10.2 MB, 시간: 727.81 ms

구분

코딩테스트 연습 > 연습문제

채점결과


정확성: 70.0
효율성: 30.0
합계: 100.0 / 100.0

문제 설명

그렙시에는 0으로 된 도로에 숫자 블록을 설치하기로 하였습니다. 숫자 블록의 규칙은 다음과 같습니다.

블록의 번호가 n 일 때, 가장 처음 블록은 n * 2번째 위치에 설치합니다. 그다음은 n * 3, 그다음은 n * 4, ...로 진행합니다.만약 기존에 블록이 깔려있는 자리라면 그 블록을빼고 새로운 블록으로 집어넣습니다.

예를 들어 1번 블록은 2,3,4,5, ... 인 위치에 우선 설치합니다. 그다음 2번 블록은 4,6,8,10, ... 인 위치에 설치하고, 3번 블록은 6,9,12... 인 위치에 설치합니다.

이렇게 3번 블록까지 설치하고 나면 첫 10개의 블록은 0, 1, 1, 2, 1, 3, 1, 2, 3, 2이됩니다.

그렙시는 길이가 1,000,000,000인 도로에 1번 블록부터 시작하여 10,000,000번 블록까지 위의 규칙으로 모두 놓았습니다.

그렙시의 시장님은 특정 구간의 어떤 블록이 깔려 있는지 알고 싶습니다.

구간을 나타내는 두 수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열(리스트)을 return하는 solution 함수를 완성해 주세요.

제한 사항
  • begin, end 는 1 이상 1,000,000,000이하의 자연수 이고, begin는 항상 end보다 작습니다.
  • end - begin 의 값은 항상 10,000을 넘지 않습니다.
입출력 예
begin end result
1 10 [0, 1, 1, 2, 1, 3, 1, 4, 3, 5]
입출력 예 설명

입출력 예 #1
다음과 같이 블럭이 깔리게 됩니다.
Imgur

※ 공지 - 2019년 4월 07일 테스트케이스가 변경되었습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

2. 해결방법 시간복잡도

  1. 소수 판별 O(N^2)

3. 문제 해결 및 코드

  • 주석을 참고하면서 이해를 돕습니다.

4. 알고리즘 및 해설

  1. 확실히 프로그래머스 level 2부터는 문제를 해석하는데 시간이 조금 걸리는 것 같다.
    • 이번 문제의 경우 흔히 말하는 소수 판별 알고리즘을 사용해서 풀이가 가능하다. 그 중 에라토스테네스의 체가 있지만 보다 단순하게 가능했다.
  2. 반복문을 통해서 begin부터 end를 포함한 값까지 받아준다.
    • 이떄 해당 값이 1이라면 0으로 받아주고, 1인 경우 0으로 받아준다.
  3. 받은 값이 소수인지 아닌 지 알기 위해서 소수 판별에 사용되는 반복문인 for i in range(a, math.sqrt(b) + 1)) 형식을 사용해준다.
    • 이때 math.sqrt()를 사용하는 이유는 소수는 자기 자신과 1을 제외한 수는 있으면 안되는데, 배수의 경우 자기를 포함한 약수가 존재하므로 소수가 아니기에 제곱근을 사용해주는 것이다.
      • math 라이브러리를 사용하면 편한데 이때 b ** 0.5와 같은 방법도 있다.
  4. 이때 문제에서 제시한 10000000번째 블록을 기준으로 해당 값보다 작은 경우에만 값을 업데이트해주고 break를 걸어준다.
  5. 위의 과정을 반복을 통해서 우리가 원하는 값이 리스트에 전부 들어간 뒤 최종 출력해준다.

참고