완전탐색 - 카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

문제에서 갈색 격자는 노란색 격자들 바깥으로 한 줄만 있기 때문에, 노란색 격자의 개수가 중요 포인트라고 생각했다. 

input으로 갈색 격자 개수와, 노란색 격자 개수를 받기 때문에 직사각형의 둘레를 이용해서 문제를 풀 수 있겠다고 생각했다. 

 

1. 우선 노란색 격자 개수를 통해 만들 수 있는 직사각형의 모든 경우를 구한다.

2. 그 모든 노란색 직사각형의 경우들이 input으로 주어진 갈색 격자의 개수와 잘 맞아 떨어지는지 확인한다. 

 

1번에서 모든 노란색 직사각형의 경우는, input으로 받은 노란색 격조의 개수의 약수들을 구하는 로직을 활용해서 찾아낼 수 있다. 

예를 들어 노란색 격자들이 24개가 있다고 하면, 가로 세로 길이가 (1, 24), (2, 12), (3, 8), (4, 6) 인 경우들이 있다. 

 

그리고 2번을 확인하기 위해 갈색 격자들의 개수를 이용하는데, 그림을 보면 갈색 격자들의 개수는

노란색 부분을 둘러싼 부분 + 각 모서리 4개 이다. 

노란색 부분을 둘러싼 부분의 개수는 노란색 직사각형의 둘레 길이를 통해 구할 수 있다. 

 

그렇기 때문에 모든 노란색 직사각형의 경우들의 둘레가 brown-4와 값이 같은 경우가 정답이 된다. 

 

아래는 작성한 답안 코드이다. 

def get_yellow_cases(num):
    m = int(num ** 0.5)
    result = []
    for i in range(1, m+1):
        if num % i == 0:
            result.append((i, num//i))
    return result

def solution(brown, yellow):
    answer = []
    brown_without_corner = brown - 4
    yellow_cases = get_yellow_cases(yellow)
    print(yellow_cases)
    for case in yellow_cases:
        if (case[0] + case[1]) * 2 == brown_without_corner:
            answer.append(case[0] + 2)
            answer.append(case[1] + 2)

    answer.sort(reverse=True)
    return answer

제한사항에서 카펫의 가로길이는 세로보다 같거나 길다고 했기 때문에 answer를 내림차순으로 정렬을 한번 해주었다. 

 

처음에는 get_yellow_cases에서 약수들을 모두 구하는 로직을 그대로 썼다. 

def get_yellow_cases(num):
    m = int(num ** 0.5)
    result = []
    for i in range(1, m+1):
        if num % i == 0:
            result.append((i, num//i))
         	if i != num // i:
                result.append((i, i))
    return result

이전에 약수의 합을 구하는 코드에 대해 포스팅한 적이 있는데, 그걸 그대로 썼더니 get_yellow_cases 함수에서 필요하지 않은 부적합한 결과들이 나왔다. 

어차피 그 부적합한 결과들은 solution 함수 안에서 걸러지기 때문에 최종적으로 틀린 답을 내지는 않아서 정답코드로 제출은 됬는데, 

그렇게 되면 불필요한 자원을 쓰게 된다. 

 

이렇게 블로그에 글을 남기면서 코드는 수정해서 다시 제출했다. 

전에 사용했던 로직을 갖다 쓰는건 좋지만, 상황에 따라 잘 생각해보고 적절하게 수정해서 써야겠다고 생각했다.