Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- Node
- 해시
- 자료구조
- 프로그래머스
- 리액트
- react
- 정렬
- 연결리스트
- 브루트포스
- JavaScript
- node.js
- BOJ
- hash
- 완전탐색
- 알고리즘
- 코딩테스트
- 백준
- useState
- state
- 코테
- 병합 정렬
- 기술면접
- sort
- 합병 정렬
- 최소공배수
- 자바스크립트
- 딥다이브
- CSS
- 정규표현식
- JS
Archives
- Today
- Total
가치투자자
[BOJ] 2501번 : 약수 구하기 본문
728x90
반응형
백준 2501번 : 약수 구하기
🔗 문제 링크
https://www.acmicpc.net/problem/2501
2501번: 약수 구하기
첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.
www.acmicpc.net
💬 문제
약수 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다.
- 자연수 N의 약수 중 K번째로 작은 약수를 구해 출력해준다.
- 1번째 줄에 N과 K가 공백을 기준으로 주어진다
💡 입력값 받아오기
JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.
이 문제에서는 1번째 줄에 N과 K를 주고 있다. 공백을 기준으로 N과 K를 잘라주고 정수화해주면 된다.
입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.
https://valueengine.tistory.com/2
[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅
1. Node.js fs모듈 사용법 백준에서 JavaScript로 문제를 풀기 위해선 Node.js를 사용해야 하며, 이때 readline 모듈이나 fs 모듈로 입력값(input)을 받아와야 한다. 이 중 속도나 코드의 길이, 작성 편리성에
valueengine.tistory.com
728x90
💻 풀이
이 문제는 나누는 수의 범위와 약수를 찾는 방법에 따라 총 3가지 방식으로 풀 수 있다.
🔑 풀이1 : 모든 수로 나눠 약수 구하기
- 공백을 기준으로 잘라주고, N과 K를 정수화해준다.
- for문으로 2부터 N까지 모든 수로 N을 나눠 약수 배열 divisor을 채워준다.
- 1은 항상 약수이므로, 미리 약수 배열 divisor에 넣어준다. - K번째 약수가 존재하려면 배열의 길이는 K보다 크거나 같아야 한다.
- K번째로 작은 약수를 출력해주거나, 0을 출력해준다.
// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);
[N, K] = input;
console.log(solution(N, K));
function solution(N, K) {
const divisor = [1]; // 약수 (배열)
for (let i=2; i <= N; i++) {
if (N % i === 0) { // 약수일 때
divisor.push(i);
}
}
if (divisor.length < K) {
return 0; // K번째 약수가 없을 경우 (K가 배열길이보다 클 때)
} else {
return divisor[K-1];
}
};
시간은 다음과 같이 걸렸다.
🔑 풀이2 : 제곱근 범위까지만 나눠 약수 구하기
- 공백을 기준으로 잘라주고, N과 K를 정수화해준다.
- for문으로 모든 수를 도는 것보다 제곱근까지 도는 것이 조금 더 효율적이다.
- Math.sqrt() 메서드로 제곱근을 구할 수 있다.
- i가 약수일 때, N을 i로 나눈 수도 약수이기에 동시에 배열 divisor에 추가해준다.
- 제곱근이 약수와 같을 땐, 약수 하나만 추가해야 한다 (예시> 5 X 5)
- K번째 약수가 존재하려면 배열의 길이는 K보다 크거나 같아야 한다.
- K번째로 작은 약수를 출력해주거나, 0을 출력해준다.
- 약수 i의 상대값도 동시에 추가해줬기에 정렬해줘야 한다.
// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);
[N, K] = input;
console.log(solution(N, K));
function solution(N, K) {
const divisor = [];
for (let i=1; i <= Math.sqrt(N); i++) { // 제곱근까지만 나눠주기
if (i * i === N) { // 약수 = 제곱근
divisor.push(i);
} else if (N % i === 0) { // 약수일 때
divisor.push(i);
divisor.push(N / i);
}
}
if (divisor.length < K) {
return 0; // K번째 약수가 없을 경우 (K가 배열길이보다 클 때)
} else {
return divisor.sort((a,b) => a - b)[K-1]; // K번째 약수 출력
}
};
제곱근까지만 for문을 돌렸기에 아주 약간 더 시간이 빨라졌다.
🔑 풀이3 : K의 값을 역산하여 K번째로 작은 약수 찾기
- 공백을 기준으로 잘라주고, N과 K를 정수화해준다.
- for문으로 1부터 N까지 모든 수로 N을 나눠주고, 약수가 있을 때마다 K의 값에서 1을 빼준다.
- K가 0이 되었을 때, 약수 i를 출력해준다.
- K번째 약수가 없다면, 0을 출력해준다
- K번째 약수가 없다면, K는 0이 되지 못한다.
// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);
[N, K] = input;
console.log(solution(N, K));
function solution(N, K) {
for (let i=1; i <= N; i++) {
if (N % i === 0) { // 약수일 때 K-1
K--;
}
if (K === 0) { // K번째로 작은 약수
return i;
}
}
return 0; // K번째 약수가 없을 경우 (K가 0이 되지 못했을 때)
};
시간은 다음과 같이 걸렸다.
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
[BOJ] 5086번 : 배수와 약수 (0) | 2023.04.08 |
---|---|
[BOJ] 9506번 : 약수들의 합 (0) | 2023.04.06 |
[BOJ] 11004번 : K번째 수 (0) | 2023.04.05 |
[BOJ] 11650번 : 좌표 정렬하기 (0) | 2023.04.04 |
[BOJ] 10814번 : 나이순 정렬 (0) | 2023.04.02 |