문제

Programmers, 카펫

핵심

• 입력의 크기가 $5000, 2'000'000$이라 대략 $O(n)$ 이하의 알고리즘을 사용한다.
• 아래와 같은 카펫이 주어졌을 때, 갈색 타일과 노란 타일 개수로 전체 카펫의 가로와 세로 길이를 구해야 한다.
• 해당 문제는 규칙을 찾아 2차 연립 방정식을 이용하면 시간복잡도를 확 낮출 수 있다. 예를 들어 갈색 타일과 노란색 타일 개수가 10, 2로 주어졌다고 하자. 전체 타일 개수가 12개라면 가능한 가로와 세로 조합은 공약수로 12 1, 6 2, 4 * 3이 가능하다. 전체 타일 중 노란색 타일의 개수는 갈색 타일에 1줄씩 둘러싸여 있으므로 가로와 세로 2씩 차감하면 구할 수 있다.
• 다음 연립방정식을 풀면 가로와 세로를 알 수 있다.
  $x + y = 12; \\ (x - 2) * (y - 2) = 2;$
  

개선

코드

시간복잡도

• $O(N)$

C++

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int sum = brown + yellow;
    for (int i = 1; i <= sum; ++i) {
        if (sum % i != 0)
            continue;
        int j = sum / i;
        int ySum = (i - 2) * (j - 2); 
        if (ySum == yellow) {
            answer.push_back(j);
            answer.push_back(i);
            break;
        }
    }
    return answer;
}

Java

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {0, 0};
        int sum = brown + yellow;
        for (int i = 1; i <= sum; ++i) {
            if (sum % i != 0)
                continue;
            int j = sum / i;
            int ySum = (i - 2) * (j - 2);
            if (ySum == yellow) {
                answer[0] = j;
                answer[1] = i;
                break;
            }
        }
        return answer;
    }
}