[프로그래머스]LV. 2 - 카펫(Python)

[프로그래머스] LV. 2 - 카펫(Python)

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

문제 설명

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

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

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

제한 조건

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

입출력 예

풀이과정

1. 문제를 보고 모든 경우의 수를 따져봐야 하는 완전탐색 문제인 것을 파악했다.
2. brown 카펫은 반드시 yellow를 감싸고 있는 형태이다. 문제와 주어진 그림을 반복해서 보며 생각하니 규칙을 알 수 있었다.

• 전체 카펫의 모서리를 제외하면 카펫은 십자 모양이 된다. 전체 카펫이 십자 모양일 때 brown 카펫의 가로 길이와 yellow 카펫의 가로 길이가 같고, 세로 길이 또한 같은 것을 확인할 수 있었다.
• 테스트 케이스 3번의 경우를 그림판에 직접 그려보았는데, 이 때 전체 카펫이 십자 모양일 때 brown 카펫의 가로와 세로를 곱한 값은 yellow 카펫의 개수라는 것을 알게 되었다.

4. 반복문과 조건문을 통해 경우의 수를 탐색하는 방법으로 코드를 작성했다.

• 편의를 위해 brown 카펫의 개수에서 모서리를 제외하고 반으로 나눴을 때의 몫을 k라는 변수에 초기화 시켜주었다.
• for문의 range() 함수를 사용해 i에 1부터 k-1까지의 정수값을 받아주고 이를 수식에 활용했다.
• 카펫의 가로 길이는 세로 길이보다 길거나 같다는 제한 조건이 있다.
  이 경우와 brown 카펫의 가로*세로가 yellow 카펫의 개수와 같은 경우를 한번에 확인하기위해 논리 연산자를 사용했다.

5. 위의 조건에 해당하는 값이 있을 때, 처음에 제외한 모서리 카펫 개수를 더한 값을 리턴시켜주었다.

코드

def solution(brown, yellow):
    k = (brown-4)//2
    for i in range(1, k):
        if i*(k-i) == yellow and i >= (k-i):
            return [i+2, (k-i)+2]

후기

처음에 문제를 이해하기 어려웠다.
하지만 주어진 테스트 케이스를 그림판에 직접 그려보니 규칙을 찾을 수 있었고 방향이 잡히기 시작했다.
이 과정이 없었다면 문제를 해결하는 데 많은 어려움을 겪었을 것이다.
문제를 풀고 나서 나의 풀이보다 더 좋은 풀이가 분명 있을 것이라 생각하고 다른 사람의 풀이를 보았다. 나는 반복문과 조건문을 사용해 문제를 해결했지만 그렇지 않은 사람들도 많았다.
2차 방정식을 활용해 문제를 해결한 사람들의 풀이가 많았는데, 이렇게 수학적 접근을 통해 문제를 해결할 수 있구나 라는 생각이 들었다.
다른 사람들의 풀이를 보며 시간복잡도의 중요성 등 많은 것을 배울 수 있었다.