[프로그래머스] 카펫

문제 분석

카펫

요약 | 위 그림처럼 노란 타일을 갈색 타일이 둘러싸는 구조일때, 노란 타일의 개수와 갈색 타일의 개수를 받아 전체 카펫의 크기를 구하여라.

Input data :

• brown: Int
  • 8 ≤ brwon ≤ 5,000
• yellow: Int
  • 1 ≤ yellow ≤ 2,000,000
• 카펫의 가로 길이 >= 세로 길이

• yellow의 길이가 brown보다 길 수 있다. brown은 테두리 타일이기 때문에 카펫의 크기가 커지면 안에 들어가는 yellow 타일의 개수가 더 많아질 수도 있다.
• yellow의 길이가 최대 200만이므로 혹시라도 yellow와 brown을 서로 곱한다거나.. 아니면 이중 for문으로 각 타일을 순회한다거나 하는 식의 풀이는 지양해본다.

Output data :

IntArray

풀이

전개 순서

1. (첫 번째 for문) 1부터 yello까지 순회하면서 약수를 찾아 저장(list)해둔다.
2. (두 번째 for문) 0부터 list 길이의 절반까지 반복하면서 list의 0번째-마지막, 1번째-마지막의 앞, 2번째-마지막의 앞앞 ... 의 요소들을 가져와 계산하여 brown과 동일한지 확인한다.
   • 계산 : 첫 번째 항에 대해서는 +2 한 후 곱하기 2를 한 값과, 두 번째 항에 대해서는 곱하기 2한 값을 더한다.

계산식을 저렇게 한 이유는 그림을 그려보면 간단히 이해할 수 있다. brown=24, yellow=24 라는 값이 들어온다고 가정해보자.

4-6 쌍일 때, 즉 yellow 타일의 크기가 세로 4, 가로 6일 때 yellow를 둘러싸는 brown 타일의 크기와 맞아 떨어지게된다.

이렇게되면 yellow의 크기가 확보되는 것이므로, brown의 개수는 yellow를 둘러싸고 있는 크기만큼을 계산해주면 된다.

brown 세로 개수 : yellow 세로 크기에 2를 더하고, 그 값에 2를 곱한다. 이때 2를 더하는 이유는 모서리 타일 때문이다.
brown 가로 개수 : 이미 모서리 타일은 위에서 계산이 되었기 때문에 yellow 가로 크기에 2를 곱한다.

사용한 data type

MutableList
yellow의 약수를 저장할 때 보다 쉽게 데이터를 추가할 수 있다.
인덱스로 바로 접근하여 데이터를 쉽게 찾을 수 있다.
데이터 삭제, 정렬, 중간에 끼워넣기를 하지 않을 것이므로 사용하는 데에 적합하다는 생각이 들었다.

코드

class Solution {
    fun solution(brown: Int, yellow: Int): IntArray {
        var answer = intArrayOf()        
        var list = mutableListOf<Int>()
        for (i in 1 .. yellow) {
            if ( yellow % i == 0 ) {
                list.add(i)
            }
        }                
        var last = list.size - 1
        for (i in 0 until (list.size/2)+1) {
            if ((list[i] + 2) * 2 + list[last] * 2 == brown) {
                answer += list[last] + 2
                answer += list[i] + 2
                break
            }
            last--
        }        
        return answer
    }
}

---

[TIL-240402]