SWEA 1289. 원재의 메모리복구하기

---

문제

원재가 컴퓨터를 만지다가 실수를 저지르고 말았다. 메모리가 초기화된 것이다.

다행히 원래 메모리가 무슨 값이었는지 알고 있었던 원재는 바로 원래 값으로 되돌리려고 했으나 메모리 값을 바꿀 때 또 문제가 생겼다.

메모리 bit중 하나를 골라 0인지 1인지 결정하면 해당 값이 메모리의 끝까지 덮어씌우는 것이다.

예를 들어 지금 메모리 값이 0100이고, 3번째 bit를 골라 1로 설정하면 0111이 된다.

원래 상태가 주어질 때 초기화 상태 (모든 bit가 0) 에서 원래 상태로 돌아가는데 최소 몇 번이나 고쳐야 하는지 계산해보자

---

문제해석

언제나 메모리의 모든 숫자는 0부터 시작된다.
뒤에서부터 N번째 숫자를 세는데 선택한 숫자까지 모든 숫자가 1또는 0으로 바뀐다.

그럼 예시로 0011 입력이 주어지면 0000 -> 0011끝
1출력

다른 예시로 100 입력 000 -> 111 -> 100 끝
2출력

---

입력과 출력

[입력]

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

각 테스트 케이스는 한 줄로 이루어져 있으며, 메모리의 원래 값이 주어진다.

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

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

초기값(모든bit가 0)에서 원래 값으로 복구하기 위한 최소 수정 횟수를 출력한다.

---

설계방식

1. 문자열을 입력받고 길이가 똑같은 char배열을 만든다.
2. 배열에 모두 0을 집어넣고 입력받은 문자열과 반복문과 charAt을 통해 비교한다.
3. 만약 다르다면 해당 문자를 복사하고 문자배열의 인덱스~끝까지 해당 문자로 대체한다. 그리고 바뀔 때 마다 카운트를 세준다
4. 반복문이 끝나면 입력값과 동일한 문자를 찾을 수 있으며 카운트를 출력하면 된다.

---

코드풀이

public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine()); //테스트케이스 입력
		for (int t = 1; t <= tc; t++) { //테스트 케이스 만큼 반복
			
			String recover = br.readLine(); //복구하고싶은 메모리 입력 예시)001101
			char[] memory = new char[recover.length()]; //입력받은 문자열의 길이만큼 char배열 선언
			
			for (int i = 0; i < memory.length; i++) {
				memory[i] = '0'; //배열 속 모든 칸에 '0' 입력(초기상태)
			}
			
			int cnt = 0; //정답이 될 카운트 변수 선언
			for (int i = 0; i < memory.length; i++) { //배열의 길이만큼 반복
				if (memory[i] != recover.charAt(i)) { //만약에 복구하고 싶은 메모리의 i번째 문자가 현재 복구하고있는 문자와 다를경우
					char fill = recover.charAt(i); //해당 문자를 char변수 fill에 저장합니다.
					
					for (int j = i; j < memory.length; j++) { // 그리고 i번부터~ 끝까지 fill을 집어넣으면 숫자가 반전되는 효과와 동일합니다.
						memory[j] = fill; 
					}
					cnt++; //그리고 최종적으로 몇 번 뒤집었는지 알아야하니 cnt ++후위연산자를 통해 횟수를 셉니다. 
				}
			}
		System.out.println("#" + t +" "+cnt); //마지막에 최종횟수 출력
		}
	}
}