[programmers] 카펫, 소수 찾기

💡 오늘의 학습 키워드

📌  구현

📌  순열
📌  소수 판별 식 

 

🥈 카펫

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42842

 

문제 설명

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

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만,
전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때
카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

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

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

테두리를 1줄로 고정된 조건의 brown 값을 어떻게 활용할 지 생각해야 합니다. 문제 해결 과정은 다음과 같습니다.

1. yellow 값을 순회합니다.
2. yellow 의 약수를 판별하는 조건문으로 yellow 값의 행x열 경우의 수를 구해줍니다.
3. yellow 행x열 값이 brown 총 길이와 일치하는 경우 전체 카펫의 행x열을 리턴합니다.

 

yellow의 약수에서 brown의 둘레와 비교하여 올바른 경우의 수를 구한 후 전체 카펫의 값을 구하는 방법입니다.

 

💡 내가 해결한 방식은?

약수와 둘레 비교를 통한 풀이

def solution(brown, yellow):
    # 테두리 1줄 - 갈색
    # 중앙 - 노랑
    
    # 약수 안에서 최적의 yellow의 둘레 구하기
    # a x b = yello 가 되는 a, b의 값 구하기
    for i in range(1, yellow+1):
        # 노랑에 현재 노랑의 약수 나눈 값이 0일 경우
        if yellow % i == 0:
            j = yellow / i
        else: 
            continue
        
        s_val = (i*2) + (j*2) + 4
        
        if int(s_val) == brown:
            return [j+2, i+2]
    
    return 0

이분 탐색을 통한 풀이

# x * y = brown + yellow
# x + y = (brown + 4)//2

# x + y 에서 x, y를 정한다. 이때 x와 y의 차가 작을 수록 그 곱은 더 커진다.
# 이를 이용해서 이분 탐색으로 그 차의 크기를 조절해서 답을 구한다.

# x <= y 라고 하면, x는 1 ~ (x+y)//2 의 값을 가진다.
def solution(brown, yellow):
    m = brown + yellow
    s = (brown + 4) // 2

    # x가 가질 수 있는 최대값
    diff = (s // 2)

    # x가 가질 수 있는 최대값의 절반
    x = diff // 2
    y = s - x
    diff //= 2

    while x * y != m:
        if diff != 1:
            diff //= 2

        if x * y > m:
            x -= diff
            y += diff

        else:
            x += diff
            y -= diff

    return [y, x]

둘레 값을 이용한 풀이

def solution(brown, red):
    for i in range(1, int(red**(1/2))+1):
        if red % i == 0:
            if 2*(i + red//i) == brown-4:
                return [red//i+2, i+2]

 

---

🥈 소수 찾기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42839

 

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다.
흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때,
종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

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

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

주어진 숫자를 문제에서 원하는 값들로 정제하는데 python을 능숙하게 다룰 줄 알아야 하는 문제였습니다.
문제 해결 과정은 기본적으로 다음과 같습니다.

1. 가공된 모든 정수를 저장할 변수는 set 객체로 초기화합니다.
2. first loop은 숫자 리스트 길이 만큼 순회합니다.
3. first loop에서 정한 글자 수에 맞춰 모든 순열의 경우를 저장합니다.
4. 튜플 형태를 리턴하므로 second loop에서 join으로 해당 순열의 경우의 수를 합치고 정수로 변환합니다.
5. 변환된 숫자를 set 객체에 add 해줍니다.
6. set 객체에 가공할 수 있는 모든 정수가 저장되었다면 해당 리스트에서 소수를 찾아줍니다.
7. 소수 판별 후 구한 소수의 개수를 리턴 해줍니다.

 

이 과정에서 데이터 가공 과정에서 유의해야 할 점은 다음과 같습니다.

매개변수로 들어오는 numbers 값은 숫자 형태이지만 string 타입으로 들어오는데, 
len(numbers)를 하게 되면 만일 17이라는 값이 들어온다면 해당 값의 길이는 1이 아니라 2라는 것을 유의해야 합니다.

 

permutation 메소드는 순열을 구하여 튜플로 리턴해 주므로 다음과 같은 별도 가공 과정이 동반됩니다.
만약 17이라는 값을 2개를 뽑게 될 때 ('1', '7'), ('7', '1') 이런 형식으로 리턴을 해주게 됩니다.
따라서 join 메소드로 해당 값들을 합쳐주고 int를 씌워주어 정수로 변환해주어야 합니다.

 

소수 판별식을 구현할 때 다음의 특징은 기억하는게 좋습니다.

어떤 숫자 n이 소수가 아니라면, 두 개의 자연수 a와 b의 곱으로 표현할 수 있습니다 (n = a * b).
여기서 a와 b 중 하나는 반드시 √n 이하입니다. 그 이유는, 만약 a와 b가 모두 √n보다 크다면, a * b는 n보다 커지기 때문입니다.
이를 활용한다면 3부터 √n까지만 순회하여 소수를 판별하도록 반복문을 최소화 할 수 있습니다.

 

그리고 먼저 1 이하와 2일 경우, 그리고 짝수일 경우로 나누어 소수를 판별하도록 세팅하게 되면,
이후 값은 3부터 √n까지 홀수만 확인하여 반복 횟수를 줄이는데 도움을 주게 됩니다.

 

 

💡 내가 해결한 방식은?

순열을 사용한 풀이

from collections import permutations

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

def solution(numbers):
    # 가공된 모든 정수를 저장할 변수는 set 객체로 초기화합니다.
    possible_numbers = set()

    # 숫자 리스트의 길이만큼 순회합니다.
    for length in range(1, len(numbers) + 1):
        # 순열이 a, b와 b, a가 다르다는 점을 이용합니다. 
        # first Loop에서 정한 글자 수에  맞춰 모든 순열의 경우를 저장합니다.   
        for perm  in permutations(numbers, length):
            # 튜플 형태를 리턴하므로 join을 통해 합치고, 숫자로 변환해야 합니다.
            num = int(''.join(perm))
            # 변환된 숫자를 set 객체에 add 합니다.
            possible_numbers.add(num)

    # 소수 판별 후 소수 값 개수를 리턴합니다.
    prime_cnt = 0
    for p_num in possible_numbers:
        if is_prime(p_num):
            prime_cnt += 1
    
    return prime_cnt

set 과 에라토스테네스 체를 활용한 풀이

from itertools import permutations

def solution(n):
    a = set()
    for i in range(len(n)):
    	# |= 연산은 합집합을 의미합니다.
        # 'a'가 주어진 숫자 조각으로 만들 수 있는 모든 가능한 숫자의 집합이 됩니다.
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    # 소수가 아닌 숫자 제거
    a -= set(range(0, 2))
    # 에라토스 테네스 체와 유사한 방식으로 소수 판별
    # int(max(a) ** 0.5) 는 최대 숫자의 제곱근까지 반복합니다.
    # set(range(i * 2, max(a) + 1, i)) 는 'i'의 배수들을 생성하여 'a'에서 제거합니다.
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

 

---

✍️  TIL

문제를 풀고나서 다른 사람의 풀이를 구경하는 재미가 있는 것 같다.
내가 생각하지 못한 방향으로 접근해 풀어나가는 게 참 신기하고 물론 이해하지 못할 때도 많지만
보는 것 자체로 한 층 더 두터워 지는 기분이 든다.
평소 나도 자주 사용하는 전혀 다른 방식으로 사용한다던가, 내가 생각하지도 못했던 자료구조를 통해
풀이를 성공시키는 게 참 한번 씩은 벽이 느껴지기도 하고 나도 저렇게 풀 수 있을까 걱정도 되는데,
그럼에도 나 또한 저렇게 한 계단 더 오르는 날이 올 거라고 믿는다.