[문제출처 : Codechef] 세 명의 투표자가 각각 뽑은 숫자들의 리스트를 가지고 있습니다. 집계자는 세명 중에 두명 이상이 선택하는 숫자들을 뽑아내고 싶습니다. 어떻게 하면 될까요?
예를들면,
[23, 30, 42, 57, 90]
[21, 23, 35, 57, 90, 92]
[21, 23, 30, 57, 90]
의 리스트가 있을 때에, 집계자는 결국
[21, 23, 30, 57, 90]
을 뽑아내게 됩니다.
이미 여러 예제들을 통해서 학습되셨다시피, sorting을 활용하면 손쉽고 효율적으로 풀어낼 수 있겠죠?? :)
- 일단은 세 개의 숫자 리스트를 합치고 정렬합니다.
- 두 수씩 비교해나가면서, 두 수가 같으면
pointer += 2를 해주고, 그렇지 않으면pointer += 1을 해줍니다. 이것이 가능한 이유는 설령 세개의 같은 숫자가 있다고 하더라도, 어차피 무조건 세번째 숫자와 그 다음 숫자는 다를 것이기 때문에 다음번 검사에서 같지 않다고 결론내고 다음 검사(pointer += 1)로 이동할 것입니다. - 같지 않은 경우에는 그냥
pointer += 1해서 계속 검사해 나갑니다.
이를 코드로 짜보면 다음과 같습니다.
def majorityVotes(L1, L2, L3):
L = sorted(L1 + L2 + L3)
result = []
i = 0
while i < len(L)-1:
if L[i] == L[i+1]:
result.append(L[i])
i += 2
else:
i += 1
return result
>>> L1 = [23, 30, 42, 57, 90]
>>> L2 = [21, 23, 35, 57, 90, 92]
>>> L3 = [21, 23, 30, 57, 90]
>>> print majorityVotes(L1, L2, L3)
[21, 23, 30, 57, 90]다시 한번 sorting이 알고리즘에서 얼마나 중요한지 생각해볼 수 있겠죠? ^^