[Java] 최소직사각형 Lv1
최소직사각형
문제 프로그래머스 FAQ 내용을 보니 카카오나 기업의 문제들은 저작권이 있으니 풀이를
github나 개인블로그에 올리지 말라고 되어 있어서 링크로 대체합니다.
출처: Programmers
최소직사각형
문제의 이해
문제를 처음 보고 몇가지 생각이 들었다. 진짜 무식하게 반복문으로 푸는 방법과 아마도 이러한 문제는 반복문을 무식하게 때려 넣어서 풀 수도 있고, 동적 계획법(다이나믹 프로그래밍)으로 풀 수 있다는 생각이 들긴 했는데, 현재 내가 이해하고 있는 다이나믹 프로그래밍은 딱 한가지다. 문제를 순서대로 푼다. 주어진 자료들을 전부 한번에 계산해서 답을 도출해 내는 경우도 있고, 하나씩 계산을 해서 도출해 내는 법도 있는데 내가 보기에 이 문제는 하나씩 계산하라고 내준 문제 같았다. 그래서 거창하게 다이나믹 프로그래밍이라고 말하기보다는 그냥 순서대로 풀어보려고 생각했다. 다만 몇가지 문제가 생각이 들었는데
- 가로, 세로를 변경하면서 계산하다가 410과 58 같이 같은 값을 가지고 있을 때는 어떤 계산을 할 것인가?
- 두가지 경우 이상의 뒤집기가 발생했을 때는?
1) 이건 써놓고도 설명하기가 어려운데 예를 들어서
[10, 7]
[12, 3]
[8, 15]
[14, 7]
[5, 15]
이런 데이터가 있을 경우 맨 처음 10, 7 과 12, 3을 계산해서 나온 x, y가 있다고 치면 그 값으로 다음 8, 15나 14, 7과 계산했을 때 나온 값이 맞는 정답이라는 근거가 어딨냐를 아직 모르겠다. 여튼 이런 궁금증이 생겼는데 당장 누가 해결 해줄 방법이 없어서보여서 일단 풀기로 했다.
이해 잘 안되면 그냥 이렇게 손으로 어느정도 풀어보는 게 최고이다.
일단 풀기로 한 이유는 손으로 풀었을 때 정답이 나와서이기도 하다.
다이나믹 프로그래밍도 안본지 오래되고 개념만 아주 살짝 이해하고 있는 단계라 구글 검색으로 알아낸 곳에서 추가 설명을 봤다. https://hongjw1938.tistory.com/47 이 설명을 봤는데 굉장히 설명이 잘 되어있더라. 나도 나중에 이렇게 설명할 수준이 되었으면.. 그리고 설명 중에서 제일 와 닿았던 건 4.DP 사용하기 의 1)DP로 풀 수 있는 문제인지 확인한다. 이 부분이 나도 계속 고민이 되어왔던 부분이다. DP를 사용할 수 있는지 판단하는 게 가장 어려운 것 같다.
내가 생각한 풀이 방법
- sizes[0]에 있는 가로, 세로를 비교할 변수에 저장
- sizes배열을 순회해서 비교. 이때 (w, h) or (h, w) 이렇게 바꿔서 둘 중 어는 것이 더 작은 지 검사해서 더 작은 가로와 세로를 다시 변수에 넣고 계속해서 반복
- sizes배열의 순회가 끝나면 나온 가로와 세로가 정답
풀이
첫번째 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//코드를 짜면서 순간 생각나버린, 발생할 수 있는 문제는
//동일한 곱의 값을 가지는데 숫자가 다른경우가 나올때는(예를들어 10x4와5*8은 값은 동일하지만 다른 숫자다. 어느 것으로 하는 게 맞는걸까? )
public int solution(int[][] sizes) {
int answer = 0;
int[][] dValue = new int[2][2]; //숫자의 가로 세로를 뒤집어 계산하기 위한 2,2배열
dValue[0] = sizes[0].clone(); //깊은 복사
dValue[1] = sizes[0].clone(); //처음에 이거 몰라서 dValue[0] = sizes[0]; 이걸로 했다가 나오는 값이 이상해서 디버깅 하는데
//dValue[0]의 값을 바꿨는데 dValue[1]도 같이 바뀌어서 이렇게 하면 자바에서는 얕은 복사구나 라는 걸 알았다.
for (int i = 1; i < sizes.length; i++) { //주어진 2차원 배열 순회
//가로 세로를 바꾸지 않은 그대로의 계산
dValue[0][0] = (dValue[0][0] < sizes[i][0]) ? sizes[i][0] : dValue[0][0];
dValue[0][1] = (dValue[0][1] < sizes[i][1]) ? sizes[i][1] : dValue[0][1];
//가로 세로를 바꾼 계산
dValue[1][0] = (dValue[1][0] < sizes[i][1]) ? sizes[i][1] : dValue[1][0];
dValue[1][1] = (dValue[1][1] < sizes[i][0]) ? sizes[i][0] : dValue[1][1];
//위에서 계산한 가로세로를 바꾼 것과 안바꾼 것을 비교해서 더 작은 수를 구해서 다시 dValue에 저장
if ((dValue[0][0] * dValue[0][1]) <= (dValue[1][0] * dValue[1][1])) {
dValue[1] = dValue[0].clone();
}
else{
dValue[0] = dValue[1].clone();
}
}
//모든 2차원 배열을 순회 했을 때 마지막으로 남은 가로와 세로를 곱해서 answer변수에 담아서 리턴
answer = dValue[0][0] * dValue[0][1];
return answer;
}
어려운 문제는 아니었는데 동적 계획법, 즉 다이나믹 프로그래밍에 대해서 좀 더 공부하는 게 좋겠다.
Leave a comment