반응형
📖 문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
💡 풀이 방식
• 소수/약수 (에라토스테네스의 체)
begin부터 end까지의 범위 내에 있는 숫자들 중 해당 수의 가장 큰 약수를 블록에 적는다. 단, 블록에 적는 숫자는 10,000,000 보다 작거나 같아야 한다!
또, 숫자가 1인 경우만 블록에 0을 두는 예외처리가 필요하다.
🔺 코드
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
31
32
33
34
35
36
37
38
39
|
import java.util.*;
class Solution {
static final int MAX = 10_000_000;
public List<Integer> solution(long begin, long end) {
List<Integer> answer = new ArrayList<>();
for(long i = begin ; i <= end ; i++) {
if(i == 1) { // 1인 경우만 예외처리
answer.add(0);
continue;
}
// 1이 아니면 블록에 제일 큰 약수 두기
answer.add((int)getGCD(i));
}
return answer;
}
// 블록에 둘 제일 큰 약수 구하는 메소드
private static long getGCD(long x) {
long result = 1;
for(long i = 2 ; i <= Math.sqrt(x) ; i++) {
if(x % i == 0) {
result = i;
if(x/i <= MAX) { // 블록 숫자는 MAX보다 크면 안 됨!
result = x/i;
break;
}
}
}
return result;
}
}
|
cs |
💦 어려웠던 점
- 그냥 반복문으로 갯수+1하면서 최대 약수 구할 생각을 했다.
- 10,000,000 보다 작거나 같은 수여야 한다는 조건을 놓쳤다.
- 표를 보고 dp로 풀어야하나..라는 생각을 꽤 오래 했다.
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
[Programmers] Lv2. 숫자 블록 | C++
🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. progr
daekyoulibrary.tistory.com
[프로그래머스,자바] Level2: 숫자블록
문제분석: 블록을 다음과 같은 규칙으로 칠한다. N*2 , N*3, ...일경우 블록을 칠한다. 이미 블록이 칠해져있다면 덮어서 칠한다. 여기서 칠해야하는 블록의 갯수가 무려 10억개, 각기다른 블록의색
taehoung0102.tistory.com
반응형
'코테 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/Level 3] 아이템 줍기 (JAVA) (0) | 2024.04.23 |
---|---|
[프로그래머스/Level2] [3차] 방금그곡 (JAVA) (0) | 2024.04.11 |
[프로그래머스/Level2] 후보키 (JAVA) (0) | 2024.04.08 |
[프로그래머스/Level1] 달리기 경주 (JAVA) (0) | 2024.04.06 |
[프로그래머스/Level3] 풍선 터뜨리기 (JAVA) (0) | 2024.03.29 |