[프로그래머스] (Swift) 카펫 - Lv.2

코딩테스트 연습 - 카펫 | 프로그래머스 스쿨

 

머리말

카테고리에 적혀 있는 풀이 힌트

원래 알고리즘을 풀 때 최대한 해당 문제의 주제를 알지 않으려고 한다. 이미 그 알고리즘 방식을 알고 풀면 실제 시험 상황처럼 당황하지 않기 때문이다. 하지만, 사이트에서 이미 완전 탐색임을 알려 주는 바람에 큰 힌트를 얻었다.

풀이

1. 카펫의 면적은 갈색 격자의 수와 노란색 격자 수의 총합과 같다.
2. 카펫의 상하좌우의 끝이 모두 한 줄이기 때문에 가로와 세로의 길이를 각각 2를 빼서 서로 곱하면 그것이 노란색 격자의 수와 같다.

/*
area = brown + yellow = row * col
yellow = (row - 2) * (col - 2)

OOOO
OXXO
OOOO

OOO
OXO
OOO

OOOOOOOO
OXXXXXXO
OXXXXXXO
OXXXXXXO
OXXXXXXO
OOOOOOOO
*/

 

코드

• 면적에 대한 약수를 구하기 위해 반복문의 최대 범위를 면적의 제곱근(소수점 버림)으로 정했다.
• 약수를 나눠서 그 약수를 면적에서 나눈 것을 "상대 약수"라고 정의했다.
• [상대 약수, 약수]를 담는 이차원 배열을 구해서, 두 약수를 각각 2를 빼서 서로 곱하면 노란색 격자의 수가 같은 것을 찾도록 했다.

import Foundation

func solution(_ brown:Int, _ yellow:Int) -> [Int] {
    // 카펫의 면적은 갈색과 노란색 격자의 총합
    let area = brown + yellow
    
    // 면적의 약수에 대한 경우의 수를 만들 배열 초기화
    var divisors = [[Int]]()
    
    // 반환할 배열 초기화
    var result = [Int]()
    
    // 면적의 제곱근에 소수점을 버려 반복문을 돌릴 범위를 할당
    let range = Int(Double(area).squareRoot())
    
    // 위의 범위를 돌면서
    // 약수와 면적과 약수를 나눈 값(상대 약수)을 배열로 저장
    for divisor in 2...range {
        if area % divisor == 0 {
            let opponent = area / divisor
            divisors.append([opponent, divisor])
        }
    }
    
    // 약수의 배열을 돌면서
    // 약수와 상대 약수를 곱한 것이, 노란색 격자의 수가 같으면
    // 해당 배열의 요소를 결괏값으로 할당
    for i in 0..<divisors.count {
        let yellowRow = divisors[i][0] - 2
        let yellowCol = divisors[i][1] - 2
        
        if yellow % yellowRow == 0 && yellow % yellowCol == 0 {
            if yellowRow * yellowCol == yellow {
                result = divisors[i]
            }
        }
    }
    
    // 결괏값 반환
    return result
}