2동명이인을 찾는 알고리즘

 

결괏값을 저장할 집합을 알아보았으므로 지금부터는 문제를 실제로 풀어 보겠습니다.

앞의 예시처럼 단순히 이름이 네 개만 들어 있는 짧은 리스트라면 Tom이 두 번 나온다는 것을 바로 알 수 있습니다. 사람이 이 문제를 어떻게 풀지 생각해 보면 다음과 같을 것입니다.

 

1 | 첫 번째 Tom을 뒤에 있는 Jerry, Mike, Tom과 차례로 비교합니다.

2 | 첫 번째 Tom과 마지막 Tom이 같으므로 동명이인입니다(동명이인: Tom).

3 | 두 번째 Jerry를 뒤에 있는 Mike, Tom과 비교합니다(앞에 있는 Tom과는 이미 비교했음).

4 | 세 번째 Mike를 뒤에 있는 Tom과 비교합니다.

5 | 마지막 Tom은 비교하지 않아도 됩니다(이미 앞에서 비교했음).

6 | 같은 이름은 Tom 하나뿐입니다.