DP 문제들은 앞으로 정리해놓을까 한다. 나한테 어려우면서도 흥미로워서...다음 문제는 메모이제이션을 이용해서 해결한 문제중 기억에 남는 문제중 하나다.
문제
내 풀이
문제를 접근한 방식
해결해야할 문제
- x2 x3 x4 중복이 되지않게 출현시키기. (중복 수 처리)
- 시소짝 '한 쌍'의 갯수에 대한 카운트 처리
해결한 방식
- 아예 처음부터 중복된 숫자들을 테이블에 저장.
이문제의 정답률이 낮은이유는 중복수에 대한 처리가 어렵기 때문이다. 메모이제이션을 어떻게 구상할지는 감이 왔는데, 중간에 헤맸던 이유는 처음부터 [100,100...]이런식의 중복값들이 곱하기가 되었을때 동시에 나타난다면, 횟수처리가 어려웠기 때문이다. 그래서 애초에 중복숫자들의 갯수를 위한 테이블을 만든 후 그 중복처리에 순서쌍을 미리 카운트 해두었다.
- 출현한 값과 출현한 횟수(겹쳐진 숫자의횟수)의 구분.
출현된 값들은 곱해서 나온 수를 겹쳐진 만큼 더해서 저장해야하고, 시소쌍은 곱해서 저장해야한다. 예를들어 [100, 100, 100, 150, 150] 일 경우 중복된 개수는 {100: 3 ,150 : 2} 이며 300이 출현한 빈도는 5번이지만, 시소쌍으로 본다면 2 x 3 , 6개다. 즉, 테이블은 기존 나온 빈도에 더해주고 count는 곱한걸 누적해주면 된다.
오답노트
해당 문제는 이중순회를 통해 짝을 지어주거나 재귀로 조합을 구현해 풀수도 있다.
물론 input의 100,000을 보자마자 통과되지 않을 것 같았지만, 첫번째는 이중순회를 통해 짝을 지어주는 방식으로 풀어보았다. 그리고 원래의 무게가 작은 수의 두배가 넘는다면 큰수는 작은수의 4배가 넘어가기 때문에, 탈출하는 식으로 시간복잡도를 줄이고자 했다.
그치만 애초에 접근을 할 필요가 없었던 것을 인지하자. 10만개의 케이스라면 최소 O(n)안에 해결해야 하는 케이스이기 때문이다. 이중순회를 하게된다면 최대 O(n**2)의 시간이 소요된다.
