코딩테스트/프로그래머스
2022. 6. 15.
[Javascript] 숫자 블록 (12923)
문제링크 코딩테스트 연습 - 숫자 블록 1 10 [0, 1, 1, 2, 1, 3, 1, 4, 3, 5] programmers.co.kr 접근 방법 처음엔 간단하게 2중 for문을 사용하여 1 ~ end까지의 result array를 구하여 begin부터 end까지 slice하여 답을 구하였다. 그런데 주어진 begin과 end의 범위가 1 ~ 1천만으로 넒은 범위를 가지고 있어 2중 for문으로 사용하면 O(n^2)으로 이렇게 긴 시간이 걸렸다. 그래서 최대 nlogn의 시간복잡도를 갖도록 풀이를 다시 생각하였다. 고칠점 1. 1부터 end까지 모두 구하는게 너무 비효율적인거 같다 고칠점 2. 문제를 다시 보면 약수가 존재한다면 약수의 최대 값을 갖고, 약수가 존재하지 않으면 1을 갖는다는 규칙이 있다...