Couples Holding Hands 문제풀이

안녕하세요. 휴먼스케이프의 개발자 김병하입니다.

이 번 포스팅에서는 쉬어 가는 느낌으로 재미있는 알고리즘 문제풀이를 해보겠습니다. 문제를 설명하고 저의 풀이법을 전달해 드릴 건데, 모든 퍼즐이나 문제들이 그렇듯이 바로 답을 보면 재미없으니 문제를 보고 충분히 풀이법을 생각해보시고 보면 좋을 것 같아요. 문제는 www.leetcode.com에서 본 Couples Holding Hands 라는 제목의 문제입니다.

Couples Holding Hands 문제 설명

휴먼스케이프를 찾아온 커플들이 있고, 각 커플은 2명으로 구성되어 있습니다. 저희 휴먼스케이프는 성적 다양성을 존중함으로 각 커플의 남녀는 구분하지 않습니다. 각 커플들은 상대방의 옆에 나란히 앉아 있고 싶습니다. 그런데 현재는 랜덤하게 일렬로 앉아 있네요. 그래서 사랑과 평화를 위해 커플들이 자신의 상대방과 나란히 앉아 있을 수 있도록 자리를 재배치해야 합니다. 하지만 다 같이 일어나면 너무 소란스럽기 때문에 한 번에 두 명만 일어나서 서로 자리를 바꾸는 자리 맞교환만 가능합니다. 이 때, 최소 몇 번의 자리 맞교환을 해야 모든 커플들이 자신의 상대방의 옆에 나란히 앉을 수 있을까요?

총 N 팀의 커플이 있고, 각 커플은 다행히 2명으로 이루어져 있습니다. 그러니까 총 2N 명의 사람이 있겠네요. 의자는 거기에 맞춰 총 2N 개가 일렬로 놓여있습니다. 각 사람은 0 부터 2N-1 까지의 번호가 있고, 0 번과 1 번, 2 번과 3번, … 2i 번과 2i+1 번은 서로 커플입니다. 즉 (0, 1), (2, 3), …, (2i, 2i+1), …, (2n-2, 2n-1) 이렇게 각각 커플입니다. 사람들이 현재 앉아 있는 자리는 row[i] 라는 배열로 전달됩니다. 즉 row[i] 에 있는 값은 i 번 자리에 앉아 있는 사람의 번호를 뜻합니다.

예를 들어 row = [0, 2, 1, 3] 과 같은 입력이 들어오면 답은 1입니다. 왜냐하면 2 번과 1 번이 서로 자리 맞교환을 하면 0은 1과, 2는 3과 옆에 앉을 수 있기 때문이죠.

Couples Holding Hands 문제 풀이

위에 설명된 문제를 어떻게 풀지 천천히 생각해보고 풀이를 봐주세요.

충분히 생각하셨다면 이제 풀이를 시작하겠습니다.

hash table을 이용한 풀이

자리 바꾸는 과정을 시뮬레이션해보죠. 0번 자리부터 보면서 그 사람의 파트너를 찾아, 바로 옆인 1번 자리로 데려와 주는 거죠. 그리고 그 다음은 2번째 자리에 앉은 사람의 파트너를 찾아서 3번 자리로 데려오고… 이런 방식을 모든 커플이 서로의 파트너 옆에 앉을 때까지 반복합니다. 이 방법으로 최소 이동 횟수를 구할 수 있습니다.

처음에 i 번째 자리에 몇 번 사람이 앉아 있는지는 배열 row[i]에 저장되어 주어집니다. 그렇다면 row 배열을 처음부터 linear 하게 접근하면서, row[i]에 있는 사람의 파트너가 어디에 있는지 알 수 있다면, 한 번의 자리 맞교환으로 row[i]의 사람의 파트너를 옆에 앉힐 수 있겠죠. 커플들이 자신의 파트너 옆에만 앉으면 되고, 각 커플이 어느 자리에 앉아 있는지는 중요하지 않으므로 우리는 row[i]에 있는 사람의 파트너만 찾아서 row[i+1]에 앉혀주면 됩니다.

이렇게 i번째 앉아 있는 사람의 파트너를 뒤에서 찾아서 옆에 앉혀 준다면, 파트너를 찾는 과정이 O(n)이 걸리고, 총 O(n) iteration을 돌아야 하기 때문에 O(n²)이 나옵니다. 하지만 우리는 더 잘 할 수 있습니다.

그렇다면 어떻게 row[i]에 있는 사람의 파트너를 빠르게 찾을 수 있을까요? 이럴 때 사용할 수 있는 자료구조가 있습니다. 바로 hash table 입니다. hash table 은 data에 접근할 때, key에 hash function을 적용하여 O(1) 만에 데이터의 위치를 찾아 접근합니다.

출처: https://en.wikipedia.org/wiki/Hash_table

위 그림을 보면, ‘John Smith’라는 key에 hash function 을 거쳐 01번 장소에 있다는 것을 알 수 있습니다. ‘Lisa Smith’라는 key는 hash function 을 거쳐 02번 장소에 있다는 것을 알 수 있죠.

그런데 만약 ‘Sandra Dee’라는 key의 hash function의 결과가 ‘John Smith’와 겹친다면 어떻게 해야 할까요? 그 때는 여러 해결 방법이 있지만 간단한 방법을 설명하겠습니다.

각 key의 hash 값과 data를 바로 연결하는 것이 아니라, data의 list 혹은 data의 tree나, 혹은 또 다른 hash table과 연결하면 해결할 수 있습니다. 예를 들어 보겠습니다.

출처: https://en.wikipedia.org/wiki/Hash_table

위 그림을 보면, ‘John Smith’와 ‘Sandra Dee’의 hash 값이 겹칩니다. 하지만 문제가 되지 않습니다. hash 값이 data가 있는 장소를 가리키는 것이 아니라, data가 있는 list를 가리키게 하는 것이죠. 각 data는 해당 list에 들어가 있으므로, hash 값이 겹치더라도 덮어쓰지 않고 data를 저장할 수 있습니다. 최악의 경우, 모든 key의 hash 값이 동일해서 그냥 list와 같은 성능이 나올 수 있지만, 그 때는 hash function이 충분히 임의의 값을 반환할 수 있도록 잘 정의해야 합니다.

hash table을 직접 만드는 것은 겁나 어렵겠지만, 다행히도 hash table을 구현한 container는 거의 모든 언어에서 지원합니다. 이 풀이에서는 C++ STL의 unordered_map을 사용하겠습니다. unordered_map은 내부에 hash table을 구현하여 O(1)에 각 데이터에 접근할 수 있도록 해줍니다.

자세한 문제풀이는 아래 코드에 주석으로 대신하겠습니다.

이 때 time complexity는 커플이 총 n 팀이 있다고 했을 때, 각 커플마다 사람이 두 명이므로 2n명이 사람이 있고, 이 사람들을 모두 hash table에 넣는 시간이 2n이 나오게 됩니다. 또, row 원소 2n개를 2 칸씩 넘어서 iteration을 도므로 n 번의 iteration을 돌게 됩니다. 각 iteration 내부에서는 hash table과 배열에 접근하는 O(1)의 연산만이 존재하므로 iteration 내부는 O(1)이라 볼 수 있습니다. 그렇다면 총 합쳐서 O(2n + n) 으로 O(n)이 됩니다.

그런데 사실 이 경우, hash table을 쓰지 않아도 됩니다. 위 코드를 잘 보시면 원소의 수를 정확히 알고 있고, 각 원소의 값의 범위도 0~2n-1로 배열의 index를 벗어나지 않습니다. 그러므로 아래 코드처럼 hash table을 그냥 배열로 대체할 수 있습니다.

Union Find를 이용한 풀이

두 커플이 서로의 파트너가 바뀌어 있다면 몇 번 자리 맞교환을 해야 할까요? 한 번이면 됩니다. 서로의 상대의 파트너의 옆에 앉아 있으므로 한 번 바꾸면 서로의 파트너를 찾게 되죠. 세 커플이 각자 다 다른 파트너와 앉아 있다면 어떨까요? 일단 한 번으론 불가능합니다. 왜냐하면 A, B, C 커플이 서로 섞여 있다면, 이 중 두 명이 자리 맞교환을 하는 걸로는 한 커플만이 서로의 상대 옆에 앉을 수 있기 때문이죠. 이 경우 맞교환 후에 나머지 두 커플은 상대 커플의 파트너와 앉아 있게 됩니다. 위의 두 커플이 서로의 파트너와 앉아 있는 경우와 같아지는 거죠. 네 커플의 경우엔 한 번의 자리 맞교환으로 바로 위의 경우, 즉 세 커플이 서로 섞여있는 경우를 만들 수 있습니다. 즉, 최악의 경우 n 팀의 커플이 아무도 서로의 파트너 옆에 앉아 있지 않다면 n-1 번의 자리 맞교환이 필요한 것이죠.

만약 5 팀의 커플이 있는데, 0번 1번 커플은 서로 섞여 있고, 2번 3번 커플이 서로 섞여 있다면 2 번의 자리 맞교환이 필요합니다.

서로 자리가 섞여 있는 커플들을 하나의 집합으로 모으고 그 집합의 크기를 알 수 있다면 한 집합의 커플 크기를 a개 팀이라 했을 때, 그 팀이 모두 파트너 옆자리를 찾아가는 방법은 a-1 번의 자리 맞교환으로 가능합니다. 즉 자리가 섞여 있는 커플들의 집합을 찾고, 각 집합의 크기를 구한다면 총 필요한 맞교환 횟수를 구할 수 있습니다.

집합 연산이 필요하네요. 이럴 때 사용할 수 있는 자료구조가 Union Find 자료구조입니다.

Union Find 자료구조(Disjoint Set 자료구조 라고도 부릅니다.)는 서로소 집합 나타낼 때 유용하게 사용할 수 있는 자료구조입니다. 서로소 집합은 공통 원소가 없는 집합을 말합니다. 영어로는 Disjoint Sets 입니다. 위 문제에서는 한 사람이 동시에 여러 묶음에 속할 수 없기 때문에 아주 적합한 자료구조입니다.

Union Find 자료구조는 병합(Union)과 찾기(Find) 기능을 제공합니다. 병합은 서로 다른 두 집합을 합치는 연산이고, 찾기는 각 원소가 어느 집합에 속하는지 찾는 연산입니다.

아주 간단하게 배열을 이용해서 구현할 수 있습니다. 각 배열의 index를 원소의 key라고 생각하고, index의 value를 해당 원소의 집합의 key라고 생각합니다.

출처: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

위 그림은 원소가 8 개이고 각 집합의 원소는 1 개고 총 8 개의 집합이 있는 경우를 나타낸 그림입니다. 이 경우는 길이 8의 배열 parent[]를 정의하고 parent[i] = i 가 되도록 값을 세팅하면 나타낼 수 있습니다. parent[i]에는 원소 i의 집합 번호가 들어가게 되죠. 이렇게 하면 각 원소 i는 서로 다른 i 개의 집합에 속해 있게 됩니다.

출처: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

위 그림은 1, 2, 5, 6, 8 원소들이 한 집합에, 또 3, 4 원소가 한 집합에, 또 7 원소가 한 집합에 있는 경우입니다. 이 경우는 (1, 2, 5, 6, 8)을 1번 집합으로 묶어서 parent[1] = parent[2] = parent[5] = parent[6] = parent[8] = 1 이 되고, (3, 4)를 3번 집합으로 묶어서 parent[3] = parent[4] = 3, (7)을 7번 집합으로 parent[7] = 7 이렇게 세 집합으로 나눠서 정의할 수 있죠.

그렇다면 병합(Union)은 어떻게 할 수 있을까요? 만약 3번 원소가 속한 집합과 7번 원소가 속한 집합을 합치고 싶다면 parent[3]과 parent[7]의 값이 같도록 만들어 주면 됩니다. parent[3] = 3 이렇게 하면 되죠. 그러면 7번 원소의 부모가 3번 원소가 되면서 서로 같은 집합에 속해 있게 됩니다.

그렇다면 3번 원소가 어느 집합에 속해 있는지 찾고 싶다면(Find) 어떻게 해야 할까요? parent[3]을 봐서 3번 원소의 부모를 찾아가고 그 부모가 또 어느 집합에 속해있는지 찾으면 됩니다.

출처: https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

그런데 여기서 문제가 발생합니다. 위 그림처럼 병합의 순서에 따라서 최악의 경우 어떤 집합에 속해있는지 찾기 위해서 배열의 모든 원소를 순회해야 할 수도 있습니다. 1번 원소의 부모는 6번, 6번의 부모는 4번, 4번의 부모는 7번… 이렇게 말이죠.

이 문제는 경로 압축(path compression)과 Union by Rank를 통해 해결할 수 있습니다. 경로압축은 찾기(Find) 연산을 할 때, 기존 원소의 부모를 갱신해주는 것입니다. 위 그림으로 본다면, find(1)을 실행하여 1번 원소의 부모를 찾을 때 parent[1]에 최종 부모인 2를 저장합니다. 이는 parent[1] = find(parent[1])와 같이 간단하게 할 수 있습니다. Union by Rank는 항상 높이가 낮은 트리를 큰 트리의 루트에 붙이는 방법입니다.

구체적인 증명 과정은 너무 어려워서 생략하겠지만, 이렇게 했을 때 union과 find 연산의 big O notation은 모두 O(α(n))이 나옵니다. O 안의 α(n)함수는 inverse Ackermann function으로 모든 원격 실용적인 값으로 5보다 작습니다.

사용할 자료구조를 설명했는데요. Union Find 자료구조 구현은 아주 간단하게 구현할 수 있지만, 이 알고리즘에 적용하기에 약간 불편한 부분이 있습니다. 각 집합의 원소의 개수를 알아야 한다는 문제인데요. 이 문제는 생각을 조금 바꿔보면 해결할 수 있습니다.

총 n개의 커플이 있으니까 최악의 경우 n-1 번의 자리 맞교환이 필요합니다. 여기에 커플 집합 하나가 추가될 때마다 우리는 하나의 자리 맞교환을 save할 수 있습니다. 예를 들어서 (0, 1, 2, 4, 3, 5) 가 입력으로 들어왔을 때, (0, 1)을 한 집합으로, (2, 4, 3, 5)가 한 집합으로 묶이므로 3 - 2 = 1의 교환만 하면 됩니다.

즉 커플의 총 수 - 커플 집합의 수 = 최소 필요한 자리 맞교환의 수

가 됩니다.

자세한 문제풀이는 아래 코드에 주석으로 대신하겠습니다.

n 팀의 커플이 있는 경우 time complexity를 구해보겠습니다. iteration은 n번 돌게 되고, 각 iteration 내부에서는 union find의 union인 merge 함수를 실행하므로 iteration 전체는 O(nα(n)) 입니다. 또 마지막에 집합이 총 몇 개인지 hash table을 사용하는 STL인 unordered_set을 이용해서 세므로 O(n)이 걸립니다. 때문에 총 O((n+1)α(n)) 의 시간이 걸리게 됩니다.

마무리

제 풀이가 어설펐지만 즐거운 문제풀이가 되셨길 바랍니다. 더 좋은 풀이나 수정사항, 재밌는 접근법이 있다면 댓글로 공유해주세요.

감사합니다.

Get to know us better! Join our official channels below.

Telegram(EN) : t.me/Humanscape KakaoTalk(KR) : open.kakao.com/o/gqbUQEM Website : humanscape.io Medium : medium.com/humanscape-ico Facebook : www.facebook.com/humanscape Twitter : twitter.com/Humanscape_io Reddit : https://www.reddit.com/r/Humanscape_official Bitcointalk announcement : https://bit.ly/2rVsP4T Email : support@humanscape.io