99클럽 코테 스터디 9일자 TIL + 완전탐색

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/42842?language=java(프로그래머스)

학습 키워드

완전탐색

시도 방법

(1) brown + yellow 의 개수로 가로x세로 가 될수있는 모든 케이스를 저장하였음

ex) 12 라면 [1,12] , [2,6] , [3,4] , [4,3] , [6,2][12,1]

(2) 위 문제를 해석해보면 brown 격자는 항상 yellow를 1줄로 감싸고 있음. 즉, brown 가로개수에서 -2을 하면 내부의 yellow 가로가 되고 brown 새로 개수에서 -2를 하면 내부의 yellow 세로가 됨

ex) brown 가로 4 , 세로 3 이면 yellow는 가로 2 , 세로 1

(3) 위 규칙을 적용해서 전체개수 (brown의 가로 x 세로) 에서 내부에 있는 새로 개수 (yellow 의 가로 x 새로) 를 제외한 개수가 문제에 제시된 brown 의 개수와 동일하면 리턴.

ex)
brown 의 가로x세로 = 12
yellow의 가로x세로 = 2
둘을 빼면 10이 되고, 이는 yellow를 제외한 brown의 색 개수인 10과 동일함

내가 작성한 코드

import java.util.ArrayList; 

class Solution {
    public int[] solution(int brown, int yellow) {        
        int[] answer = {};
        
        ArrayList<Integer[]> cases  = resultCandidates(brown+yellow); //가로 세로 길이 경우의 수가 들어있음
        
        for(int i = 0 ; i<cases.size() ; i++) {
            
            int brownHorizontal = cases.get(i)[0]; 
            int brownVertical = cases.get(i)[1] ; 

            int yellowHorizontal = brownHorizontal-2; 
            int yellowVertical = brownVertical-2 ; 
            
            if(brownHorizontal * brownVertical - yellowHorizontal * yellowVertical == brown) {
                return new int[]{ brownHorizontal , brownVertical } ; 
            }
        }
        
        return answer;
    }
    
    public ArrayList<Integer[]> resultCandidates(int num) {
        
        ArrayList<Integer[]> tmp = new ArrayList<>(); 
        
        int divisor = 1; 
        
        while(divisor <= num) {
            
            if(num/divisor < divisor) break; 
            
            if(num % divisor == 0) {
                tmp.add(new Integer[]{num/divisor , divisor }); 
            }
            
            divisor++; 
        }

        return tmp; 
    }
}

코드설명

(1) resultCandidates 메서드로 가로x세로가 가능한 경우의 수를 찾는다.
이때 brown이 yellow보다 가로가 같거나 더 길기때문에 [3,4] 같은 순서부터는
break를 걸었다.
ex) 12 => [12,1][6,2] [4,3] // brown 가로개수 , brown 새로 개수

(2) 모든 경우의 수를 돌리며 ####시도방법 에서 설명한 수학적 지식을 이용해
일치하는 경우를 리턴한다.

실행결과

새롭게 알게된 점

없음

다음에 풀어볼 문제 - 소수찾기

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL