03_문자열 뒤집기 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 happenundo.tistory.com
문자열뒤집기
1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 입력받는 문자열 s의 길이가 100만보다 작은데 시간 제한은 2초였다. 2초라면 파이썬의 경우 약 4,000만 번의 계산이 가능한 시간이므로 O(NlogN)의 시간까지도 가능하다고 생각했다. 물론 O(N)도 가능하다. 그러므로 그냥 반복문을 통해 문자열을 돌면서 뒤집는 횟수의 최솟값을 구하면 된다고 생각했다. 그래서 단순히 생각해서 1을 뒤집는 경우와 0을 뒤집는 경우 모두 for문을 돌려서 두 결과값 중 작은 값이 답이 된다. for문을 2번 돌리는 것이라서 ..
