Menu

Subscribe

[JAVA/프로그래머스] 완전탐색_카펫

HEESOO on Programmers

👀 문제

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

👊 첫 번째 도전

1. 설계

  1. red로 만들 수 있는 약수 조합(가로>=세로)을 찾아서 Carpet형태로 스택에 저장한다.
  2. 스택을 하나씩 뽑아서 둘레 길이가 brown과 같으면 그 값을 answer로 리턴한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

import java.util.Stack;
/**
 *
 * @author HEESOO
 *
 */
 class Carpet{
     int width;
     int height;
     public Carpet(int w, int h){
         this.width=w;
         this.height=h;
     }
 }
 class Solution {
     public void divisor(int brown, int red, Stack st){
         st.push(new Carpet(red, 1));
         int j;
         for(int i=2;i*i<=red;i++){
             if(red%i==0){
                 j=red/i;
                 if(i>j){
                     st.push(new Carpet(i,j));
                 }
                 else{
                     st.push(new Carpet(j,i));
                 }
             }
         }
     }
     public void check(Stack st, int brown, int[] answer){
         Carpet cp;
         int round;
         while(!st.isEmpty()){
             cp=(Carpet)st.pop();
             round=2*(cp.width+cp.height)+4;
             if(round==brown){
                 answer[0]=cp.width+2;
                 answer[1]=cp.height+2;
                 break;
             }
         }
     }
     public int[] solution(int brown, int red) {
         int[] answer = {};
         answer=new int[2];
         Stack<Carpet> st=new Stack<>();
         divisor(brown, red, st);
         check(st, brown, answer);
         return answer;
     }
 }

3. 코드 설명

  • class Carpet: red로 만들 수 있는 가로 세로 조합을 찾아서 스택에 함께 저장하기 위해 Carpet 클래스를 생성하였다.
    • int width: 가로
    • int height: 세로를 저장한다.
  • pulib void divisor(int brown, int red, Stack st): red의 약수를 찾는 메소드이다. i는 2부터 시작해 약수인지 판별한다. i를 찾는 즉시 대응값 j도 찾으므로 굳이 red까지 반복할 이유는 없다. red가 제곱값일때 i가 최대가 되므로 i*i<=red까지만 순회한다.
    for문안의 처음 if를 통해 red가 i로 나눠지는지 확인한다. 나눠진다면 약수이므로 j를 찾고, 카펫은 가로가 세로보다 같거나 크므로 부등호를 통해 나눠서 Carpet 형태로 스택에 저장한다.
    • int i: i는 2부터 시작하여 red의 약수를 찾는다.
    • int j: i를 찾으면 거기에 대응하는 값을 j에 저장한다(예를 들어 24의 약수인 3에 대응하는 숫자는 8이다).
  • public void check(Stack st, int brown, int[] answer): 스택안의 값을 뽑으면서 해당 값이 조건에 만족하는지 체크한다. brown은 red를 감싸야하므로 red의 둘레에 +4를 한 것과 같다. 계산한 round가 brown과 같다면 이것이 정답이므로 answer에 값을 넣고 종료한다.
    • Carpet cp: 스택에서 뽑은 값을 저장한다.
    • int round: cp로 둘레를 구한다.
  • public int[] solution(int brown, int red): divisor()로 red의 약수를 모두 찾아 스택에 저장한 후, check()를 통해 조건에 맞는 지 확인 후 answer에 저장해 리턴한다.
    • Stack st: red로 잡을 수 있는 모양(약수)을 저장한다.

4. 결과

실행결과 🤟 성공 🤟

👏 해결 완료!

쉬운 문제였다! 근데 다른 사람들은 더 간단하게 풀은 것 같다.