ONE MAN GAME DEV

내 인생에서 믿을 건 오직 나 자신뿐!

The only one you can truly trust is yourself.

게임 프로그래밍/Python 프로그래밍

프로그래머스 숫자 카드 나누기

🎮inspirer9 2023. 2. 15. 20:09

728x90

문제

문제 설명

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 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에는 중복된 원소가 있을 수 있습니다.

입출력 예

arrayA	arrayB	result
[10, 17]	[5, 20]	0
[10, 20]	[5, 17]	10
[14, 35, 119]	[18, 30, 102]	7

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

문제 예시와 같습니다.

입출력 예 #3

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

문제풀이

무지성 코딩

def solution(arrayA, arrayB):
    arrayA = list(set(arrayA))
    arrayB = list(set(arrayB))
    arrayA.sort()
    arrayB.sort()
    arrayAlen = len(arrayA)
    arrayBlen = len(arrayB)
    divisorsA = set()
    divisorsB = set()
    
    n = max(arrayA[0]+1, int(arrayA[-1]**0.5)+1)
    for i in range(2, n):
        is_break = False
        for j in arrayA:
            if j % i != 0:
                is_break = True
                break
        if is_break == False:
            divisorsA.add(i)

    n = max(arrayB[0]+1, int(arrayB[-1]**0.5)+1)
    for i in range(2, n):
        is_break = False
        for j in arrayB:
            if j % i != 0:
                is_break = True
                break
        if is_break == False:
            divisorsB.add(i)
    
    divisorsA = list(divisorsA)
    divisorsB = list(divisorsB)
    divisorsA.sort(reverse=True)
    divisorsB.sort(reverse=True)
    
    print(divisorsA, divisorsB)
    
    if len(divisorsA) == 0 and len(divisorsB) == 0:
        return 0
    elif len(divisorsA) == 0:
        # divisorsB에 있는 걸로 arrayA 나눠보기
        for i in divisorsB:
            is_break = False
            for j in arrayA:
                print(j,i)
                if j % i == 0:
                    is_break = True
                    break
            if is_break == False:
                return i
        return 0
    elif len(divisorsB) == 0:
        # divisorsA에 있는 걸로 arrayB 나눠보기
        for i in divisorsA:
            is_break = False
            for j in arrayB:
                print(j,i)
                if j % i == 0:
                    is_break = True
                    break
            if is_break == False:
                return i
    else:
        A_used = True
        B_used = True
        a = 0
        b = 0
        _t = 0
        while len(divisorsA) > 0 or len(divisorsB) > 0:
            if len(divisorsA) != 0 and A_used == True:
                A_used = False
                a = divisorsA.pop(0)
            if len(divisorsB) != 0 and B_used == True:
                B_used = False
                b = divisorsB.pop(0)
            
            if a == b:
                A_used = True
                B_used = True
                b = 0
                a = 0
            elif a > b:
                A_used = True
                is_break = False
                for j in arrayB:
                    if j % a == 0:
                        is_break = True
                        break
                if is_break == False:
                    return a
                a = 0
            else:
                B_used = True
                is_break = False
                for j in arrayA:
                    if j % b == 0:
                        is_break = True
                        break
                if is_break == False:
                    return b
                b = 0
        return 0
    
    return 0

당연하지만 코드가 길면 파이썬은 시간 초과됨

정확성  테스트
테스트 1 〉	통과 (250.26ms, 10.3MB)
테스트 2 〉	통과 (222.42ms, 10.4MB)
테스트 3 〉	통과 (284.40ms, 10.4MB)
테스트 4 〉	통과 (210.04ms, 13.3MB)
테스트 5 〉	통과 (203.27ms, 11.3MB)
테스트 6 〉	통과 (205.46ms, 11.8MB)
테스트 7 〉	통과 (203.34ms, 10.4MB)
테스트 8 〉	통과 (212.16ms, 10.4MB)
테스트 9 〉	통과 (297.72ms, 11.2MB)
테스트 10 〉	통과 (217.82ms, 10.5MB)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (시간 초과)
테스트 14 〉	실패 (시간 초과)
테스트 15 〉	실패 (시간 초과)
테스트 16 〉	실패 (시간 초과)
테스트 17 〉	실패 (시간 초과)
테스트 18 〉	실패 (시간 초과)
테스트 19 〉	통과 (0.01ms, 10.3MB)
테스트 20 〉	통과 (0.03ms, 10.4MB)
테스트 21 〉	통과 (0.03ms, 10.2MB)
테스트 22 〉	통과 (0.03ms, 10.3MB)
테스트 23 〉	통과 (4.82ms, 10.2MB)
테스트 24 〉	통과 (323.12ms, 10.3MB)
테스트 25 〉	통과 (9741.68ms, 10.3MB)
테스트 26 〉	통과 (5803.71ms, 10.5MB)
테스트 27 〉	통과 (0.35ms, 10.3MB)
테스트 28 〉	통과 (0.58ms, 10.5MB)
테스트 29 〉	통과 (0.60ms, 10.3MB)
테스트 30 〉	통과 (0.65ms, 10.3MB)
테스트 31 〉	통과 (0.91ms, 10.5MB)
테스트 32 〉	통과 (1.17ms, 10.4MB)
테스트 33 〉	통과 (177.98ms, 10.3MB)
테스트 34 〉	통과 (0.15ms, 10.3MB)
테스트 35 〉	통과 (0.09ms, 10.4MB)
테스트 36 〉	통과 (0.15ms, 10.4MB)

나의 머리가 멍청이였다. 휴먼.
문제 자체가 함정이었다. 휴먼.
- 리스트에서 최대 공약 수를 구하고, 그걸로 상대 리스트를 나눠서 0이 나오면 더 볼 필요가 없이 끝난거다.
- 앞에 짠 소스는 모든 약수를 다 계산하고 있었기 때문에 시간 초과가 났던 것...

import math

def solution(arrayA, arrayB):
    arrayA = list(set(arrayA))
    len_arrayA = len(arrayA)
    gcdA = arrayA[0]
    if len_arrayA != 1:
        for i in range(1,len_arrayA):
            gcdA = math.gcd(gcdA, arrayA[i])
            
    arrayB = list(set(arrayB))
    len_arrayB = len(arrayB)
    gcdB = arrayB[0]
    if len_arrayB != 1:
        for i in range(1,len_arrayB):
            gcdB = math.gcd(gcdB, arrayB[i])
    
    for i in arrayA:
        if i % gcdB == 0:
            gcdB = 1    
            break
    
    for i in arrayB:
        if i % gcdA == 0:
            gcdA = 1
            break
    
    if gcdA == 1:
        if gcdB == 1:
            return 0
        else:
            return gcdB
    else:
        if gcdB == 1:
            return gcdA
        else:
            return max(gcdA, gcdB)
            
정확성  테스트
테스트 1 〉	통과 (0.29ms, 10.3MB)
테스트 2 〉	통과 (1.18ms, 10.5MB)
테스트 3 〉	통과 (0.16ms, 10.2MB)
테스트 4 〉	통과 (7.02ms, 13.4MB)
테스트 5 〉	통과 (2.84ms, 11MB)
테스트 6 〉	통과 (4.73ms, 11.7MB)
테스트 7 〉	통과 (0.69ms, 10.6MB)
테스트 8 〉	통과 (0.38ms, 10.5MB)
테스트 9 〉	통과 (2.87ms, 11.2MB)
테스트 10 〉	통과 (0.16ms, 10.2MB)
테스트 11 〉	통과 (228.88ms, 82.9MB)
테스트 12 〉	통과 (271.21ms, 82.8MB)
테스트 13 〉	통과 (225.80ms, 82.8MB)
테스트 14 〉	통과 (216.91ms, 82.8MB)
테스트 15 〉	통과 (220.48ms, 82.8MB)
테스트 16 〉	통과 (215.80ms, 82.9MB)
테스트 17 〉	통과 (189.72ms, 83MB)
테스트 18 〉	통과 (222.93ms, 82.9MB)
테스트 19 〉	통과 (0.00ms, 10.2MB)
테스트 20 〉	통과 (0.01ms, 10.4MB)
테스트 21 〉	통과 (0.01ms, 10.2MB)
테스트 22 〉	통과 (0.01ms, 10MB)
테스트 23 〉	통과 (0.01ms, 10.2MB)
테스트 24 〉	통과 (0.01ms, 10.4MB)
테스트 25 〉	통과 (0.01ms, 10MB)
테스트 26 〉	통과 (0.01ms, 10.2MB)
테스트 27 〉	통과 (0.07ms, 10.4MB)
테스트 28 〉	통과 (0.05ms, 10.1MB)
테스트 29 〉	통과 (0.01ms, 10.4MB)
테스트 30 〉	통과 (0.01ms, 10.2MB)
테스트 31 〉	통과 (0.01ms, 10.2MB)
테스트 32 〉	통과 (0.01ms, 10.1MB)
테스트 33 〉	통과 (0.01ms, 10.2MB)
테스트 34 〉	통과 (0.01ms, 10.2MB)
테스트 35 〉	통과 (0.01ms, 10.2MB)
테스트 36 〉	통과 (0.01ms, 10.2MB)

그리고 배열 길이도 같네?
코드 더 줄일 수 있다.

import math
from functools import reduce

def solution(arrayA, arrayB):
    len_arrayA = len(arrayA)
    gcdA = arrayA[0]
    gcdB = arrayB[0]
    for i in range(1,len_arrayA):
        gcdA = math.gcd(gcdA, arrayA[i])
        gcdB = math.gcd(gcdB, arrayB[i])
    
    for i in arrayA:
        if i % gcdB == 0:
            gcdB = 1    
            break
    
    for i in arrayB:
        if i % gcdA == 0:
            gcdA = 1
            break
    
    if gcdA == 1:
        if gcdB == 1:
            return 0
        else:
            return gcdB
    else:
        if gcdB == 1:
            return gcdA
        else:
            return max(gcdA, gcdB)
            
정확성  테스트
테스트 1 〉	통과 (0.21ms, 10.3MB)
테스트 2 〉	통과 (0.87ms, 10.2MB)
테스트 3 〉	통과 (0.14ms, 10.2MB)
테스트 4 〉	통과 (10.44ms, 12.9MB)
테스트 5 〉	통과 (3.44ms, 10.4MB)
테스트 6 〉	통과 (4.58ms, 11.1MB)
테스트 7 〉	통과 (0.39ms, 10.3MB)
테스트 8 〉	통과 (0.56ms, 10.2MB)
테스트 9 〉	통과 (1.84ms, 10.6MB)
테스트 10 〉	통과 (0.21ms, 10.2MB)
테스트 11 〉	통과 (143.83ms, 53.3MB)
테스트 12 〉	통과 (174.65ms, 53.2MB)
테스트 13 〉	통과 (183.44ms, 53.2MB)
테스트 14 〉	통과 (217.14ms, 53.2MB)
테스트 15 〉	통과 (150.58ms, 53.2MB)
테스트 16 〉	통과 (144.12ms, 53.2MB)
테스트 17 〉	통과 (212.05ms, 53.1MB)
테스트 18 〉	통과 (139.89ms, 53.5MB)
테스트 19 〉	통과 (0.00ms, 10.2MB)
테스트 20 〉	통과 (0.01ms, 10.1MB)
테스트 21 〉	통과 (0.01ms, 10.1MB)
테스트 22 〉	통과 (0.01ms, 10.2MB)
테스트 23 〉	통과 (0.01ms, 10MB)
테스트 24 〉	통과 (0.01ms, 10.2MB)
테스트 25 〉	통과 (0.01ms, 10.1MB)
테스트 26 〉	통과 (0.01ms, 10.2MB)
테스트 27 〉	통과 (0.03ms, 10MB)
테스트 28 〉	통과 (0.04ms, 10.2MB)
테스트 29 〉	통과 (0.00ms, 10.2MB)
테스트 30 〉	통과 (0.00ms, 10MB)
테스트 31 〉	통과 (0.01ms, 10.1MB)
테스트 32 〉	통과 (0.00ms, 10.2MB)
테스트 33 〉	통과 (0.01ms, 10.4MB)
테스트 34 〉	통과 (0.01ms, 9.97MB)
테스트 35 〉	통과 (0.01ms, 10.1MB)
테스트 36 〉	통과 (0.01ms, 10.2MB)

코드 줄이기

import math
from functools import reduce

def solution(arrayA, arrayB):
    len_arrayA = len(arrayA)
    gcdA = arrayA[0]
    gcdB = arrayB[0]
    
    for i in range(1,len_arrayA):
        gcdA = math.gcd(gcdA, arrayA[i])
        gcdB = math.gcd(gcdB, arrayB[i])
    
    for i in reversed(arrayA):
        if i % gcdB == 0:
            gcdB = 1    
            break
    
    for i in reversed(arrayB):
        if i % gcdA == 0:
            gcdA = 1
            break
    
    if gcdA == gcdB:
        return 0
    else:
        return max(gcdA, gcdB)
        
정확성  테스트
테스트 1 〉	통과 (0.37ms, 10.2MB)
테스트 2 〉	통과 (1.54ms, 10.1MB)
테스트 3 〉	통과 (0.08ms, 10.2MB)
테스트 4 〉	통과 (10.02ms, 12.8MB)
테스트 5 〉	통과 (2.36ms, 10.2MB)
테스트 6 〉	통과 (5.05ms, 11MB)
테스트 7 〉	통과 (0.35ms, 10.1MB)
테스트 8 〉	통과 (0.32ms, 10.2MB)
테스트 9 〉	통과 (3.44ms, 10.5MB)
테스트 10 〉	통과 (0.11ms, 10.1MB)
테스트 11 〉	통과 (147.29ms, 53.2MB)
테스트 12 〉	통과 (148.26ms, 53.4MB)
테스트 13 〉	통과 (159.85ms, 53.3MB)
테스트 14 〉	통과 (174.96ms, 53.4MB)
테스트 15 〉	통과 (169.69ms, 53.2MB)
테스트 16 〉	통과 (171.18ms, 53.2MB)
테스트 17 〉	통과 (136.89ms, 53.4MB)
테스트 18 〉	통과 (168.21ms, 53.3MB)
테스트 19 〉	통과 (0.00ms, 10.1MB)
테스트 20 〉	통과 (0.01ms, 10.1MB)
테스트 21 〉	통과 (0.01ms, 10.1MB)
테스트 22 〉	통과 (0.03ms, 10.1MB)
테스트 23 〉	통과 (0.02ms, 10.2MB)
테스트 24 〉	통과 (0.01ms, 10.1MB)
테스트 25 〉	통과 (0.01ms, 10.1MB)
테스트 26 〉	통과 (0.01ms, 10MB)
테스트 27 〉	통과 (0.06ms, 10MB)
테스트 28 〉	통과 (0.05ms, 10.1MB)
테스트 29 〉	통과 (0.01ms, 10.1MB)
테스트 30 〉	통과 (0.01ms, 10.1MB)
테스트 31 〉	통과 (0.00ms, 10.2MB)
테스트 32 〉	통과 (0.01ms, 10.1MB)
테스트 33 〉	통과 (0.01ms, 10.1MB)
테스트 34 〉	통과 (0.01ms, 10.2MB)
테스트 35 〉	통과 (0.01ms, 10.1MB)
테스트 36 〉	통과 (0.01ms, 10MB)

다 풀고나면 쉬운데, 풀기전까지는 참 어렵네... 400의 벽을 뚫기가 이렇게 힘드나?

아참 고수의 풀이 리듀스를 이렇게 쓰는 거였구나. reduce 써보려다가 공부가 덜되서 포기했는데 ㅎㅎㅎ

from math import gcd
from functools import reduce

def check(arrayA, arrayB):
    gcd_A = reduce(gcd, arrayA, arrayA[0])
    factors = [i for i in range(1, gcd_A//2+1) if not gcd_A % i]
    factors.append(gcd_A)
    for factor in factors[::-1]:
        if all(i % factor for i in arrayB):
            return gcd_A
    return 0

def solution(arrayA, arrayB):
    return max(check(arrayA, arrayB), check(arrayB, arrayA))
    
정확성  테스트
테스트 1 〉	통과 (0.42ms, 10.3MB)
테스트 2 〉	통과 (0.76ms, 10.3MB)
테스트 3 〉	통과 (0.59ms, 10.2MB)
테스트 4 〉	통과 (8.17ms, 12.9MB)
테스트 5 〉	통과 (2.45ms, 10.5MB)
테스트 6 〉	통과 (5.01ms, 11.2MB)
테스트 7 〉	통과 (0.50ms, 10.3MB)
테스트 8 〉	통과 (1.00ms, 10.3MB)
테스트 9 〉	통과 (2.36ms, 10.6MB)
테스트 10 〉	통과 (0.53ms, 10.2MB)
테스트 11 〉	통과 (95.66ms, 53.4MB)
테스트 12 〉	통과 (117.54ms, 53.5MB)
테스트 13 〉	통과 (84.06ms, 53.4MB)
테스트 14 〉	통과 (89.90ms, 53.4MB)
테스트 15 〉	통과 (110.30ms, 53.5MB)
테스트 16 〉	통과 (89.00ms, 53.5MB)
테스트 17 〉	통과 (82.23ms, 53.5MB)
테스트 18 〉	통과 (141.29ms, 53.3MB)
테스트 19 〉	통과 (0.01ms, 10.2MB)
테스트 20 〉	통과 (0.01ms, 10.2MB)
테스트 21 〉	통과 (0.02ms, 10.2MB)
테스트 22 〉	통과 (0.02ms, 10.2MB)
테스트 23 〉	통과 (0.02ms, 10.2MB)
테스트 24 〉	통과 (0.03ms, 10.3MB)
테스트 25 〉	통과 (0.06ms, 10.4MB)
테스트 26 〉	통과 (0.20ms, 9.96MB)
테스트 27 〉	통과 (0.04ms, 10.4MB)
테스트 28 〉	통과 (0.05ms, 10.2MB)
테스트 29 〉	통과 (0.01ms, 10.2MB)
테스트 30 〉	통과 (0.41ms, 10.3MB)
테스트 31 〉	통과 (0.39ms, 10.2MB)
테스트 32 〉	통과 (0.06ms, 10.4MB)
테스트 33 〉	통과 (0.01ms, 10.1MB)
테스트 34 〉	통과 (0.02ms, 10.4MB)
테스트 35 〉	통과 (0.03ms, 10.3MB)
테스트 36 〉	통과 (0.02ms, 10.2MB)

728x90

저작자표시 동일조건

'게임 프로그래밍 > Python 프로그래밍' 카테고리의 다른 글

프로그래머스 두 큐 합 같게 만들기 (0)	2023.02.16
프로그래머스 우박수열 정적분 (0)	2023.02.15
프로그래머스 테이블 해시 함수 (0)	2023.02.15
프로그래머스 디펜스 게임 (0)	2023.02.15
프로그래머스 점 찍기 (0)	2023.02.14

현재글프로그래머스 숫자 카드 나누기

ONE MAN GAME DEV

프로그래머스 숫자 카드 나누기

문제

문제 설명

제한사항

입출력 예

입출력 예 설명

문제풀이

'게임 프로그래밍 > Python 프로그래밍' 카테고리의 다른 글

'게임 프로그래밍/Python 프로그래밍'의 다른글

티스토리툴바

프로그래머스 숫자 카드 나누기

문제

문제 설명

제한사항

입출력 예

입출력 예 설명

문제풀이

'게임 프로그래밍 > Python 프로그래밍' 카테고리의 다른 글

'게임 프로그래밍/Python 프로그래밍'의 다른글

관련글

티스토리툴바