[프로그래머스/CPP/JS] 카펫

프로그래머스. 카펫

1. 문제

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

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

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

2. 제한사항

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

3. 풀이

• yellow의 가로가 m이고 세로가 n이면 brown의 개수는 2(m+n+2)다. 이와 일치하는 m과 n을 찾고 전체 가로의 길이는 m+2 세로의 길이는 n+2로 구하면 된다.
• yellow의 가로 +1 세로 +1을 해보면서 가로와 세로가 증가할 때 brown의 가로와 세로가 어떻게 바뀌는 지 살펴보고 brown의 개수는 2(m+n+2)라는 결론을 내렸다.
• m과 n의 후보를 찾기 위해 yellow의 약수를 찾는 함수를 만들었다. 약수는 짝이기 때문에 절반만 찾아주고 나머지 쌍은 실제로 계산할 때 처리해주었다.

4. 처음 코드와 달라진 점

• 약수 찾기에서 loop를 0부터 시작해서 0으로 나누는 오류로 발생했다.
• loop 시작을 1로 수정해주었다.
• 근데 loop 범위를 n/2까지로 하니까 1이 그냥 통과하더라
• 그래서 1은 모든 수 의 약수라서 loop 시작 전에 1은 미리 넣고 loop 시작을 2부터 범위를 n/2까지로 했다.
• 근데 테스트 케이스 한 개를 통과 못 하길래 n/2를 포함하게 바꿨더니 됐다
• 다 풀고 왜 그런가 생각해보니까 4의 경우 n/2를 포함 안 하게 되면 2가 약수로 안 들어간다.

5. 코드

#include <string>
#include <vector>

using namespace std;

vector<int> find_factor(int n){
    vector<int> factors;
    factors.push_back(1);
    
    for(int i=2; i<=n/2; i++){
        if(n % i == 0) factors.push_back(i);
    }
    return factors;
}

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    vector<int> factors = find_factor(yellow);
    
    for(int factor : factors){
        int divided = yellow / factor;
        int result = (factor + divided + 2) *2;
        if(result == brown) {
            answer.push_back(divided+2);
            answer.push_back(factor+2);
            break;
        }
    }
    
    return answer;
}

근데 이 문제 1점밖에 안준다...

➕ 21.09.01 추가

6. 풀이

• brown = 2(m + n -2)
• yellow = (m - 2)(n - 2)
• 1부터 2501까지 모든 경우를 조사했다.
• 2501까지인 이유
  • brown ≤ 5000
  • 2(m + n - 2) ≤ 5000
  • m + n - 2 ≤ 2500
  • m + n ≤ 2502
  • m이 n보다 크다.
  • 그래도 n이 1은 되겠지
• n은 m보다 작거나 같기 때문에 반복을 i와 같거나 같을 때까지만 한다.
• m을 i로 n을 j로 모든 경우를 조사하며 조건에 충족하면 answer 배열에 추가하고 반복을 종료한다.

7. 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    for (int i = 1; i < 2502; ++i) {
        for (int j = 1; j <= i; ++j) {
            bool isBrown = 2 * i + 2 * j == brown + 4;
            bool isYellow = (i - 2) * (j - 2) == yellow;
            if (isBrown && isYellow) {
                answer.push_back(i);
                answer.push_back(j);
                break;
            }
        }
    }
    return answer;
}

8. 코드(JS)

function solution(brown, yellow) {
  const total = brown + yellow;

  for (let height = 1; height < total; height++) {
    const width = total / height;
    if (width !== Math.floor(width)) continue;
    if ((width - 2) * (height - 2) === yellow) return [width, height];
  }
}