완전탐색 > 카펫

아래 문제는 프로그래머스에서 제공하는 코딩테스트 >  완전탐색 > 카펫 (고득점 Kit)의 문제입니다🧑🏻‍💻

 

문제 제시

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

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

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

제한사항

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

입출력 예

10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

문제 해결

import Foundation

func solution(_ brown:Int, _ yellow:Int) -> [Int] {
    let width = Int(sqrt(Double(yellow)))
    
    for i in width...yellow {
        for height in 1...width {
            if yellow == i * height {
                if brown == ((i + 2) * 2) + (height * 2) {
                    return [i + 2, height + 2]
                }
            }
        }
    }
    return []
}

사용된 개념

 - 반복/조건문

 - 제곱근

 

문제 뒷담화

이번 문제는 크게 복잡한 부분은 없었다. 다만 코드가 중첩된 조건 반복문으로 깔끔하지 못하고 뎁스가 길어져서 문제지만..

우선 갈색 타일이 노란 타일을 한라인만 둘러쌓게 됨으로 가로의 길이는 무조건 노란 타일보다 2만큼 크고 세로의 길이는 노란 타일의 세로와 동일하다고 생각하였다. 그래서 노란타일로 접근을 먼저했다.

우선 노란타일의 입력값에서 직사각형이니 여러가지로 약수가 나올 수 있다. 우선 중간값을 찾기위해 제곱근 함수를 사용하였다. 더블타입으로 만들어 소수점이 있을수 있다고 생각했다. 그리고 다시 정수로 변환해주어 가로를 구했다. 가로는 세로보다 무조건 크다 했으니까 가로를 기준으로 반복문을 돌렸다.

가로 길이부터 전체 타일수까지 반복문을 돌리며 그 안에서 세로 길이에 대해서 가로길이를 넘지 않을테니 1부터 가로길이까지 반복문을 돌렸다. 이제 조건문으로 가로와 세로를 곱해 타일수와 같아지는 조건을 찾았다. 또 중복된 조건문으로 갈색타일의 갯수를 노란 타일의 가로 세로 길이로 도출하여 값을 비교한뒤 맞아 떨어지면 해당 가로/세로 배열을 리턴하도록 하였다.

 

 

[참고자료]

programmers.co.kr/learn/courses/30/lessons/42842#