[이것이 코딩 테스트다 with Java] 그리디 예제 - 문자열 뒤집기

문자열 뒤집기

난이도 ●○○ | 풀이 시간 20분 | 시간 제한 2초 | 메모리 제한 128MB | 기출 핵심 유형

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하시오.

 

입력 조건

• 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력 조건

• 첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

입력/출력 예시

입력 예시	출력 예시
0001100	1

요점

• 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 횟수를 가지는 경우를 계산한다.

소스 코드

import java.util.*;

public class Main
{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		String numStr = scan.next();
		int count[] = {0, 0};
		
		count[numStr.charAt(0) - '0']++;
		
		for(int i = 1; i < numStr.length(); i++){
			if(numStr.charAt(i)!= numStr.charAt(i-1)) count[numStr.charAt(i) - '0']++;
		}
		
		System.out.println("result = " + Math.min(count[0], count[1]));
	}
}

 

문제 풀이 후기

코딩 테스트는 풀이 능력도 중요하지만 문제 이해 능력도 매우 중요한 것 같다. 대충 읽어서는 뭔 소리인지 모르겠는 문제들은 주늑이 들 때가 있는데 다시 잘 읽어보면 이해도 되고 생각보다 쉬운 경우가 꽤 많은 것 같다. 다 읽어보기 전까지 기죽지 않기!

 

GitHub: https://github.com/Leeyeonjae/coding-test/blob/main/11_Greedy_Example/11_3_replaceString.java

참고서적 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈