[1스4코1파] #107. LV 2. 숫자 카드 나누기

gunny·2023년 4월 20일

1스4코1파 코딩테스트 코딩테스트 python 프로그래머스 숫자 카드 나누기 프로그래머스 숫자 카드 나누기 python

코딩테스트

목록 보기

107/530

[1스4코1파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 1명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (107일차)
[4코1파] 2023.01.13~ (98일차)
[1스4코1파] 2023.04.12~ (9일차)

Today :

2023.04.20 [107일차]

프로그래머스 LV 2
숫자 카드 나누기
https://school.programmers.co.kr/learn/courses/30/lessons/135807

문제 설명
철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 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 해 주세요.

제한사항

1 ≤ arrayA의 길이 = arrayB의 길이 ≤ 500,000
1 ≤ arrayA의 원소, arrayB의 원소 ≤ 100,000,000
arrayA와 arrayB에는 중복된 원소가 있을 수 있습니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.
입출력 예 #2

문제 예시와 같습니다.
입출력 예 #3

철수가 가진 카드에 적힌 숫자들은 모두 3으로 나눌 수 없고, 영희가 가진 카드에 적힌 숫자는 모두 3으로 나눌 수 있습니다. 따라서 3은 조건에 해당하는 양의 정수입니다. 하지만, 철수가 가진 카드들에 적힌 숫자들은 모두 7로 나눌 수 있고, 영희가 가진 카드들에 적힌 숫자는 모두 7로 나눌 수 없습니다. 따라서 최대값인 7을 return 합니다.

문제 풀이 방법

주어진 array들의 최대공약수들을 구해서, 비교하면 되는 로직이라서
좀 쉬워보이는데 array 변수에 담긴 [10,20] 리스트 안에 담긴 int형 자료형을 array들을 math.gcd(10,20) 이렇게 넣는 방법에서 1차로 애를 먹었고..
=> 이거는 첫번째 인덱스를 다른 변수에 넣어두고, 나머지 인덱스부분으로 for문으로 돌아가면서 핸들링하면서 해결함

그 이후에 이제 구해진 최대공약수를 각 array들에 담긴 원소와 비교하면 되는 문제

왠걸.. 테스트 코드 35에서 걸림

영문을 몰라서 살펴보니

A = [10, 20]; B = [5, 17, 20]의 사례와 같이 B[0], B[1]은 A의 gcd로 나누어지지 않다가 B[2]가 A의 gcd로 나누어지는 경우, A의 gcd는 답이 될 수 없음에도 불구하고 이미 배열 l에 append 되어 있으므로 max(l)에 의하여 A의 gcd가 return 되는 문제
라고 한다..

그래서 뒷부분에 조건을 더 걸어 줌

for 문에 for문에 if에 elif문을 더해서
더하고 더하고 티기고 티기고 티기고

내 코드

from math import gcd

def solution(arrayA, arrayB):
    answer = []
    gcdA, gcdB = arrayA[0], arrayB[0]
    for a,b in zip(arrayA[1:], arrayB[1:]):
        gcdA, gcdB = gcd(a, gcdA), gcd(b, gcdB)
        
    for a in arrayA:
        if gcdB==1:
            break
        elif a % gcdB ==0:
            gcdB=1
            break
        else:
            answer.append(gcdB)
            
    for b in arrayB:
        if gcdA ==1:
            break
        elif b % gcdA ==0:
            gcdA=1
            break
        else:
            answer.append(gcdA)
    
    if gcdA ==1 and gcdB ==1:
        return 0
    else:
        return max(answer) if answer else 0

증빙