프로그래머스<카펫>

문제 설명

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]

 

위 카펫문제는 완전탐색 카테고리의 문제라고 나와있다. 재귀법이나, 순열, DFS등의 방법들을 여러가지를 생각해보았지만, 효율적으로 풀 수 있는 방법을 생각해내지 못하였다.

고민을 하던 중, 반복/조건문을 통한 Brute Force 기법을 통해 가능한 경우를 구하는게 최선이라는 방법이 들었다. 

 

문제 접근을 위해 필요한 정보들에 대해 먼저 생각해보았다.

1. 노란색 개수의 약수를 구해야한다

2. 노란색 개수가 어떻게 분포할 수 있는지 가로의 길이와 세로의 길이 경우의 수를 구해야 한다

3.노란색 개수와 갈색 개수의 상관관계를 구하는 공식을 작성해야한다

 

위와 같은 내용을 전부 담은 코드를 작성해보았다.

1차코드)

import java.util.ArrayList;
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=1; i<=yellow; i++){
            if(yellow %i == 0){
                list.add(i);
            }
        }
        int[] m = {};
        m = list.stream().mapToInt(Integer::intValue).toArray();
        for(int j=0; j<m.length; j++){
            int width = m[j];
            int restofpart = m.length-1-j;
            // if(restofpart<1){
            //     break;
            // }
            int vertical = m[restofpart];
            int brownwidth = (width+2)*2;
            int brownvertical = (width)*2;
            if(brownwidth+brownvertical==brown){
                answer[0] = (width+2);
                answer[1] = (vertical+2);
            }
        }
        return answer;
    }
}

하지만 결과는 예상과 달랐다. 

 

테스트2만을 통과하였고, 나머지는 통과하지 못하였다. 

 

무엇이 문제였을까? 계속 코드를 보던 중, 말도 안되는 실수를 해버리고 말았다. 

갈색 세로 길이를 나타내는 코드에 vertical*2가 아닌 width*2라고 적어둔 것

이를 수정하니 바로 정답이 나왔다. 

 

import java.util.ArrayList;
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=1; i<=yellow; i++){
            if(yellow %i == 0){
                list.add(i);
            }
        }
        //1 2 3 4 6 8 12 24
        int[] m = {};
        m = list.stream().mapToInt(Integer::intValue).toArray();
      
        for(int j=0; j<m.length; j++){
            int width = m[j];
            int restofpart = m.length-1-j;
            // if(restofpart<1){
            //     break;
            // }
            int vertical = m[restofpart];
            int brownwidth = (width+2)*2;
            int brownvertical = (vertical)*2;
            if(brownwidth+brownvertical==brown){
                answer[0] = (width+2);
                answer[1] = (vertical+2);
            }
        }
        return answer;
    }
}