프로그래머스 완전탐색 카펫

1. 개요

완전탐색 문제를 풀었다.
시간은 1시간 30분 정도 소요되었고, 예상치 못한 오타때문에 시간이 더 걸렸다.
앞으로는 꼼꼼히 적자.

2. 코드

class Solution {
    fun solution(brown: Int, yellow: Int): IntArray {
        var answer = IntArray(2)
        var width = 0
        var height = 0
        var start = yellow
        
        while(true) {
            if (yellow%start == 0) {
                width = start
                height = yellow/start
                if (width*2 + height*2 + 4 == brown) {
                    answer[0] = width+2
                    answer[1] = height+2
                    break
                }
            }
            start -= 1
        }
        return answer
    }
}

3. 해설

먼저 yellow에 해당하는 곳은 직사각형의 형태를 띤다. 그래서 yellow의 약수들을 큰 순서대로 width에 넣어준다.(가로, 세로 중 가로가 더 크거나 같으므로)
그리고 yellow를 width로 나눈 값을 height로 넣어준 다음, 계산을 해서 맞다면 이 값을 반환한다.

이때 while문에 true를 사용한 것은 이 문제에서 예외가 발생하지 않는 것 같아서 넣었고, 만일 추가적인 조건이 있다면 그 조건을 넣을 것이다.
물론 이런 방식이 맞지는 않을 수 있지만, 프로그래머스에서 돌렸을 때 true로 설정할 때 가장 빨라서 조건을 그냥 true로 설정하였다. 만일 예외가 없다면 굳이 제곱수까지 구해서 조건을 넣을 필요가 없으니까.

4. 시간복잡도

while문에서는 yellow의 모든 약수를 바탕으로 구한다.
따라서 현재 코드 상으로는 최대 시간복잡도는 O(N)이며, 문제의 경우 2,000,000이 된다.

5. 공간복잡도

계속해서 이미 선언된 약수를 바탕으로 구하기 때문에, 공간복잡도는 O(1)이라고 생각한다. while문을 돌면서 추가적으로 자원을 필요로 하지 않기 때문이다.

6. 마무리

사실 처음에는 문제를 잘못 해석했다.
나는 yellow에 해당하는 것이 직사각형 뿐만이 아니라 여러 유형의 다각형도 되는 줄 알았다(권총 모양처럼)
그래서 처음에는 코드는 맞았는데 시간초과로 통과되지 않았고, 이것 때문에 40분은 더 잡아먹힌 것 같다.
다음부턴 문제를 더 잘 이해할 수 있는 내가 되어야겠다.