문제

풀이

public int[] solution(int brown, int yellow) {
    int totalRec = brown + yellow;

    for (int i = 3; i <= Math.sqrt(totalRec); i++) {
        if (totalRec % i != 0) continue;
        if ((i - 2) * (totalRec / i - 2) == yellow) return new int[]{totalRec / i, i};
    }
    return null;
}

전체 타일 개수를 totalRec 이라는 변수로 선언해주고,

totalRec 이 정수의 곱이 되는 i와 totalRec / i 에 대해 yellow 개수가 맞는지를 확인하기 위해 for 문 순회.

i 는 내부에 yellow 라는 사각형도 포함해야 하므로 최소 3부터 시작하도록 해주고, 약수에 대해 확인할 것인데 중복인 경우가 발생하지 않도록 totalRec의 제곱근까지만 확인하면 된다. i 가 나머지 약수보다 작거나 같으므로 세로 길이가 된다.

다른 풀이

public int[] solution(int brown, int red) {
    int a = (brown+4)/2;
    int b = red+2*a-4;
    int[] answer = {(int)(a+Math.sqrt(a*a-4*b))/2,(int)(a-Math.sqrt(a*a-4*b))/2};
    return answer;
}

구해야 하는 값을 x(가로), y(세로) 라고 했을 때

• xy = brown + red
• x + y = (brown + 4) / 2
  • brown 이 둘레의 길이인데 (가로 + 세로) * 2 의 값에서 모서리에 겹치는 4개를 뺀 값이 된다.
• x + y, xy 를 아래의 2차방정식의 근의 합, 근의 곱으로 간주해서 x값(x, y)를 근의 공식으로 풀어낸 풀이.

$$ x^2 + (a + b)x + ab = 0 $$

코드의 간결성에서는 크게 차이는 없지만, 공식을 이용해서 바로 답을 구해내는 방식이라 훨씬 효율적일 것 같다.

나의 풀이 : O(N)

근의 공식 풀이 : O(1)