[코테 공부(Kotlin) - 프로그래머스] 카펫

문제

문제 출처

프로그래머스 : https://programmers.co.kr/learn/courses/30/lessons/42842 https://hsin.hr/coci/archive/2010_2011/contest4_tasks.pdf

문제 설명

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

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]

---

풀이

나의 풀이

사실은 문제 카테고리를 똑바로 안 보고 풀어서 완전 탐색이 아닌
2차 방정식의 일반해를 이용해 문제를 풀었다. (머쓱 ^^;)

풀이는 다음과 같다.

갈색 격자의 수를 b , 노란 격자의 수를 y, 노란 부분의 가로를 x 라고 하면
다음과 같은 관계식이 성립한다.

위의 식을 정리하면 다음과 같은 2차 방정식을 확인할 수 있다.

가로의 길이가 세로의 길이보다 크거나 같다고 했으므로
2차 방정식의 일반해를 이용하면 x의 일반해를 구할 수 있다.

카펫의 가로 세로는 노란 부분의 가로 세로에 2를 더한 값과 같으므로
x+2와 y/x+2를 배열에 담아 출력한다.

이 풀이를 그대로 옮겨 코드를 작성했다.

fun solution(brown: Int, yellow: Int) : IntArray{
    val d = (4 - brown)*(4 - brown) - 16* yellow
    val width = (brown - 4 + sqrt(d.toFloat()).toInt())/4
    val height = yellow/width
    return intArrayOf(width+2,height+2)
}

풀이를 제출하면서 왜 이런 문제가 레벨 2인가 했지만
다른 사람들의 풀이를 보고 완전 탐색을 이용해 푸는 문제란걸 깨달았다 ㅋㅋㅋㅋ
(그치만..이게 더 효율적인걸?)

---

다른 사람의 풀이

대부분의 풀이 방식은 다음과 같았다.

1. 우선 1 부터 yellow 까지의 수 중에서 yellow의 약수를 찾는다.(노란 부분의 가로 또는 세로)
2. 세로 × 2 + 가로 x 2 + 4 = brown을 만족하는 세로 혹은 가로를 찾는다.
3. 만족하는 수 중 가장 큰 수가 가로, 가장 작은 수가 세로가 된다.
4. 가로+2, 세로+2

여러 풀이 중 가장 간단하고 깔끔한 풀이를 약간 수정해 가지고 왔다.

fun solution(brown: Int, yellow: Int) =
    (1..yellow)
        .filter { yellow % it == 0 }
        .first { brown == (yellow / it * 2) + (it * 2) + 4 }
        .let { intArrayOf(yellow / it + 2, it + 2) }

위의 설명 처럼 yellow의 약수 중에서 조건을 만족하는 가장 작은 수(세로)를 찾아
카펫의 가로 세로를 찾는다. 가장 깔끔한 답안이라 그저 감탄

나의 풀이 실행 결과

완전 탐색 실행 결과

수학적 풀이가 루프를 돌지 않아 더 빠르기는 하다.(정신 승리)