20210206, 프로그래머스 문제

001 모의고사

문제설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...

2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...

3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

문제해석

• 수포자1이 문제를 찍는 패턴 [1, 2 ,3, 4 5]
• 수포자2가 문제를 찍는 패턴 [2, 1, 2, 3, 2, 4, 2, 5] :[2, 1] → [2, 3] → [2, 4] → [2, 5] 2와 2를 제외한 1, 3, 4, 5를 번갈아 나온다.
• 수포자3이 문제를 찍는 패턴 [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] : 33, 11, 22, 44, 55 → 3, 1, 2, 4, 5 의 순서로 각 2회씩

코드

answers = [1, 2, 3, 4, 5]

def solution(answers):
    answer = []
    scores = [0, 0, 0]
    patterns = [[1, 2, 3, 4, 5],
                [2, 1, 2, 3, 2, 4, 2, 5],
                [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]]

    for idx, elem in enumerate(answers):
        if elem == patterns[0][idx % 5]:
            scores[0] += 1
        if elem == patterns[1][idx % 8]:
            scores[1] += 1
        if elem == patterns[2][idx % 10]:
            scores[2] += 1
    print(scores)

    for idx in range(len(scores)):
        if scores[idx] == max(scores):
            answer.append(idx + 1)
    return answer

if __name__ == "__main__":
    print(solution(answers))

002 소수 찾기

문제설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

문제해석

• 소수를 판별하는 함수
• 주어진 문자열로 만들 수 있는 숫자 조합

코드

numbers1 = "17"
numbers2 = "011"

from math import sqrt
from itertools import permutations

def is_prime(number):
    if number < 2:
        return 0
    elif number == 2 or number == 3:
        return 1
    else:
        i = 2
        root = sqrt(number)
        while i <= root:
            if number % i == 0:
                return 0
            i += 1
        return 1

def solution(numbers):
    answer = 0
    lst = []
    for i in range(1, len(numbers) + 1):
        for item in permutations(numbers, i):
            lst.append(int("".join(item)))

    for item in set(lst):
        if is_prime(item):
            answer += 1
    return answer

if __name__ == "__main__":
    print(solution(numbers1))

다른 사람의 풀이

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

003 카펫

문제설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

문제해석

• 갈색 격자는 무조건 한줄로만 이루어 진다. → 네 꼭지점은 항상 같다. (4개)
• 두 변의 곱은 노란 격자의 갯수 이고, 두 변의 합을 2로 곱한 수는 (전체 갈색 격자 - 4(꼭지점))와 같다.
• 이때, 나온 경우의 수 중에 가로의 길이가 더 큰 가로, 세로의 조합이 return 값이 된다.

1. 주어진 노란격자의 수가 만들어지는 a 곱하기 b의 경우를 찾는 프로세스가 필요하다. → 인수분해 또는 소인수분해 알고리즘
2. 가능한 a, b 조합 중, 노란 격자의 수(a * b) == 2 * (a + b) 를 만족하는 조합을 찾는다.
   • 노란 격자가 소수인 경우에는 (노란격자 수 + 1) * 2 == 2 * (a + b)
   • 노란 격자가 1인 경우에는 4 == 2(a+b)

코드

# brown, yellow = 10, 2 # return [4, 3]
# brown, yellow = 8, 1 # return [3, 3]
brown, yellow = 24, 24 # return [8, 6]

from math import sqrt

def is_prime(number):
    if number < 2:
        return 0
    elif number == 2 or number == 3:
        return 1
    else:
        i = 2
        root = sqrt(number)
        while i <= root:
            if number % i == 0:
                return 0
            i += 1
        return 1

def solution(brown, yellow):
    factorizations = []
    root = int(sqrt(yellow))
    isprime = is_prime(yellow)
    for i in range(yellow + 1, 1, -1):
        for j in range(1, root + 1):
            if i * j == yellow:
                factorizations.append([i, j])
    # print(factorizations)

    if yellow == 1:
        return [3, 3]
    for a, b in factorizations:
        print(a, b)
        if isprime:
            if (yellow + 1) * 2 == 2 * (a + b):
                return [a + 2, b + 2]
        else:
            if yellow - 4 == 2 * (a + b):
                return [a + 2, b + 2]

if __name__ == "__main__":
    print(solution(brown, yellow))

• 문제에 주어진 케이스 3가지에 대해서는 통과하지만, 채점시에는 절반 이상의 테스트케이스에서 통과하지 못했다.
• 고려하지 못한 테스트케이스를 아우르는 코드로 수정해야할 필요성이 있다.

수정된 코드1

from math import sqrt

def is_prime(number):
    if number < 2:
        return 0
    elif number == 2 or number == 3:
        return 1
    else:
        i = 2
        root = sqrt(number)
        while i <= root:
            if number % i == 0:
                return 0
            i += 1
        return 1

def solution(brown, yellow):
    factorizations = []
    root = int(sqrt(yellow))
    prime = is_prime(yellow)

    for i in range(yellow + 1, root - 1, -1):
        for j in range(1, root + 1):
            if i * j == yellow:
                factorizations.append([i, j])
    print(factorizations)

    if yellow == 1:
        return [3, 3]
    for a, b in factorizations:
        print(a, b)
        if prime and (yellow + 1) * 2 == (a + b) * 2:
                return [a + 2, b + 2]
        elif (a + b) * 2 + 4 == brown:
                return [a + 2, b + 2]

• 케이스 몇가지에서 시간 초과 발생

수정된 코드2 (진행 중)

def solution(brown, yellow):
    factorizations = dict()
    root = int(sqrt(yellow))
    prime = is_prime(yellow)

    if yellow == 1:
        return [3, 3]

    for f in range(2, root + 1):
        count = 0
        if is_prime(f):
            while (yellow % f) == 0:
                count += 1
                yellow /= f
            if count:
                factorizations.setdefault(f, count)
    print(factorizations)

    for key in factorizations:
        print(key)

• 인수분해를 소인수분해로 만들어서 분류하는 시도