[백준] 알고리즘 분류(문자열,JAVA)1439번, 뒤집기

문제 링크

1439번: 뒤집기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 0과 1로 이루어진 문자열이 주어진다.

2. 연속된 숫자를 0 -> 1, 1->0으로 변경하는 행동을 할 수 있습니다.

3. 문자열이 모두 같은 숫자가 되게하는 최소 행동 횟수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 문자열을 저장합니다.

 

2. 문자열을 탐색하여 연속되는 0과 1의 개수를 구합니다.

 

3. 연속하는 0과 1의 개수가 작은 값이 행동하는 것이 최소 행동임으로 더 작은 값을 결과로 출력합니다.

 

예제입력 1.

 

 

1. 입력되는 문자열을 저장합니다.

 

00011000

 

2. 문자열을 탐색하여 연속되는 0과 1의 개수를 구합니다.

 

문자열에서 0과 1이 연속되는 지점들을 나눕니다.

[000][11][000]

 

연속되는 0의 개수 : 2

 

연속되는 1의 개수 : 1

 

 

3. 연속하는 0과 1의 개수가 작은 값이 행동하는 것이 최소 행동임으로 더 작은 값을 결과로 출력합니다.

 

0을 뒤집으면 2번

[111][11][111] = 11111111으로 변경됩니다.

 

1을 뒤집으면 1번

[000][00][000] = 00000000으로 변경됩니다.

 

최소 행동 횟수 1번을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 이전 숫자를 문자열의 첫 번째 글자로 설정합니다.
• 두 번째 글자부터 이전 글자를 이용하여 0과 1이 연속되는 개수를 구합니다.
• 0과 1중에 연속되는 개수가 더 작은 값을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;
public class Main{
    static public void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = br.readLine();
        int one = 0;		//연속되는 0의 횟수 저장 변수
        int zero = 0;		//연속되는 1의 횟수 저장 변수
        char previousNum = input.charAt(0);	//이전 숫자
        //문자열을 탐색하여 0과 1이 연속되는 개수를 구하기
        for(int i=1;i<input.length();i++){
            char cur = input.charAt(i);
            //이전 숫자와 다르면 연속이 중단으로 판정
            if(cur != previousNum){	
                previousNum = cur;	//이전 숫자 변경
                if(cur == '0')	//현재 숫자가 0이면 이전 숫자는 1
                    one++;
                else		//현재 숫자가 1이면 이전 숫자는 0
                    zero++;
            }
        }
        //마지막 연속된 숫자도 확인!
        if(previousNum == '1')
            one++;
        else
            zero++;
        //연속되는 개수가 더 작은 값을 BufferedWriter 저장
        bw.write(Math.min(one, zero) + "");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}