leetcode: Couples Holding Hands

커플 (2N-2, 2N-1)가 인접해서 앉고 싶은데, 그렇지 못하다면 최소로 swap하여 인접하게 앉을 수 있도록 하는 문제이다.

 

커플은 (2N-2, 2N-1)으로 (0,1), (2,3), (4,5), ...이므로 x의 파트너는 x가 짝수인 경우 x+1, 홀수인 경우 x-1이다.

먼저 array를 0부터 2자리씩 보기 시작하면서 해당 파트너와 인접하면 넘어가고,

인접하지 않으면 짝은 옆으로 데려와서 앉힌다.

 

즉, 소파에 첫번째 앉아있는 사람은 고정시키고 두번째 사람만 옮김으로써 커플을 완성하도록 한다. 

시간복잡도는 O(N^2)이고 코드는 아래와 같다.

class Solution {
	public int minSwapsCouples(int[] row) {
		int ans = 0;

		for (int i = 0; i < row.length; i += 2) {
			int x = row[i];

			if (row[i + 1] == findPartner(x)) {
				continue;
			}

			ans++;

			for (int j = i + 1; j < row.length; ++j) {
				if (row[j] == findPartner(x)) {
					row[j] = row[i + 1];
					row[i + 1] = findPartner(x);
					break;
				}
			}
		}
		return ans;
	}

	public int findPartner(int x) {
		if (x % 2 == 0) {
			return x + 1;
		}
		return x - 1;
	}
}