[오늘의 문제] 카펫

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

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

carpet.png

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

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

제한사항
갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
입출력 예
brown yellow return
10 2 [4, 3]
8 1 [3, 3]
24 24 [8, 6]
출처

※ 공지 - 2020년 2월 3일 테스트케이스가 추가되었습니다.
※ 공지 - 2020년 5월 11일 웹접근성을 고려하여 빨간색을 노란색으로 수정하였습니다.

내가 작성한 코드문

import java.util.*;
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        int width = brown + yellow;
        
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
        
        for(int i = 1; i <= width; i++){
            
            
            // 단, 가로 길이가 세로 길이보다 크거나 같게 
            if(width / i < i){
                break;
            }
            
            if(width % i == 0){
                map.put(width / i, i);// 가로 길이를 키 값, 세로 길이를 밸류 값에 저장
            }    
            // 여기에 다음 변수를 정의하고 yellow 일치시 for문 break 하는 식으로 하기 
            int innerWidth = (width / i) - 2;
            int innerHeight = i - 2;
            if(innerWidth == yellow){
                break;
            }
            
        }
        
        // 가장 마지막 인덱스 answer 배열에 저장 -> 이렇게 하면 무조건 마지막 값만 저장하게 됨
        // 22, 8 에서 에러가 뜨게 됨 
        for (Map.Entry<Integer, Integer> elem : map.entrySet()) {
            answer[0] = elem.getKey();
            answer[1] = elem.getValue();
        }

        return answer;
    }
}

❌ 문제점 요약
innerWidth == yellow ❌
→ 노란색 카펫의 넓이(yellow)는 (가로 - 2) * (세로 - 2)여야 함
→ innerWidth == yellow는 전혀 맞지 않습니다.

LinkedHashMap에 모든 후보를 저장하고 마지막 값만 반환하는 방식
→ 최종 조건을 검증하지 않으면 틀린 값이 저장될 수 있음

요구 사항 충족하는 코드문

import java.util.*;
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        int total = brown + yellow;
        
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
        
        for(int i = 1; i <= total; i++){
            if (total % i != 0) continue;
            int width = total / i;
            int height = i;
            
            // 여기에 다음 변수를 정의하고 yellow 일치시 for문 break 하는 식으로 하기 
            if (width < height) continue; // 가로 ≥ 세로

            int innerWidth = width - 2;
            int innerHeight = height - 2;
            
            if(innerWidth * innerHeight == yellow){
                map.put(width, height);
                // answer[0] = width;
                // answer[1] = height;
            }
            
        }
        
        // 가장 마지막 인덱스 answer 배열에 저장 -> 이렇게 하면 무조건 마지막 값만 저장하게 됨
        // 22, 8 에서 에러가 뜨게 됨 
        for (Map.Entry<Integer, Integer> elem : map.entrySet()) {
            answer[0] = elem.getKey();
            answer[1] = elem.getValue();
        }

        return answer;
    }
}

그리고 링크드맵을 뺀 버전

import java.util.*;
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        int total = brown + yellow;
        
        // LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
        
        for(int i = 1; i <= total; i++){
            if (total % i != 0) continue;
            int width = total / i;
            int height = i;
            
            // 여기에 다음 변수를 정의하고 yellow 일치시 for문 break 하는 식으로 하기 
            if (width < height) continue; // 가로 ≥ 세로

            int innerWidth = width - 2;
            int innerHeight = height - 2;
            
            if(innerWidth * innerHeight == yellow){
                // map.put(width, height);
                answer[0] = width;
                answer[1] = height;
            }
            
        }
        

        return answer;
    }
}

그외에 다른 사람들 풀이

class Solution {
    public int[] solution(int brown, int red) {
        int[] answer = {};
        answer = new int[2];
        int iAllNum = brown + red;
        int iHeight = 0;

        for (int iBrownWidth = 1; iBrownWidth < brown; iBrownWidth++) {
            iHeight = iAllNum/iBrownWidth;

            if((iBrownWidth-2)*(iHeight-2) == red) {
                answer[0] = iBrownWidth;
                answer[1] = iHeight;
            }
        }
        return answer;
    }
}

class Solution {
    public int [] solution(int brown, int red){
        int [] answer = new int[2];
        int n = brown / 2 + 2; // 가로세로의 총 길이는 brown / 2 + 2
        int length = n - 1, width = n - length; // length: 가로, width: 세로
        while(length >= width){
            int temp = (length - 2) * (width - 2);
            if(temp == red) {
                answer[0] = length;
                answer[1] = width;
                break;
            }
            length -= 1;
            width += 1;
        }
        return answer;
    }
}

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int width = 0, height = 0;
        int i, temp;
        
        for(i = 1; i * i <= yellow; i++)
        {
            if(yellow % i == 0){
                width = yellow / i;
                height = i;
                System.out.println("yellow width : " + width);
                System.out.println("yellow height : " + height);
                if(brown == ((width * 2) + (height * 2) + 4)){
                    answer[0] = width + 2;
                    answer[1] = height + 2;
                    System.out.println("brown width : " + answer[0]);
                    System.out.println("brown height : " + answer[1]);
                    break;
                }
            }
        }
        if(answer[0] < answer[1]){
            temp = answer[0];
            answer[0] = answer[1];
            answer[1] = temp;
        }
        
        return answer;
    }
}