알고리즘-그리디-문자열 뒤집기

알고리즘-그리디-문자열 뒤집기

 

문제 : 문자열 S에 있는 모든 숫자를 전부 같게 만드려고한다. 

이때 연속된 숫자는 횟수 한번으로 뒤집을 수 있다.

문자열 S가 주어졌을 때 의 최소 횟수를 구하시오.

 

S의 범위는 100만보다 작다 , S는 0과 1로만 주어진다.

 

ex) 0001100  은 11을 00으로 바꾸는 1회만 이용하면 0000000으로 같게 만들수있다.

ex) 0100101 은 1을 0으로 바꾸는 3번만 이용하면 0000000으로 같게 만들 수 있다. 전부 1로 만드는것도 3회다.

 

 

 

해결방안

1. 문자열 S는 100만보다 작다. O(N)

2. 최소횟수를 구해야한다. 범위가 크므로 앞에서부터 찾되 for문을 한번만 사용해야할것같다.

3. 0으로 뒤집는 횟수를 세는 변수와 1로 뒤집는 횟수를 세는 변수를 만든다.

4. 같은 숫자가 연속되면 하나의 횟수로 치기 때문에 다음자리 숫자까지 비교할 필요성이있다.

5. 첫 숫자는 따로 처리한 후 for문을 통해 앞에서부터 찾으면서 앞과 뒤에 숫자가 다를때에만 0이냐 1이냐에따라 횟수를 추가시켜준다.

 

6. 앞과 뒷 숫자가 똑같으면 이미 처리를 했음으로 볼 필요가없고 숫자가 바뀔때만 count를 해주는것이 핵심인것같다.

 

 

 

코드

 

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String st = bf.readLine();
int count1 = 0;
int count0 =0;

if ( st.charAt(0) == '0') {
    count0 +=1;
}
else {
    count1 +=1;
}


for( int i=0 ; i<st.length()-1; i++) {
    if ( st.charAt(i) != st.charAt(i+1)) {
        if ( st.charAt(i+1) =='1') {
            count1 +=1;
        }
        else {
            count0 +=1;
        }
    }
}
System.out.println(Math.min(count0,count1));