[Java] 카펫 - Lv2 프로그래머스 완전탐색 / 코딩테스트 고득점 Kit

https://school.programmers.co.kr/learn/courses/30/lessons/42842#

프로그래머스

 

 

풀이

---

1. div메서드를 통해 총 카펫 크기의 약수를 모조리 구한다.

public void div(int sum) {
    for(int i=1; i<=sum/2; i++) {
        if(sum%i==0) {
            list.add(i);
        }
    }
    list.add(sum);
}

 

 

2. list 사이즈가 짝수일 경우만 고려해주었다. 홀수일 경우는 x*x=sum이 되는 x의 값이 정답이라고 생각함.

 

총 카펫 크기에 대한 약수를 구했기 때문에, 해당 약수의 곱이 yellow가 일치하는지 꼭 확인해주어야했다.

예를들어 brown = 18 yellow = 6일 경우 검증해주지 않으면 8,3의 정답이 6,4가 나와버린다.

if(list.size()%2==0) {
    int x = list.size()/2;
    int y = list.size()/2-1;

    while((list.get(x)-2)*(list.get(y)-2)!=yellow) {
        y--;
        x++;
    }
    answer[0] = list.get(x);
    answer[1] = list.get(y);
}
else {
    answer[0] = list.get(list.size()/2);
    answer[1] = list.get(list.size()/2);                
}

 

 

전체 코드

import java.util.ArrayList;
import java.util.List;

class Solution {

    static List<Integer> list = new ArrayList<>();

    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int sum = brown+yellow;       
        div(sum);
        
        if(list.size()%2==0) {
        	int x = list.size()/2;
        	int y = list.size()/2-1;
            
        	while((list.get(x)-2)*(list.get(y)-2)!=yellow) {
        		y--;
        		x++;
        	}
            answer[0] = list.get(x);
            answer[1] = list.get(y);
        }
        else {
            answer[0] = list.get(list.size()/2);
            answer[1] = list.get(list.size()/2);                
        }        
        return answer;
    }

    public void div(int sum) {
        for(int i=1; i<=sum/2; i++) {
        	if(sum%i==0) {
        		list.add(i);
        	}
        }
        list.add(sum);
    }
}

 

 

 

 

 

 

다른 풀이

---

프로그래머스 내의 신재권님의 풀이가 비슷한 접근방법이면서도 엄청 간단하게 풀어진 것 같아서 리뷰해보려 한다.

class Solution {
    public static int[] solution(int brown, int yellow) {
        int sum = brown + yellow;

        return find(yellow, sum);
    }

    private static int[] find(int yellow, int sum) {
        int y = 0, x = 0;

        for (int i = 1; i <= yellow; i++) {
            if (yellow % i == 0) {
                y = Math.min(i, yellow / i);
                x = Math.max(i, yellow / i);
                if ((y + 2) * (x + 2) == sum) {
                    break;
                }
            }
        }

        return new int[] {x + 2, y + 2};
    }
}

 

같은 약수를 찾는 완전탐색이지만,

yellow자체를 처음부터 나눠가면서 x+2,y+2의 곱이 전체 카펫의 크기와 같을 때 리턴해주었다.

내가 x-2, y-2로 yellow 자체의 크기와 비교한 것과 같은 맥락으로

x+2, y+2를 했을 경우 sum의 x와 y의 길이일 것이기 때문에, 곱했을 경우 전체 카펫의 크기가 된다.

 

똑같은 접근 방법이라고 생각하지만, 훨씬 간략한 코드인 것 같다.