[ALGORITHMS]문제 14 동명이인 찾기 2(딕셔너리)

문제 14

동명이인 찾기 2 (딕셔너리)

n명의 사람 이름 중에 같은 이름을 찾아 집합으로 만들어 돌려주는 알고리즘을 만들어보세요

문제 3에서 살펴본 동명이인 찾기 문제를 다시 풀어 보겠습니다. 동명이인 찾기 문제는 사람들의 이름이 나열된 리스트 안에 같은 이름이 있는지 확인해서 중복된 이름들을 집합으로 돌려주는 문제였습니다. 예를 들어 ["Tom", Jerry", "Mike" "Tom"] 이 입력으로 주어지면 "Tom"이 중복되므로 이를 집합에 넣은 {"Tom"}을 결과로 돌려주면 됩니다.

이번에는 파이썬의 딕셔너리(dictionary, 사전)라는 자료 구조를 이용해서 동명이인 문제를 풀어 보겠습니다. 

1. 딕셔너리

파이썬의 딕셔너리는 정보를 찾는 기준이 되는 키(key)와 그 키에 연결된 값(value)의 대응 관계를 저장하는 자료 구조입니다. 예를 들어 여러사람이 있을때 각 사람의 이름(키)과 나이를 대응시켜 딕셔너리로 쉽게 표현 할 수 있습니다.

지금부터 실행 예를 한 줄씩 살펴보면서 딕셔너리에 대해 알아보겠습니다.

딕셔너리는 중괄호를 이용해 만듭니다. { }안에 대응되는 값을 콜론(:)으로 연결해 주면 딕셔너리가 만들어집니다. 다음과 같이 하면 키 "Justin"에 값 13, 키 "John"에 값 10, 키 "Mike"에 값 값 9가 대응된 딕셔너리가 새로 만들어집니다.

정보가 아무것도 들어 있지 않은 빈 딕셔너리를 만들려면 값이 들어 있지 않은 빈 중괄호 또는 dict()를 이용하면 됩니다.

딕셔너리에서 키로 웧나는 값을 찾으려면 리스트와 마찬가지로 대괄호 안에 키를 적어주면 됩니다.(단, 리스트에서는 대 괄호 안에 원하는 위치 번호를 넣습니다.)

딕셔너리에 없는 키를 대괄호 안에 넣으면 에러가 발생합니다.

딕셔너리에 새 값을 추가하려면 다음과 같이 값을 대입하면 됩니다.

이제 "Summer"라는 키에 1이라는 값이 저장되었습니다.

한 가지 주의할 것은 딕셔너리에는 키가 중복되지 않는다는 점입니다. 

이미 존재하는 키에 새 값을 넣으면 기존 값은 지워지고 새 값으로 덮어써집니다.

* 자주 사용하는 파이썬의 딕셔너리 기능을 정리합니다.

2 딕셔너리 이용한 동명이인 찾기 알고리즘

딕셔너리는 정보를 찾는 기준이 되는 키(key)와 그 키에 해당하는 값(value)이 나열된 것이라고 배웠습니다. 그렇다면 동명이인 문제에 딕셔너리를 어떻게 활용 할 수 있을까요?

각 이름을 키(key)로, 그 이름이 리스트에 등장한 횟수를 값(value)으로 보면 문제를 풀 수 있는 힌트가 보일 것입니다.

문제 14를 처음 봤을때 ["Tom","Jerry","Mike","Tom"] 을 다음과 같이 처리하는 것입니다.

name_dict라는 딕셔너리를 만들고 이 중에서 값(value)이 2 이상인 키(key)를 골라내면 동명이인으로 구성된 집합을 쉽게 얻을 수 있습니다.

이 과정을 알고리즘으로 적으면 다음과 같습니다.

1. 각 이름이 등장하는 횟수를 저장할 빈 딕셔너리(name_dict)를 만듭니다

2. 입력으로 주어진 리스트에서 각 이름을 꺼내면서 반복합니다.

3. 주어진 이름이 name_dict에 있는지 확인합니다.

4. 이미 있다면 등장횟수를 1 증가시킵니다.

5. 아직 없다면 그 이름을 키(key)로 하는 항목을 새로 만들어 1를 저장합니다.

6. 1~5번 과정을 거치면 name_dict에는 리스트에 등장하는 모든 이름과 각각의 등장 횟수가 저장됩니다.

7. 만들어진 딕셔너리에서 등장 횟수가 2이상인 이름을 찾아 결과 집합에 넣은 다음 출력으로 돌려줍니다.

*딕셔너리를 이용해 동명이인을 찾는 알고리즘

3. 알고리즘 분석

문제 3에서 살펴본 동명이인 찾는 알고리즘은 리스트 안에 들어 있는 모든 사람을 서로 한 번씩 비교하여 같은 이름이 있는지 찾아내는 방식이었습니다.

즉, 사람 수가 n일때 계산 복잡도는 O(n^2)이었습니다.

반면 딕셔너리를 이용해 동명이인을 찾는 알고리즘은 1단계로 리스트 정보를 한 번 읽어서 각 이름과 등장 횟수를 딕셔너리에 넣는 동작(n번 처리)을 하고, 2단계로 딕셔너리 안에 저장된 서로 다른 이름을 확인하여 등장 횟수가 2 이상인 자료를 찾습니다.(n번 이하처리). 이는 for 반복문을 겹쳐서 사용하지 않고 따로따로 두 번 반복하는 과정이므로 대문자 O 표기법으로 표현하면 O(n)에 해당합니다.

* 프로그램에서 for 반복문이 여러 번 나올때는 서로 겹치느냐 겹치지 않느냐에 따라 계산 복잡도가 많이 달라집니다.

*연습문제

14-1 연습문제 7-3에서 풀어 본 학생 번호로 학생 이름을 찾는 문제를 딕셔너리를 이용해 풀어보세요

다음과 같이 학생번호와 이름이 주어졌을때 학생 번호를 입력하면 그 학생 번호에 해당하는 이름을 돌려주고, 해당하는 학생 번호가 없으면 물음표를 돌려줘야합니다.

읽어주셔서 감사합니다