99클럽 코테 스터디 4기 21일차 TIL - 프로그래머스: 카펫(42842) Swift & Python

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
프로그래머스	42842	카펫	완전탐색	Lv.2	Swift, Python

🚀 나의 접근 방법

완전탐색으로 카펫의 최소 높이(3)부터 1씩 증가시키면서 yellow 개수가 실제 개수와 일치할 때까지 탐색한다.

yellow는 1이상이므로 카펫의 전체 높이는 3 이상이다. 그래서 초기 height를 3으로 정의한다.
카펫의 width는 (brown + yellow)/height로 계산할 수 있다.

반복문을 돌면서 yellow 개수를 구하고((width-2) * (height-2)) 일치하다면 반복문 종료, 아니면 높이를 1 증가시키고 width를 다시 계산한다.

이 과정을 반복하면 답을 구할 수 있다. 즉, 카펫의 최소 높이부터 격자의 개수를 계산하며 탐색하는 것이다.

✍️ 나의 코드

Swift

import Foundation

func solution(_ brown:Int, _ yellow:Int) -> [Int] {
    var height = 3
    var width =  (brown + yellow)/height
    while true {
        if (width-2) * (height-2) == yellow { break }
        height += 1
        width = (brown + yellow)/height
    }
    return [width, height]
}

Python

def solution(brown, yellow):
    height = 3
    width = (brown+yellow)/height
    while True:
        if (width-2) * (height-2) == yellow: break
        height += 1
        width = (brown+yellow)/height
    
    return [width, height]

🤔 회고

첫 시도의 반례

처음에는 아래와 같이 풀이했다. 기본 테스트 케이스는 통과했지만 제출 채점은 통과할 수 없었다.

def solution(brown, yellow):
    yellowX = yellow
    yellowY = 1
    while yellowX >= yellowY:
        if yellowX*2 + yellowY*2 + 4 == brown:
            break
        else:
            yellowX /= 2
            yellowY *= 2
    
    return [yellowX+2, yellowY+2]

이것에 대한 반례로 Parameters(brown: 24, yellow: 25), Return([7, 7])가 있다.
즉, 위의 코드는 높이가 짝수인 경우만 탐색하므로 답을 찾을 수 없다.

반례를 찾고 생각하며 문제를 해결해 보자.