2027. Minimum Moves to Convert String

https://leetcode.com/problems/minimum-moves-to-convert-string

난이도 : easy

문제

모든 문자가 O로 바뀌는 최소 이동 횟수를 반환하라.

 

이 문제는  입력으로 들어오는 문자열에서 X 가 있는 경우 O로 바꾸는 작업의 최소 비용을 구하는 문제이다.

OXOX 문자열이 있다면 문제에서 주어진 제약 사항 중에서 한번에 3 개의 문자열을 바꿀 수 있다는 제약사항이 있다. OXOX는 OXOX XOX 문자열을 1회 변경하면 최소 값을 구할 수 있다. 또한 제약사항에 입력으로 들어오는 문자열의 길이는 3 <= s.length <= 1000 임으로 bruth-force 로 접근해서 풀이가 가능하다.

시간 복잡도는 최대 O(1000) -> O(n)의 연산으로 해당 문제를 풀이 가능하다.

 

소스코드

필자가 풀이 한 코드는 아래와 같다.

class Solution {
public:
    int minimumMoves(string s) {

        int sol = 0;
        for(int i = 0; i < s.size(); i ++) {
            if (s[i] == 'X') {
                s[i] = 'O';
                
                if (i + 1 < s.size())
                    s[i+1] = 'O';
                if (i + 2 < s.size())
                    s[i+2] = 'O';
                
                sol++;
            }
        }
        return sol;
    }
};

 

Most Votes 코드를 몇 개 확인해 보았다.

아래 코드는 문자열 변환 없이 X를 만나면  count를 증가하고  i 값을 3을 증가시키는 코드이다. 간결하고 이해하기 쉽게 작성되어 있다.

int minimumMoves(string s) {
	int i = 0, n = s.length(), count = 0;
	while (i < n) {
		if (s[i] == 'O')  // If we find 'O' we simply move the pointer one step
			i++;
		else
			count++, i += 3;  // When we find 'X' we increment the count and move the pointer by 3 steps
	}
	return count;
}

 

또 다른 코드를 확인해 보았다. 위 코드랑 비슷하다. ㅎㅎ 두 코드의 장점은 문자열을 치환 하지 않고도 처리하는 방식에서 깔끔함을 느꼈다.

class Solution {
public:
  int minimumMoves(string s) {
    int i = 0, ans = 0, n = s.size();
    
    while(i < s.size())
      if(s[i] == 'O') i++;
      else i += 3, ans++; 
      
    return ans;
  }
};