[SWEA] 1289번 - 원재의 메모리 복구하기 문제

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

0으로 초기화된 상태에서 최소 횟수로 입력값을 만드는 문제이다.

만약 한 위치에 1을 넣으면 거기서부터 끝까지 다 1로 덮어씌워지기 때문에

왼쪽에서 오른쪽으로 가면서 수를 넣으면 된다.

예를들어 0000에서 0010을 만들고자 한다면

세번째 위치에 1를 넣고 (0011) 네번째 위치에 0을 넣는다.(0010 완성) 2번이 최소횟수가 됨!

훑어가다가 0->1이 되거나, 1->0으로 바뀌는 지점이 관건이 된다.

따라서 이전값을 저장해두고 동일하면 넘어가고, 다른값이 나왔다면 그 값을 새로 저장하고 카운트해주는 식으로 풀었다.

 

풀이코드

package D3;

import java.io.*;
import java.util.StringTokenizer;

public class SW_1289 {  //SWEA 원재의 메모리 복구하기 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            String input = br.readLine();    //0,1로 이루어진 입력값, 길이 재려고 string형으로 받음
            char prevBit = '0';   //이전값(0인지 1인지), 만약 input이 전부 0이면 카운트도 0이됨
            int count = 0;  //바뀌는 구간들을 세어준다
            for (int j = 0; j < input.length(); j++) {  //최대 input길이만큼 반복해서 확인
                if (input.charAt(j) != prevBit) {   //j번째 문자가 이전과 달라질경우 카운트해준다(0->1, 1->0)
                    count++;
                    prevBit = input.charAt(j);
                }
            }
            bw.write("#" + (i+1) + " " + count);
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}