[20210528] 프로그래머스 - 카펫 (사각형의 가로 세로 / 폭 높이)

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

코딩테스트 연습 - 카펫

 

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brownyellowreturn

10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

출처

아 너무 짜증났다. 진짜 한 네시간 풀었는데도 계속 실패떴다.

 

첫번째 풀이

: yellow의 가로, 세로 값을 먼저 추정하기로 했다.

추정값(yelEst)과 실제값(yellow)이 바로 같다면 정사각형으로 인지하고 while문을 빠져나오게 했다.

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        int yelH = (int) Math.sqrt(yellow); // yellow의 제곱근(세로최대길이)
        int yelW = (int) Math.sqrt(yellow); // yellow의 제곱근(가로추정길이)
        int yelEst = 0;     // yellow 추정길이
        
        
        if (yellow == 1) {
            answer[0] = 3;
            answer[1] = 3;
            return answer;
        }
        
        
        while (yelH <= yellow / 2) {
            
            yelEst = yelH * yelW;  
            
            if (yellow == yelEst) {     // 정사각형
                break;
                
            } else if (yellow < yelEst) {
                yelH = yelH - 1;
                yelW = yellow / yelH;
                
            } else if (yellow > yelEst) {
                yelW = yelW + 1;
                yelH = yellow / yelW;
            }            
        }
                
        // System.out.println(yelH);
        
        int broW = yelW + 2;
        int broH = yelH + 2;
        if (broW * broH - yellow == brown) {
            answer[0] = broW;
            answer[1] = broH;
        }
        
        return answer;
    }
    

}

 

두 번째 풀이

: 추정값(yelEst)과 실제값(yellow)이 같다고 해서 바로 끝내버리면 안되고,

brown의 추정값도 맞는지 확인하고 틀리면 그 while문을 다시 돌려야 했다.

그래서 맨끝에 있던    
                int broW = yelW + 2;
                int broH = yelH + 2;
                if (broW * broH - yellow == brown) {
                    answer[0] = broW;
                    answer[1] = broH;
                }

이 부분을 while문 안으로 넣게 되었다!

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        int yelH = (int) Math.sqrt(yellow); // yellow의 제곱근(세로최대길이)
        int yelW = (int) Math.sqrt(yellow); // yellow의 제곱근(가로추정길이)
        int yelEst = 0;     // yellow 추정길이
        
        
        if (yellow == 1) {
            answer[0] = 3;
            answer[1] = 3;
            return answer;
        }
        
        
        while (yelH <= yellow / 2) {
            
            yelEst = yelH * yelW;  
            
            if (yellow == yelEst) {     
                int broW = yelW + 2;
                int broH = yelH + 2;
                if (broW * broH - yellow == brown) {
                    answer[0] = broW;
                    answer[1] = broH;
                    
                    break;
                }
            } 
            
            if (yellow < yelEst) {
                yelH = yelH - 1;
            } else if (yellow > yelEst) {
                yelW = yelW + 1;
            } 
            
        }
                
        // System.out.println(yelW+);
        
        
        
        return answer;
    }
    

}

두번째 풀이는 시간초과 발생

 

세번째 풀이

추정값과 실제값 비교할때 <= 으로 바꿔주거나 else문으로 바꿔줘야 한다.

while문 내에서는 모든 케이스를 미리 생각해줘야 한다.

if (yellow <= yelEst) {
     yelH = yelH - 1;

} else if (yellow > yelEst) {
     yelW = yelW + 1;
}

 

그랬더니 통과

최종 풀이 코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {3,3};  // 배열의 크기 미리 할당
        
        int yelH = (int) Math.sqrt(yellow); // yellow의 제곱근(세로)
        int yelW = (int) Math.sqrt(yellow); // yellow의 제곱근(가로)
        int yelEst;     // yellow 추정길이
        
        // 최소값은 미리 생각해주기
        if (yellow == 1) return answer;  // 이거 없으면 test11에서 실패
            
        while (yelH <= yellow / 2) {  
            yelEst = yelH * yelW;   // 추정한 yellow값
            if (yellow == yelEst) { 
  // 추정한 yellow값이 실제 yellow와 같다면, brown 크기도 추정을 시작한다.
                int broW = yelW + 2;    // brown 가로
                int broH = yelH + 2;    // brown 세로
                if (broW * broH - yellow == brown) {    
                    answer[0] = broW;
                    answer[1] = broH;
                    break;      // brown도 추정값이 맞으면 while문 종료
                }
            }   // brown || yellow 둘 중하나라도 틀리면 아래를 실행한다.
            if (yellow < yelEst) {  
            yelH = yelH - 1;		// 추정값이 크다면 세로를 줄여준다.
            } else {    // while문 안에서는 모든 케이스를 생각해줘야함. (안하면 시간초과남)
                yelW = yelW + 1;    // 추정값이 작다면 가로를 늘려준다.
            } 
        }
        return answer;
    }
}

 

아무튼 두개의 인자가 문제에 주어진다면 그 둘 다 조건을 충족하는지 확인하고

둘 중 하나라도 충족하지 않는다면 다시 로직을 태워야 한다는 걸 깨달았다.