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 | 31 |
Tags
- Binary Tree
- Tree
- Method
- greedy
- bit manipulation
- Data Structure
- Binary Search
- 코딩테스트
- 코테
- string
- Counting
- geometry
- Stack
- Number Theory
- implement
- dynamic programming
- Math
- 구현
- java
- hash table
- Matrix
- array
- SQL
- 자바
- two pointers
- simulation
- Class
- sorting
- 파이썬
- database
Archives
- Today
- Total
코린이의 소소한 공부노트
[프로그래머스/Lv.1] 최대공약수와 최소공배수 본문
1. Input
1) 자연수 n
2) 자연수 m
2. Output
1) 두 수의 최대공약수와 최소공배수를 담은 배열
3. Constraint
1) n, m은 1 이상 1,000,000 이하의 자연수
4. Example
Input: n=3, m=12 -> Output: {3, 12}
5. Code
1) 첫 코드(2022/??)
int x, y;
if(n>m) {
x = m; y = n;
}
else {
x = n; y = m;
} // 둘 중 작은 수가 x, 큰 수가 y
int[] answer = {x, y}; // y가 x의 배수일때를 디폴트 값으로
if(y%x != 0) { // y가 x의 배수가 아닐 때 실행
for(int i=x-1 ; i>0 ; i--) { // x-1부터 1씩 줄여가면서
if( x%i==0 && y%i==0) { // 공약수를 찾으면
answer[0] = i; // 처음 나오는 i값이 최대공약수
answer[1] = x*y/i; // 두 수의 곱 = 최대공약수 * 최소공배수
break;
}
} // for i
}
return answer;
2) 조금 더 간결하게 바꿔본 코드(2022/11/23)
int big = Math.max(n,m);
int small = Math.min(n,m);
int[] answer = {small, big}; // big이 small의 배수라고 가정
if(big%small!=0){
for(int i=small-1 ; i>0 ; i--)
if(big%i==0 && small%i==0){
answer[0] = i;
answer[1] = big/i*small; // 두 수의 곱 = 최대공약수 * 최소공배수
break;
}
}
return answer;
- big*small*i 보다 big/i*small이 계산이 빨랐다.
'코딩테스트 풀이 > JAVA' 카테고리의 다른 글
[프로그래머스/Lv.2] 피보나치 수 (0) | 2022.11.23 |
---|---|
[프로그래머스/Lv.2] 최댓값과 최솟값 (0) | 2022.11.23 |
[프로그래머스/Lv.1] 콜라츠 추측 (0) | 2022.11.23 |
[프로그래머스/Lv.1] 평균 구하기 (0) | 2022.11.23 |
[프로그래머스/Lv.1] 하샤드 수 (0) | 2022.11.23 |