카펫 (자바)

김재현·2023년 12월 15일
0

알고리즘 풀이

목록 보기
54/90

문제

정답 코드

import java.util.HashMap;
import java.util.Map;
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {0,0};
        
        // 전체 가로세로 맵 구하기
        Map<Integer, Integer> wholeMap = new HashMap<>();
        for (int i = 3; i <= brown + yellow; i++) {
            int j = (brown + yellow) / i;
            if (i>=j && i * j == brown + yellow) {
                wholeMap.put(i, j);
            }
        }

		// yellow 가로세로 맵 구하기
        Map<Integer, Integer> yellowMap = new HashMap<>();
        for (int i = 1; i <= yellow; i++) {
            int j = (yellow) / i;
            if (i>=j && i * j == yellow) {
                yellowMap.put(i, j);
            }
        }
		
        // 구한 맵끼리 비교
        for (Map.Entry<Integer, Integer> wholeEntry : wholeMap.entrySet()) {
            for (Map.Entry<Integer, Integer> yellowEntry : yellowMap.entrySet()) {
                if (wholeEntry.getKey() == yellowEntry.getKey() + 2 && wholeEntry.getValue() == yellowEntry.getValue() + 2) {
                    answer[0] = wholeEntry.getKey();
                    answer[1] = wholeEntry.getValue();
                    return answer;
                }
            }
        }
        
        return answer;
    }
}

왜 이렇게 복잡하게 풀었나 변명을 해보자면...

나는 처음에 brown이 1겹이 아니라 2겹, 3겹 등등 더 많은 layer를 가질 수 있다고 이해했다.

그러나 그렇게 풀이했을 때 테스트에서 실패케이스가 생겨서 다른 사람의 풀이를 참고하니 brown은 1겹만 존재한다는걸 알았다. 문제 설명이 애매한거 아닌가 싶다.

다른 사람 풀이

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];

        int xy = yellow;
        //(2 + x)*(2 + y) = yellow + brown
        //4 + 2x + 2y + xy = yellow + brown
        // 4 + 2(x+y)= brown
        //2(x+y) = brown - 4
        int sum = (brown - 4)/2;

        for(int i=1;i <= sum/2 ; i++){
            int y = i;
            int x = sum - i;   
            if(x * y == xy){
                answer[0] = x+2;
                answer[1] = y+2;
                return answer;
            }
        }
        
        return answer;
    }
}

brown이 yellow +2 로 정해져있기에 수학 공식을 적용시켜서 yellow의 x,y만 찾는다.

그 뒤에 각각 2를 더해 return!

더 추가하자면 i<=sum/2 대신 제곱근을 사용하면 속도면에서 더 유리할 수 있을 것 같다.

profile
I live in Seoul, Korea, Handsome

0개의 댓글