반응형
https://school.programmers.co.kr/learn/courses/30/lessons/135807
package Programmers;
import java.util.*;
public class 숫자카드나누기 {
public static void main(String[] args){
숫자카드나누기 T = new 숫자카드나누기();
int[] arrayA = {14, 35, 119};
int[] arrayB = {18, 30, 102};
T.solution(arrayA, arrayB);
}
public int solution(int[] arrayA, int[] arrayB) {
int answer = 0;
//순서대로 정렬
Arrays.sort(arrayA);
Arrays.sort(arrayB);
//Key의 큰수 부터 꺼내기위해서 TreeMap 사용
TreeMap<Integer, Integer> divisorMap = new TreeMap<>();
//arrayA돌면서 divisorMap에 담는다.
for (int i = 1; i <= arrayA[0]; i++) {
boolean isDivisor = true;
for (int iArr:arrayA) {
if(iArr % i != 0) {
isDivisor = false;
break;
}
}
if(isDivisor){
divisorMap.put(i, 0);
}
}
// arrayB돌면서 공약수가 이미 배열에 들어있음 삭제하고 없으면 추가한다;
for (int i = 1; i <= arrayB[0]; i++) {
boolean isDivisor = true;
for (int iArr:arrayB) {
if(iArr % i != 0) {
isDivisor = false;
break;
}
}
if(isDivisor){ //공약수 t, f
if(divisorMap.containsKey(i)){
divisorMap.remove(i); //이미 공약수 배열에 들어있으면 삭제
}else{
divisorMap.put(i, 1); //없으면 추가
}
}
}
//두배열의 공약수가 들어있는 Map이 전부 없어질때까지 탐색
while (!divisorMap.isEmpty()){
int division = divisorMap.lastKey();
boolean isDivision = true;
//value가 1이면 arrayB 의 약수
if(divisorMap.get(division) == 1){
//arrayA 의 약수를 탐색하면서 약수가 있는지 비교
for (int iArr:arrayA) {
if(iArr % division == 0){
isDivision = false;
divisorMap.remove(division);
break;
}
}
}else{
//arrayB 의 약수
for (int iArr:arrayB) {
if(iArr % division == 0){
isDivision = false;
divisorMap.remove(division);
break;
}
}
}
//isDivision이 T 면 상대편에 약수가 없다는뜻
if(isDivision){
answer = division;
break;
}
}
return answer;
}
}
1. arrayA 돌면서 divisorMap에 약수들 집어넣음 (TreeMap을 쓴이유는 어느 배열의 약수인지 확인과 최대값부터 비교하기위해서 )
2. arrayB 돌면서 divisorMap에 추가한다. 이미 있는거면 지운다. 둘다 약수가 되는수는 답이 아니기 때문에
3. divisorMap에 추가된 값들을 큰수부터 탐색한다.
4. value값에따라서 상대편 배열을 탐색.
반응형
'기타 > 알고리즘' 카테고리의 다른 글
[알고리즘] 프로그래머스 옹알이2 lv1 java (0) | 2023.05.08 |
---|---|
[알고리즘] 프로그래머스 - 기사단원의무기 Lv.1 (java) (0) | 2023.05.08 |
[알고리즘] 프로그래머스 - 귤고르기 java 정렬활용 (0) | 2023.05.03 |
[알고리즘] 프로그래머스 -명예의전당 (Java) queue - Lv.1 (0) | 2023.05.01 |
[알고리즘] 프로그래머스 - 점찍기 (Java) (0) | 2023.04.30 |