1289. 원재의 메모리 복구하기 - 자바(JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV19AcoKI9sCFAZN 

SW Expert Academy

문제 해석

메모리 초기값은 000000으로 0으로 이루어진 값들로 이루어집니다.

3번째 값에 1을 채우면 해당 값이 끝까지 덮어씌워집니다.(ex 000111)

만약 왼쪽부터 2번째값에 1을 채우면 011111으로 덮어씌워집니다.

여기서 왼쪽에서 4번째 값에 0을 채우면 011000으로 덮어씌워집니다.

 

이때 모든 bit가 0인 상태에서 원래 상태로 돌아가는데 최소 몇 번이나 고쳐야 하는지 찾아보자.

 

입력

첫 번째 줄에는 테스트 케이스의 수 T가 주어진다.

두 번째 줄부터는 T개의 메모리 원래 값이 주어진다.

ex)

2

0011

100

 

제약조건

메모리 길이는 1 이상 50 이하이다.

 

출력

각 테스트 케이스마다 '#x'를 출력하고 x=1부터 시작

초기값에서 원래 값으로 복구하기 위한 최소 수정 횟수를 출력한다.

ex)

#1 1

#2 2

 

문제 풀이 전 설계

메모리 주소를 원래대로 복 구하기 위해서 좌측부터 검사하여 만약 해당 값이 1이라면 count를 증가합니다.

또한 그 뒤에 값이 자동적으로 1로 변환됩니다.

만약 해당 값이 0이라면 초기값이 0이기 때문에 count를 증가할 필요가 없습니다.

 

만약 맨 좌측 값이 1이어서 뒤에 값도 모두 1로 바뀌었다면 이제는 상황이 뒤집힙니다.

다음 값이 1이라면 count를 증가할 필요가 없습니다.

반면에 다음값이 0이라면 count를 증가시키면서 뒤에 값을 모두 0으로 변환시킵니다.

 

이렇게 어떤 값을 마지막으로 덮어쓰었냐에 따라서 상황이 뒤집힙니다.

따라서 temp라는 변수를 사용하여 초기에 0을 설정합니다.

그리고 temp와 다른 값 = 1 을 만나게 되면 count를 증가시키면서 temp 에 다른값 = 1을 넣어주게 된다면 

temp변수에 1이 들어가 있더라도 temp와 다른값 = 0 이 만나게 되면 count를 증가시키며 temp에 다른값 = 0이 설정되면서 최소 수정 횟수를 구할 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= n; i++) {

			char[] memory = br.readLine().toCharArray();									
			char temp = '0';
			int count = 0;
			
			for (char c : memory) {				
				if(c == temp) {
					continue;					
				}
				count++;
				temp = c;
			}			
			sb.append("#"+ i + " " +  count + "\n");						
		}
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

}

테스트 케이스 '#i'를 출력하기 위해 반복문을 1부터 시작하였습니다.

출력을 효율성을 위해 Stringbuilder를 사용하여 출력하기 위한 문자들을 쌓아놓고 마지막에 한 번에 출력합니다.