Today's Algorithm(2019-01-13)

programmers. 카펫

처음에 문제를 읽었을 때는 똑같은 격자 문양 패턴이 여러번 나타날 수도 있을 것이라 생각하고 다양한 경우의 수를 고려해야겠다는 생각이 들었습니다. 하지만 입출력 예를 보면서 격자 문양 패턴이 1개가 있고 그 안의 red의 모양만 바뀐다고 생각했을 때 고려해야 하는 경우의 수는 확 줄었습니다.

 

일단 red의 width와 height가 결정이 되었다고 한다면 brown의 개수는 red의 width와 height를 이용하면 (width * 2 + (height + 2) * 2) 라는 사실은 충분히 납득할 수 있을거라 생각합니다. 그렇다면 red의 width와 height만 구한다면 문제를 거의 다 푼 것인데요. 그건 문제의 조건에서 가로가 세로보다 크거나 같거라는 것을 고려했을 때 그 조건안에서 계속 반복문을 돌리면서(while(width >= height)) 찾으면 됩니다. 반복문 조건은 여러 방식이 있겠지만 저의 경우 width를 red와 같은 값으로 설정해두고 width를 -1하면서 red % width == 0 을 조건 안에서 height를 구할 수 있었습니다.

class Solution {
    public int[] solution(int brown, int red) {
        int width = red;
        int height = 0;
        while(width >= height) {
            height = red / width;
            if(red % width == 0) {
                int temp = width * 2 + (height + 2) * 2;
                if(temp == brown) break;
            }
            width--;
        }
        return new int[]{width + 2, height + 2};
    }
}

 

다만 처음에 while문의 조건으로 while(red <= width * width) 로 썼었습니다. 그 이유는 사실 height = red / width 다 보니 height를 줄이면 저렇게 사용할 수 있거든요. 그런데 이것은 문제 조건에서 red가 1이상 2,000,000라는 점에서 int범위로 초과할 수 있어 실패가 발생한 것 같아 수정하였습니다.