LeetCode (C/C++) 2380. Time Needed to Rearrange a Binary String

https://leetcode.com/problems/time-needed-to-rearrange-a-binary-string/

 

---

풀이

문제에서 요구한 방식대로 코드를 구현하였다.문자열을 순회하며 "01"을 찾으면 "10"으로 바꾸는 과정을 더 이상 "01"이 없을 때까지 반복하였다.

DP로 푸는 방식도 있었지만 잘 이해가 되지 않아 코드만 올려두었다.

---

코드

class Solution {
 public:
    int secondsToRemoveOccurrences(string s) {
        int cnt = 0;
        while (1) {
            bool isChanged = false;
            int i = 0;
            while (i < s.size()) {
            
            	// "01" 이라면 "10"으로 바꾸고 idx + 2
                if (s[i] == '0' && s[i + 1] == '1') {
                    s[i] = '1', s[i + 1] = '0';
                    isChanged = true;
                    i += 2;
                }
                
                // 아니라면 바로 다음 원소 탐색
                else
                    i++;
            }
            
            // 문자열을 끝까지 순회했을 때 변경된 부분이 없다면 현재까지의 반복 회수 반환
            if (!isChanged)
                return cnt;
            cnt++;
        }
        return cnt;
    }
};

 

코드 2 - DP 풀이

class Solution {
 public:
  int secondsToRemoveOccurrences(string s) {
    int ans = 0;
    int zeros = 0;

    for (const char c : s)
      if (c == '0')
        ++zeros;
      else if (zeros > 0)  // c == '1'
        ans = max(ans + 1, zeros);

    return ans;
  }
};