백준 1439번 뒤집기 [JAVA]

문제:

 

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

예를 들어 S=0001100 일 때,

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

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

 

 

입력:

 

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

 

출력:

 

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

 

 

 

알고리즘 설계:

 

일단 처음 문제를 읽었을때 뭘 하라는건지 파악을 못했다

그래서 처음엔 뻘짓좀 했다

 

중요한건 이거다 

 

1. 모든 문자열은 0과 1로 이루어져 있다는것

2. 모든 숫자를 전부 같게 만들려고 한다는 것

3. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다

 

 

예를 들어 11010111001 이라는 문자열을 입력했다고 하자

 

그러면 11/0/1/0/111/00/1 크게 이렇게 part를 구분한다

1->0으로 바뀔때 숫자1로 구성된 part를 증가 시켜주고

0->1로 바뀔때  숫자로0으로 구성된 prart를 증가 시켜주면 된다

 

그런데 여기서 주의할점은 마지막 part는 따로 계산해줘야 된다는것이다

00->1로 바뀔때 숫자 0으로 구성돤 part는 증가하지만 마지막 part인 1은 count되지 않았다

 

따라서 따로 for문으로 구성해서 마지막 숫자로 구성된 part까지 count해주면 

 

0으로 구성된 part와 1로 구성된 part 수를 구할 수 있다

 

최소 횟수로 1111111111이나 0000000000으로 바꿀려면 

part가 적은 숫자를 뒤집어 주는것이 좋다

 

그래서 마지막에 zero와 one중에 최솟값을 선택하는것이다 

 

import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int zero=0; //0이 연속된 횟수
		int one=0; //1이 연속된 횟수	
		String s=scan.next(); //문자열 S입력

		for(int i=0;i<s.length()-1;i++) {
			if(s.charAt(i)!=s.charAt(i+1) && s.charAt(i)=='0')
				zero++;  //0에서 1로 넘어갈때 0인 part +1해준다
			else if(s.charAt(i)!=s.charAt(i+1) && s.charAt(i)=='1')
				one++;   //1에서 0으로 넘어갈때 1인 part +1해준다
		}

	    //마지막 part는 위의 for문에서 계산이 안되기 때문에 따로 구해줘야 한다
		if(s.charAt(s.length()-1)=='0') {
			zero++; 
		}
		else 
			one++;

		//0과 1중에 part개수가 적은 숫자를 뒤집는게 최솟값을 구하는 방법이다 
		System.out.println(Math.min(zero, one));

	}
}

 

 

 

위의 코드 보다 비효율적이지만 정답인 코드 하나 더 올리겠다 이건 string을 쓸때 없이 배열에 담았다...

 

import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int zero=0; //0이 연속된 횟수
		int one=0; //1이 연속된 횟수	
		String s=scan.next(); //문자열 S입력
		char[] str=new char[s.length()];
		for(int i=0;i<str.length;i++) {
			str[i]=s.charAt(i); //입력한 문자를 배열에 담는다 
		}

		for(int i=0;i<str.length-1;i++) {
			if(str[i]!=str[i+1] && str[i]=='0')
				zero++;  //0에서 1로 넘어갈때 0인 part +1
			else if(str[i]!=str[i+1] && str[i]=='1')
				one++;   //1에서 0으로 넘어갈때 1인 part +1

		}

	    //마지막 part는 위의 for문에서 계산이 안되기 때문에 따로 구해줘야 한다
		if(str[str.length-1]=='0') {
			zero++; 
		}
		else 
			one++;

		//0과 1중에 part개수가 적은 숫자를 뒤집는게 최솟값을 구하는 방법이다 
		System.out.println(Math.min(zero, one));

	}
}

 

솔직히 쉽지않았는데 정답률이 50퍼가 넘는다.. 더 열심히 해야겠다