[프로그래머스][최소직사각형] - 그리디 문제

안녕하세요 Dibrary 입니다.

이번에는 과거에 풀지 못했던 문제를 다시 도전했는데, 생각외로? 쉽게 풀려서 당황했는데, 왜 그런 느낌을 받았는지를 정리해보고자 합니다.

문제는 '최소 직사각형'이라는 문제인데, 처음에 맞이했을 때의 그 느낌을 아직도 잊을 수 없습니다. (알고리즘을 아예 풀지 못하면서 BOJ에서 A+B 이런거만 건드릴 때 였죠...)

프로그래머스

 

---

지금에 와서야 이 문제가 '그리디'고, 문제에 '숨은' 조건을 찾는 것이 중요하다는 것을 알지만, 처음에는 아예 몰랐습니다.

처음에 이 문제를 맞닥뜨리고 느낀 생각은 아래와 같습니다.

1. 돌아갈 수 있는 것을 어떻게 알지?
2. 돌아갈 수 있는게 연속되면 어떻게 알지?
3. 꼭 오른쪽으로만 돌리지 않고 왼쪽으로도 돌리면 어떻게 해야 하지?
4. 하나도 안 돌려도 되는 것과, 돌려야 하는 것은 뭔 차이가 있는 걸까?

네 아주 온갖 궁금증의 산에 갇혀서 결국 손도 대지 못했었죠.

 

우선 풀이 부터 소개하자면, 다 한가지 방향으로 넘겨보면 되는 겁니다.

저는 좌, 우 값을 비교해서 큰 것을 모조리 왼쪽에 몰아 넣었습니다.

그렇게 한 후에 최대값만 곱하면 최대 공간이 되는 것이라고 생각을 했으니까요. 결과는 통과입니다.

 

---

지금 생각해보면 너무 간단한 생각인데, 왜 그때는 그 생각을 못했을까요? 

먼저, 알고리즘을 공부하지 않아서 라는 이유가 떠오릅니다.

닥치는대로 맨땅에 헤딩하면서 풀어낼 수 있긴 합니다. 그러나, 이미 수십년에 걸쳐 사람들이 찾아 정리해 놓은 것을 활용한다면? 당연히 더 유용하고, 그 기초 '위에' 쌓아나갈 수 있으니 시간도 절약이 되죠.

그래서 문제를 보기 전에 어느정도의 '공부'를 하는 것을 추천합니다.

 

그리고, 처음 문제를 맞닥뜨렸을 때 고민한 걱정들을 왜 했는지? 에 대한 생각이 들었습니다.

코드를 보면 무조건 한 방향으로 다 몰빵 해 버리는 '규칙'을 찾아버리면 되는 것이었죠. 즉, 회전은 '내 마음대로 해도 된다'는 것인데... '이게 중간중간에 만 있다면' 이런 가정에 갇혔던 것이죠.

 

지금에서는 손쉽게 풀면서 감회가 남달랐던 문제네요.