프로그래머스 알고리즘 고득점 Kit - [Lv.2] 카펫 (Java)

문제 출처 - 링크

알고리즘 분류

• 완전탐색

📋 문제 요약 설명

• 주어진 카펫의 노란색과 갈색의 격자 수를 이용해서 카펫의 가로, 세로 크기를 구해 순서대로 배열에 담아 return 해라

💡 알고리즘 설계 / 접근 방법

1. 갈색 격자 수에서 4를 빼고, 그 값을 반으로 나누면 노란색 격자의 가로, 세로 길이를 더한 값이 나온다.
   • 4를 빼는 이유는 카펫의 네 모서리 길이를 뺀 것이다.
2. 완전탐색을 통해 노란 카펫의 가로, 세로 길이를 구한다.
3. 가로, 세로 길이에 1번에서 뺀 네 모서리의 값을 반으로 나눈 2를 각각 더해서 값을 반환한다.

✅ 풀이

시간 복잡도 → O(N)

1. 반복문 : O(brown)
   • 최대 (yellowSize / 2)까지 반복
   • yellowSize = (brown - 4) / 2 → (yellowSize / 2) = (brown - 4) / 4 → O(brown)

최종 시간 복잡도 :

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {};
        int yellowSize = (brown - 4) / 2; // 노란 카펫의 가로 + 세로 길이
        
        // 노란 카펫의 크기 구하기
        for (int i = 1; i <= (yellowSize / 2); i++) {
            // i = 노란 카펫의 세로 길이, yellowSize - i = 노란 카펫의 가로 길이
            if (i * (yellowSize - i) == yellow) {
                // 2를 더하는 이유는 카펫의 네 모서리 값을 더한것임
                answer = new int[] {yellowSize - i + 2, i + 2};
                break;
            }
        }        
        
        return answer;
    }
}