[프로그래머스] 카펫(java)

문제

카펫

문제 풀이

1. brown + yellow를 소인수 분해한다.
2. brown + yellow를 편의상 A라고 치환하고, A가 어떤수의 제곱일 경우와 아닐 경우가 있다.
3. 제곱이 아닐경우 항상 소인수a X 소인수b 의 형태로 나온다.
4. (a-2) X (b-2) = yellow 인 경우가 답이다.

어떤수의 제곱이 아닌이상 무조건 페어로 떨어지기 때문에 작은수를 스택 s1, 큰수를 스택 s2에 저장한다.

그 후 s1을 빼서 덱 앞에 삽입, s2를 빼서 덱 뒤에 삽입한다.

그럼 덱에 소인수 분해한 숫자들이 전부 들어가 있는데, 양쪽에서 하나씩 빼면서 a-2 X b-2 = yellow 가 맞는지 확인한다. 전체 타일의 행의 개수-2 X 열의 개수 -2 는 항상 yellow의 개수가 나오기 때문이다.

전체 타일의 수가 어떤 수의 제곱의 형태를 띌 경우는 예외로 처리해준다.

프로그램 코드

import java.util.*;
class Solution {
    public int[] solution(int brown, int yellow) {
		int[] answer = new int[2];
		Stack<Integer> s1 = new Stack();
		Stack<Integer> s2 = new Stack();
		Deque<Integer> d = new LinkedList();

		for (int i = 1; i <= Math.sqrt(brown + yellow); i++) { // 소인수 분해 후 s1, s2에 담음
			if ((brown + yellow) % i == 0) { // 나누어 떨어지면
				if (i * i == brown + yellow) { // 어떤 수의 제곱일 경우
					s1.push(i);
				} else {
					s1.push(i);
					s2.push((brown + yellow) / i);
				}
			}
		}

		if (s1.size() == s2.size()) { // s1을 뽑아서 덱 앞으로, s2뽑아서 덱 뒤로 삽입
			while (!s1.isEmpty()) {
				d.offerFirst(s1.pop());
				d.offerLast(s2.pop());
			}
		} else { // 제곱일 경우
			while (!s2.isEmpty()) {
				d.offerFirst(s1.pop());
				d.offerLast(s2.pop());
			}
			d.offerFirst(s1.pop());
		}

		int dSize = d.size();
		if (d.size() % 2 == 0) {
			for (int i = 0; i < dSize / 2; i++) {
				int left = d.pollFirst();
				int right = d.pollLast();
				if ((left - 2) * (right - 2) == yellow) { // 정답
					answer[0] = right; // 큰 숫자가 처음 들어감
					answer[1] = left;
					break;
				}
			}
		} else {// 제곱일경우
			for (int i = 0; i < dSize / 2; i++) {
				int left = d.pollFirst();
				int right = d.pollLast();
				if ((left - 2) * (right - 2) == yellow) { // 정답
					answer[0] = right; // 큰 숫자가 처음 들어감
					answer[1] = left;
					break;
				}
			}
			if (answer[0] == 0) { // 어떤 수의 제곱이 답인 경우
				answer[0] = answer[1] = (int) Math.sqrt(brown + yellow);
			}

		}
        return answer;
    }
}