765. Couples Holding Hands

[zeikar]

Problem link

https://leetcode.com/problems/couples-holding-hands/

Problem Summary

커플이 2n개의 좌석을 서로 붙어 있게 앉기 위한 최소의 스왑 횟수를 구하는 문제.

Solution

그리디하게 생각하면 의외로 쉽게 풀린다.

일단 앞에서 순차로 탐색한다고 해보면 짝이 안 맞는 사람이 있을 경우 뒤쪽에서 한 명이랑 스왑을 해줘야 한다. 그리고 이렇게 스왑을 한 경우 이 커플은 더 이상 스왑을 해줄 필요가 없어진다.
이렇게 순차적으로 커플이 되도록 스왑을 쭉 돌려주면 되는 문제.

Source Code

from typing import List


class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        pos = [0] * len(row)

        for i in range(len(row)):
            pos[row[i]] = i

        ans = 0
        for i in range(0, len(row), 2):
            partner = row[i] % 2 == 0 and row[i] + 1 or row[i] - 1

            if pos[partner] != i + 1:
                ans += 1
                row[i + 1], row[pos[partner]] = row[pos[partner]], row[i + 1]
                pos[row[pos[partner]]] = pos[partner]

        return ans