[완전탐색] 프로그래머스 - 소수찾기

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42842#

 

문제 설명 :

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

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

제한사항

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

입출력 예

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

 

문제 풀이:

가장 처음 생각난 풀이는 다음과 같다.

import math

def solution(brown, yellow):
    answer = []
    mul = brown + yellow
    root = int(math.sqrt(mul))
    for i in range(root, brown+1):
        for j in range(i+1):
            if i * j == mul and (i-2)*(j-2)==yellow:
                answer.append(max(i, j))
                answer.append(min(i, j))
                break
        if len(answer) != 0:
            break
    return answer

brown + yellow 값이 가로*세로의 값과 동일하니까 범위 내에서 가로*세로 = brown + yellow 인 값을 찾자는 것이다. 범위는 큰 값의 범위를 설정해줬다. 따라서 사각형이 정사각형일 때의 가로 길이 ~ yellow가 존재하지 않고 하나의 열로 이루어진 brown일 경우(brown+1)일 때까지의 범위이다. 

 

처음에는 if i * j == mul 까지만 조건을 설정해줬는데, 이렇게 하니까 테스트 4번, 6번, 7번을 통과하지 못했다. 결국 벗어난 테스트 케이스를 찾지는 못했으나, 다른 분들로부터 힌트를 얻어서 yellow 값에도 맞는 수를 찾아야 한다는 점을 파악했다. 생각해보니 brown + yellow = 104인 경우에도 52 * 2, 26 * 4, 13 * 8의 세가지 경우가 나오는데 나는 단순히 두 수의 차가 가장 적은 13 * 8의 경우만 찾고 있었다. 쉬운 테스트 케이스였는데도 확신에 차서 생각을 못하고 있었다.

 

이 외에도 다른 방정식을 이용해서 푸는 방법도 존재한다. 처음에 brown과 yellow 각각을 가로와 세로에 대한 방정식으로 정리해보다가 이걸로 좀 더 쉽게 풀지 않았을까 싶던 방법이다. 

import math

# brown = (가로 + 세로) * 2 -2 
# yellow = (가로 - 2) * (세로 - 2)
def solution(brown, yellow):
    answer = []
    mul = brown + yellow
    root = int(math.sqrt(mul))
    for i in range(root, brown+1):
        for j in range(i+1):
            if (i+j-2)*2 == brown and (i-2)*(j-2)==yellow:
                answer.append(max(i, j))
                answer.append(min(i, j))
                break
        if len(answer) != 0:
            break
    return answer