카펫 (프로그래머스) [JAVA]

 

문제

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

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

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

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

제한사항

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

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

 

풀이

2차 방정식으로 생각하면 된다.

가로 세로가 a,b일때

brown + yellow = a*b;

yellow = (a-2)*(b-2) 두 식을 a에대해서 풀고, b역시 구하면 된다.

이때 a를 1부터 늘려가면서 식을 풀기 때문에 a가 무조건 b보다 작다.

시간복잡도는 1~ brown+yellow이므로 O(N)이라 할 수 있다.

 

코드

public int[] solution(int brown, int yellow) {
    int[] answer = new int[2];
    int kk = brown + yellow;
    int k = 2+brown/2;
    int a = 0;

    while(true) {
        if((a*a - a*k + kk) == 0) break;
        a++;
    }
    answer[1] = a; answer[0] = kk/a;
    System.out.println(answer[0] + " " + answer[1]);
    return answer;
}

 

결과

 

복기

조금만 더 생각해서 근의 공식에 아예 넣어버려서 풀면 O(1)로 풀 수 있다.

int[] answer = new int[2];
int kk = brown + yellow;
int k = 2+brown/2;
int a = 0;
answer[1] = (int)(k - Math.sqrt((int)(k*k-4*kk)))/2; 
answer[0] = kk/answer[1]; 

하지만 유의미한 시간상의 변화는 적었다. 아마 sqrt계산이 시간이 오래걸려서 그런게 아닌가 생각하고 있다.