프로그래머스 Level 2 : 숫자 카드 나누기 C언어

▶문제 : 코딩테스트 연습 - 숫자 카드 나누기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

▶코드 작성

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int arrayA[], size_t arrayA_len, int arrayB[], size_t arrayB_len) {
    int minA = arrayA[0], minB = arrayB[0];
    int num;
    bool t;

    //각 배열에서 가장 작은 값 구하기
    for (int i = 1; i < arrayA_len; i++) if (arrayA[i] < minA) minA = arrayA[i];
    for (int i = 1; i < arrayB_len; i++) if (arrayB[i] < minB) minB = arrayB[i];

    for (num = minA; num >= 2; num--) {//배열 A부터
        if (minA % num == 0) {//num이 minA의 약수일 때
            t = true;
            for (int j = 0; j < arrayA_len && t; j++) {//배열 A 전체탐색
                if (arrayA[j] % num != 0) t = false;//num이 약수가 아니라면 false
            }
            for (int j = 0; j < arrayB_len && t; j++) {//배열 B 전체탐색
                if (arrayB[j] % num == 0) t = false;//num이 약수라면 false
            }
            if (t) break;//배열 A의 약수이고, 배열 B의 약수가 아니라면 종료
        }
    }

    for (int i = minB; i > num; i--) {//약수 i를 찾을 때 num보다 큰 값 찾기
        if (minB % i == 0) {//i가 minB의 약수일 때
            t = true;
            for (int j = 0; j < arrayB_len && t; j++) {//배열 B 전체탐색
                if (arrayB[j] % i != 0) t = false;//i가 약수가 아니라면 false
            }
            for (int j = 0; j < arrayA_len && t; j++) {//배열 A 전체탐색
                if (arrayA[j] % i == 0) t = false;//i가 약수라면 false
            }
            if (t) return i;//배열 B의 약수이고, 배열 A의 약수가 아니고, 가장 큰 정수이므로 반환
        }
    }

    if (num == 1) return 0;//조건에 만족하는 값이 존재하지 않음
    else return num;//가장 큰 정수이므로 반환
}

 

▶해석

양쪽 배열의 약수를 찾아야 하므로 각 배열에서 가장 작은 값 minA, minB을 구한다.

for문으로 minA의 약수를 구한 뒤 두 가지 조건 중 하나인

배열 A의 모든 숫자를 나눌 수 있고, 배열 B의 모든 숫자들 중 하나라도 나누지 못하는 약수 num을 구한다.

 

약수 num을 구하더라도 가장 큰 정수를 반환해야 하므로

for문으로 minB의 약수를 구한 뒤 다른 하나의 조건인

배열 B의 모든 숫자를 나눌 수 있고, 배열 A의 모든 숫자들 중 하나라도 나누지 못하는 약수 i를 구한다.

이때, 약수 i는 무조건 num보다 큰 값이므로 바로 i를 반환한다.