프로그래머스 가장 큰 수 : 수 2개만 고려해 봅시다.

 오랫만입니다. 정렬에 대해서 배웠으니, 오늘은 프로그래머스에 있는 가장 큰 수를 풀어보도록 하겠습니다.

 

 쉽지 않아 보입니다. 옛날 (브, 실, 골 티어로 이루어진) USACO 실버나, 아니면 COCI 2번이나 3번 정도에 나왔던 문제로 기억합니다. 일단, 문제가 무엇을 요구하는지는 알았습니다. 조건을 해석해 봅시다.

 

 n의 최댓값이 10만이니, O(nlogn)이나, O(n) 정도의 복잡도를 생각할 수 있습니다. 물론, O(n^2)에서 상수 최적화를 잘 해서 통과할 수도 있겠지만, 상수 최적화 같은 경우에는, ps를 조금 깊숙히 하셔야 하는 부분입니다. 코딩 테스트에서 안 풀리는 복잡도가 정해인데 상수로 잘 뚫어야 하는 문제가 나왔다. 그러면 거르면 됩니다.

 

 

---

 일단, 구하고자 하는 것은, 어떻게 배열을 적절히 재배치 해서, f 함수를 호출하였을 때, 리턴값이 최대가 되게 만드는 것입니다. 그러면, '재배치' 라는 행동에 주목해 봅시다.

 

 그러면 arr이 있을 때, 이것을 재배치 하지 않고, f 함수를 호출해도 됩니다.

 

 그런데, a(2)와 a(1)의 위치를 바꾼 다음에 a 함수를 호출해도 됩니다. 바꾸기만 했지, 배열 내에 있는 수들 중 하나를 다른 것으로 변경하지 않았습니다. 따라서, vaild한 연산입니다. 우리는 이것을 어떻게 잘 '재배치'를 해서, f 함수를 호출했을 때 결과값이 최대가 나오도록 하는 게 목표인데요.

 

 이것을 관점을 바꾸어서 생각해 봅시다.

 

 a(i)가 앞에 오는 게 좋은가? a(j)가 앞에 오는 게 좋은가? 이를 잘 해석해 보면, 2개의 Key를 주고, 어떻게 잘 비교 기준을 세워서 재배치 하면 된다는 말과 동일합니다. 비교 기반 정렬은 2개의 Key를 주고 우선 순위에 따라 재배치 하는 것을 말합니다. 위 표에서 우선 순위를 판단하는 기준이 무엇인가요? i번째 수와 j번째 수 중에서, 어떠한 것이 앞에 와야, f 함수의 리턴값이 최대가 되느냐입니다.

 

 

---

 i번째 수와 j번째 수만을 가지고 우선 순위를 판단하려면, 다른 수들의 배치 순서에 의해서, i와 j의 우선 순위가 바뀌면 안 됩니다. 무슨 이야기인지, 알기 쉽게 설명을 해 드리겠습니다. 예를 들어, 아래와 같은 명제가 있다고 해 봅시다.

 

 사실, 맞는 이야기긴 합니다만. 조건이 빠졌습니다. 나머지 조건이 모두 동일할 때. 사실 기압 때문에 끓는 점이 높아지기도, 낮아지기도 하기 때문입니다. 이제 다시 문제로 돌아와 봅시다. 수 A, B가 있을 때, A가 앞에 와야 하느냐, B가 앞에 와야 하느냐만을 따지려면 어떻게 해야 하나요? 이 상황보다는 조금 더 복잡합니다.

 

 

 92와 923이 있을 때, 어떤 것이 앞에 와야 할까요? 위에 있는 그림을 보면, 923이 앞에 와야 할 거 같습니다. 왜냐하면 923을 92보다 앞에 둔 밑의 수가 92를 923보다 앞에 둔 수보다 크기 때문입니다.

 

 

 이 경우는 또 달라집니다. 923보다 92를 앞에 둘 때 수가 더 커졌다는 것을 알 수 있어요. 9239921보다는 9299231이 더 크다는 것은, 그냥 앞에 3자리만 봐도 알 수 있는 사실입니다.

 

 

 이 때는 어떤가요? 923192보다 921923이 더 작습니다. 923이 앞에 올 때가 92가 앞에 올 때 보다 더 큰 상황이 벌어집니다. A와 B의 우선 순위를 정할 때에는 A와 B 말고, 다른 요소에 의해서 priority가 변경이 되면 안 되는데, 다른 수에 의해 변경이 된 셈입니다. 어떻게 해야 할까요? 간단합니다.

 

 다른 요소를 고려하지 않으면 됩니다. Key 92와 923의 우선 순위를 비교하려면 Key 92와 923만 고려해야 한다는 의미입니다.

 

 

 어떤 게 더 큰가요? 92923이, 92392보다 크다는 것을 알 수 있습니다. 따라서 92의 우선순위가 923보다 높습니다.

 

 

 따라서 compare 함수는 위와 같이 작성할 수 있습니다. 그리고 sort 함수를 이용하면 O(nlogn)에 처리할 수 있습니다.

 

 

---

 더 효율적인 방법은 없을까요? 배열 내의 수는 [0, 10^3] 구간에 속해 있는 정수라는 조건. 이 글을 읽으셨다면, 제가 배열 안에 있는 수의 범위에 밑줄을 치지 않았어도, 그냥 지나치시지 않으셨으리라 생각이 듭니다. 제가 이 조건 또한 강조하는 이유가 있는데요. 생각보다 놓치기 매우 쉬운 조건이기 때문입니다. 그리고, 배열 내의 수에 대한 condition은 생각보다 많이 최적화를 할 수 있는 여지를 남겨두었기 때문입니다. 어떻게 하면 좋을까요? 10초 정도만 간단하게 생각해 봅시다.

 

 음. 감이 오셨나요? compare와 Key 2개를 비교한다. 라는 조건에만 집중하셨다면 못 보셨을 수도 있는데요.

 

 

[0, 1000]까지의 수만 정렬하자.

 우리는 arr에 있는 수의 갯수가 100만개이던, 1000만개이던, 배열 내에 있는 수가 [0, 10^3] 범위에 있다는 사실은 변하지 않습니다. 그런가요? 이렇게 해 봅시다. 0부터 1000까지 수를 vector이던, array에 넣어놓습니다. 그러면 이 데이터를 우리가 설정한 우선 순위에 따라 정렬을 할 수 있습니다.

 

 

 그 다음에, 우선 순위가 제일 높은 것 부터 탐색을 합니다. 예를 들어 9, 99, ... 이런 식으로 정렬이 되었다면, 9가 몇 개 있느냐, 99가 몇 개 있는지 부터 탐색을 하면 됩니다. 예를 들어 9가 2개 있고, 99가 1개 있다면, 9 9 99 이렇게 search를 하면 됩니다. 배열 안에 있는 수의 집합은 [0, 10^3]이므로, 아예 sort를 하는 집합을 10^5개에서 10^3개로 줄여놓습니다. compress를 시켜놓은 다음에, 정렬을 해 놓은 것과, x가 몇 번 나왔는지를 기록해 두면, 우선 순위가 높은 것부터 낮은 순으로 탐색하면서, 채워나갈 수 있습니다.

 

 그러면, 10만log(10만)C에서, (1000log(1000) + 10만)C로 줄일 수 있습니다. 여기서 C는 compare 함수의 상수, 혹은 복잡도 정도로 해석해도 무난합니다.