[LeetCode] 1536 - Minimum Swaps to Arrange a Binary Grid

문제

• 링크: https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers
• 난이도: Medium
• 태그: 배열, 그리디
• 결과: Time: 0 ms (100%), Space: 30 MB (41.46%)

풀이

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> v(n);
        for(int i = 0; i < n; ++i)
        {
            for (int j = n - 1; j >= 0; --j)
            {
                if(grid[i][j] == 1)
                {
                    v[i] = j;
                    break;
                }
            }
        }

        int cnt = 0;
        for(int i = 0; i < n; ++i)
        {
            bool found = false;
            for(int j = i; j < n; ++j)
            {
                if (v[j] > i)
                {
                    continue;
                }

                found = true;
                for(int k = j; k > i; --k)
                {
                    cnt++;
                    swap(v[k], v[k -1]);
                }

                break;
            }

            if(!found)
            {
                return -1;
            }
        }

        return cnt;
    }
};

나에겐 꽤나 어려웠다. 자료구조를 잘 써야하는 문제라기 보다는 논리적인 생각이 중요한 문제였는데, 잘 떠오르지 않았다. Hint와 Leet를 통해 도움을 받아서 AC를 받았다.

먼저, i행에 대해 마지막으로 1이 나오는 인덱스를 v[i]에 저장한다 ¹.

만약 i행에 대해 v[j] <= i를 만족하는 j²가 존재하지 않는다면 답을 찾을 수 없는 경우이다. 이는 행들을 어떻게 배치해도 i행에서 main diagonal 위 영역을 침범하게 된다는 뜻이기 때문이다.

반대로 v[j] <= i를 만족하는 가장 가까운 j를 찾았다면, 직접 swap해가며 시뮬레이션 하면 된다(최소 횟수를 구해야하므로 가장 가까운 j를 찾음). 이 경우, i - j번의 swap이 필요함을 알 수 있다. for문 조건을 보면, k는 $i\lt k \leq j$ 범위를 가지므로 i - j번의 swap을 하는 코드가 된다. j행에서 차근차근 swap해나가면서 i행으로 가져오면 된다.

배운 점과 후기

main diagonal의 윗부분이라는 조건을 통해, 행이 내려갈 수록 요구되는 v[i]값은 작아지게 된다는 점이 흥미롭다. 조건을 통해 어떠한 제약이 생기는지 관찰하는게 중요하겠다는 생각이 든다.

---

1. 코드 상에서 std::vector를 저런식으로 초기화하면 초기값이 0이 되므로 1이 포함되지 않는 경우도 0번째에 1이 있는 경우와 같아진다. 다만 1이 0번째 인덱스에 있는 경우는 1이 없는 경우와 마찬가지도 어느 곳이든 배치될 수 있기 때문에 해당 케이스는 의도적으로 고려하지 않고 편하게 초기화했다. ↩

2. 단, $i\leq j\lt n$ ↩