99클럽 코테 스터디 2일차 TIL 숫자 카드 나누기

nastorond 2024. 7. 23. 21:20

숫자 카드 나누기

문제 설명

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.

철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
예를 들어, 카드들에 10, 5, 20, 17이 적혀 있는 경우에 대해 생각해 봅시다. 만약, 철수가 [10, 17]이 적힌 카드를 갖고, 영희가 [5, 20]이 적힌 카드를 갖는다면 두 조건 중 하나를 만족하는 양의 정수 a는 존재하지 않습니다. 하지만, 철수가 [10, 20]이 적힌 카드를 갖고, 영희가 [5, 17]이 적힌 카드를 갖는다면, 철수가 가진 카드들의 숫자는 모두 10으로 나눌 수 있고, 영희가 가진 카드들의 숫자는 모두 10으로 나눌 수 없습니다. 따라서 철수와 영희는 각각 [10, 20]이 적힌 카드, [5, 17]이 적힌 카드로 나눠 가졌다면 조건에 해당하는 양의 정수 a는 10이 됩니다.

철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA와 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayB가 주어졌을 때, 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return하도록 solution 함수를 완성해 주세요. 만약, 조건을 만족하는 a가 없다면, 0을 return 해 주세요.

A 배열의 모든 숫자를 나눌 수 있는 모든 숫자 a, B 배열의 모든 숫자를 나눌 수 있는 모든 숫자 b 를 구한 뒤,
A 배열을 b로 모두 나눌 수 없다면 조건을 만족하는 방식
만약 a, b 둘 다 조건에 만족하는 숫자라면 그 중 큰 숫자 리턴.

문제풀이

문제를 보자마자 gcd 를 활용하는게 좋을 것 같다고 생각했고, algorithm 헤더에 있는 __gcd() 함수를 사용했다.
각 배열의 gcd 를 구해주고 조건에 맞는 지 확인하는 방향으로 정직하게 풀이했다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int gcdVal (vector<int> arr) {
    if (arr.size() == 1) return arr[0];

    int res = *arr.begin();
    for (auto it = arr.begin()+1; it != arr.end(); it++) {
        res = __gcd(res, *it);
    }
    return res;
}

bool check (int val, vector<int> arr) {
    for (auto it=arr.begin(); it!=arr.end(); it++) {
        if (*it%val == 0) return false;
    }
    return true;
}

int solution(vector<int> arrayA, vector<int> arrayB) { 
    int gcdA = gcdVal(arrayA);
    int gcdB = gcdVal(arrayB);

    cout << gcdA << " " << gcdB << "\n"; 

    bool ck1 = check(gcdA, arrayB);
    bool ck2 = check(gcdB, arrayA);

    if (ck1 && ck2) return gcdA > gcdB ? gcdA : gcdB;
    if (ck1) return gcdA;
    if (ck2) return gcdB;

    return 0;

}

회고

처음 gcdVal 함수에서 조건 설정을 이상하게 하고 못찾아서 애먹었다. 이런 실수를 줄일 수 있도록 하는 방향으로 공부를 해야할듯.
코드를 작성할 때, 설계를 마치고 작성한 뒤에 수정 사항이 생기면 꼼꼼하게 살펴보고 어떤부분에서 새로운 오류가 발생할 수 있는 지 유심히 살펴봐야된다는 것을 다시 깨달았다.
이번 문제같은 경우에도 핵심이 되는 알고리즘은 10분 내외로 작성이 끝났지만, 디버깅에서 1시간 가까이 사용했다. 이런 시간만 줄일 수 있으면 코테에서도 문제풀이 하는데 도움이 될듯