[리마인드] 완전탐색(완탐, 브루트 포스) 코딩테스트 문제

 

오늘의 학습 키워드

완전탐색
완탐
브루트 포스

 

 

다시풀기 문제

1. 프로그래머스 Level 2 - 카펫

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

프로그래머스

• Github 풀이

Algorithm-Practice/프로그래머스/2/42842. 카펫 at main · dev-jinius/Algorithm-Practice

 

 

회고

1. 프로그래머스 Level 2 - 카펫

어디까지 생각해봤나?

• 문제를 보고, yellow 타일의 크기에 따라 brown 타일이 정해질 수 있다고 생각했다.
• 즉, yellow의 가로, 세로 길이는 brown의 가로, 세로 길이에 영향을 주고, 전체 크기는 yellow와 brown을 합친 개수라고 생각했다. 
• 문제에서 (가로길이 > 세로길이) 라고 해줬기 때문에 전체 개수와 가로인지 세로인지 몰라도 2개의 변의 길이를 알면 풀 수 있었다.
• 먼저 yellow 개수로 만들수 있는 2개의 변의 길이를 찾아보았다. => 알고보니 약수를 찾는 것.
• 이미지를 생각해보니, brown은 yellow의 각 변의 길이의 +2한 길이였다.
• 주어진 조건에서 yellow 개수 + brown 개수는 총 타일의 개수인 점을 활용했다.

핵심

• 전체 타일의 개수와 직사각형의 길이의 관계에 대해 파악하기.
• 약수 활용하기

예전에 풀었던 풀이

• 뭔가 어렵게 푼 것 같다.

import java.util.*;

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        int totalCount = brown + yellow;
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 3; i*i<= totalCount; i++) {
            if (totalCount % i == 0) {
				numMap.put(i, totalCount/i);                
            }
        }
        
        for (int n : numMap.keySet()) {
            int sero = n;
            int garo = numMap.get(n);
            if (garo * 2 >= brown) continue;
            else {
                if((brown-garo*2) % (sero-2) == 0 || yellow % sero == 0) {
                    answer[0] = garo;
                    answer[1] = sero;
                    break;
                } else continue;
            }
        }
        
        return answer;
    }
}

 

오늘 풀이

• 나도 모르게 좀 생각하고 푸는 연습이 된 건가 예전과 다른 풀이가 되었다.

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

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i*i <= yellow; i++) {
            if (yellow%i == 0)
                list.add(i);
        }
        
        for (int y : list) {
            if (brown == ((y+2)*(yellow/y+2)-yellow)) {
                answer[0] = Math.max(y, yellow/y)+2;
                answer[1] = (brown+yellow)/answer[0];
            }
        }    
            
        return answer;
    }
}

 

좀 더 이해하기 쉬운 계산식

• feat. Chat GPT

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

        // 전체 타일 개수의 약수 탐색
        for (int height = 1; height <= Math.sqrt(total); height++) {
            if (total % height == 0) { // 약수 조건
                int width = total / height;

                // 노란색 타일 조건 확인
                if ((width - 2) * (height - 2) == yellow) {
                    return new int[] {width, height};
                }
            }
        }
        return null; // 문제 조건상 여기에 도달하지 않음
    }
}