문제 조건
- starts[i]보다 크거나 같고, e보다 작거나 같은 수 중에 억억단에서 가장 많이 등장한 숫자를 찾기
- -> starts[i]부터 e까지 약수의 갯수가 가장 많은 숫자값을 리턴
문제 풀이
- 약수의 갯수를 한번에 구해야 한다 -> 모든 숫자를 다 나눠서 구하면 시간초과
- 소인수분해를 해서 약수의 갯수를 구하는 방법으로 구한다.
- Map으로 나눠지는 수를 key로, 제곱이 되는 수를 value로 가진다.
- 모든 value + 1를 곱해주면 해당 숫자의 약수를 구할 수 있다.
- 약수의 갯수가 가장 많은 숫자를 구해야 하고, 갯수가 동일하면 가장 큰 값을 구해야하므로,
e부터 숫자를 줄여가며 약수의 갯수를 구한다. - 구한 약수의 갯수가 이전 값보다 크면 업데이트, 아니면 직전 값 그대로 2차원 배열에 저장
- starts 배열에 맞는 2차원 배열에 저장 된 숫자를 그대로 answer배열에 넣어주고
- answer배열 반환
https://school.programmers.co.kr/learn/courses/30/lessons/138475
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
참고자료
https://ksb-dev.tistory.com/253
프로그래머스 - 억억단을 외우자(Java)
구현 문제입니다. 이 문제는 약수의 개수를 통해 해결하는 문제입니다. 왜 약수의 개수의 문제를 구해야 하는지 알아보겠습니다. 이 문제의 접근은 세 단계로 이뤄집니다. 왜 약수인가? 약수의
ksb-dev.tistory.com
'Algorithms > Programmers' 카테고리의 다른 글
| [Programmers] 숫자 카드 나누기 (0) | 2022.12.04 |
|---|---|
| [Programmers] 문자열 나누기 (0) | 2022.12.03 |
| [Programmers] 택배상자 (0) | 2022.12.03 |
| [Programmers] 롤케이크 자르기 (0) | 2022.12.03 |
| [Programmers] 귤 고르기 (0) | 2022.12.03 |