https://programmers.co.kr/learn/courses/30/lessons/12987
-
flow
처음에 생각났던 것은 B.count(2)와 A.count(1) 로 시작해서 1과 2를 매칭시키고 계속 나아가는 방식이였음..
A의 수가 남으면 다음 index count 수에 덧셈이 되고 B는 수가 남든 안남든 버려지는 방식.. 근데 막상 짜려고보니 시간복잡도가 안 좋게 나와서 비슷한 논리로 다른 방법을 생각하게 됨.
A 와 B를 정렬해놓고, 작은 수부터 서로 비교하면서 B가 지거나 비기는 수면 다음 인덱스로 가고 이기는 수가 되면 매칭시키고 A와 B 모두 다음 인덱스로 넘어가는 식.. 이러면 O(N) 의 시간복잡도로 처음 생각했던 것과 같은 결과를 가질 수 있게 됨. 아차.. 왜 이게 답이냐면 greedy 하게 생각해보면 됨.. A의 작은 수부터 B가 가지고 있는 수중 이길 수 있는 가장 작은 수를 매칭 시킨다고 생각.. (만약 그게 아니라면? 일부러 지는 수를 붙인다? 왜? 다른 경우는 더 큰 수를 이용해서 이긴다? 이건 더 말도 안됨.) -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A26.py
