링크

숫자 블록

난이도

  • 프로그래머스 난이도 4
    • 연습문제라서 어렵진 않음
    • 개인적으로 난이도 2정도

문제요약

  • 도로에 번호가 있을때 n숫자가 그려진 블록은 n*2번 n*3, n*4,…번 도로에 블록을 배치한다고 할때, 특정구간의 도로위의 블록번호의 배열을 구하라
    • 2번블록과 3번블록은 6번 위치에 배치될수 있지만 3번블록이 덮어쓰는 형식으로 6번위치에는 3번 블록이 들어간다.
    • 블록은 10000000번 블록까지만 사용한다 중요한 조건

접근

  • 이 문제는 소수를 구하는 문제와 같다.
    • 구간(begin,end)이 주어지면 반복문을 통해 n이라는 해당 숫자를 2부터 n의 제곱근까지 순차적으로 나눔으로 나머지가 없는 나눠 떨어지는 숫자를 찾으면 된다.
  • 예시
    • 21번 도로의 블럭을 구하기위해서는 20을 2~4까지 나눗셈을 진행
      • 4인 이유는 21의 제곱근은 4.xxx로 소수점 아래는 빼서 4로 사용
    • 제일 먼저 딱 나눠떨어지는것은 3으로 나눈 7이 나오며, 7번블록이 21번에 들어가게 된다.
    • 만약 나눠떨어지는게 없는경우 1번 블록을 사용
      • 1번블록은 1번 도로를 제외한 모든 도로에 한번씩 사용되기 때문

간단 알고리즘

  • 블록번호 구하기 함수
    • 도로 번호 n을 받음
    • 만약 n이 1이면 0을 반환
      • 1번 도로에 사용할 블록이 존재하지 않음
    • 반환할 블록 번호를 저장할 result선언
      • 1로 초기화
    • 2부터 n의 제곱근까지를 i로 하여 반복문 진행
      • n 나누기 i의 나머지가 0인경우
        • n나누기i가 10000000보다 크면 계속 진행
        • n나누기i가 10000000보다 작으면 result에 n나누기i를 저장 후 반복문 종료
    • result 반환
  • begin부터 end까지 n으로 하여 반복
    • 블록 번호 구하기 함수에 n을 입력후 결과를 answer 배열에 추가

후기

  • 단순 소수 구하기의 비틀기 문제
  • 연습문제로 표현된것으로 보아 소수 구하기를 알고 있는지, 그리고 해당 유형의 얼마나 이해도를 가지고 있는지 검증하는 문제로 보인다.
  • 문제에 서술된 조건인 10000000번 블록까지만 사용하는 부분을 제대로 파악못하면 효율성을 통과못하며, 문제의 조건을 제대로 읽어야 했다.