(BJ_1439) 뒤집기

알고리즘이 잘 풀리지 않을 때 1) '변수를 적극 활용하자'는 것과 2) '코드를 따라가며 시뮬레이션을 하자'고 생각한다.

1) 변수활용: 개인적으로는 기존에 입력한 코드에 갇혀서 사고의 틀이 제한되기 때문에 습관적으로 변수 활용을 생각한다.

2) 시뮬레이션: 코드 작성 전에 떠오른 대로 코드가 맞을 것이라고 생각하지만.. 항상 오류가 발생한다. 그 때 내가 작성한 코드의 결함을 발견하기 위해서는 테스트 케이스를 한 개 정하고 코드 수행에 따른 단계적 결과를 확인해본다.

 

이 두 가지는 너무 당연한 과정이지만 마음만 조급해져서 자꾸 놓치고, 결국에는 한참 뒤에야 다시 밟게되는 과정이었다. 앞으로는 코드 작성 초반부터 습관을 들여야겠다. 

 

0. 문제

백준 1439

1. 내가 작성한 코드

package algorithm.BAEKJOON;

import java.util.Scanner;

public class AG_BJ_1439 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		char[] arr = sc.next().toCharArray();

		int[] iArr = new int[arr.length];

		for (int i = 0; i < iArr.length; i++) {
			iArr[i] = (int) arr[i];
		}

		int initial = iArr[0]; // 배열 첫 값 초기화
		int tmp = iArr[0]; // 값 변경 시 저장할 변수
		int cnt = 0; // 뒤집기 횟수 저장

		for (int i = 0; i < iArr.length; i++) {
			if (initial != iArr[i]) { 
            		// 초기값과 다르고
				if (tmp != iArr[i]) { 
                		// 최근값과 다르면
					cnt++; 
                    			// 뒤집고
					tmp = iArr[i]; 
                    			// 새로 최근값 저장
				}
			}
			if (initial == iArr[i]) { 
            		// 초기값과 같지만
				if (tmp != iArr[i]) { 
                		// 최근값과는 다르다면
					tmp = iArr[i]; 
                    			// 최근 값만 새로 저장 (비교를 위해 저장하고 뒤집지는 않는다)
				}
			}
		}
		System.out.println(cnt);
		sc.close();
	}
}

값이 바뀔 때마다 세는 방법을 시도하다가 뭔가 맞지 않는 것 같아 초기값과 최근값을 저장하고 갱신해가면서 카운트를 하는 방법을 활용했다..........왜 왜... 더 나아가지 못하고 방향을 틀었을까...

 

초기값과 최근값 두 개의 변수를 활용하면 가능한 경우의 수가 4가지 나온다.

최근값은 최초에는 초기값과 동일하게 선언한다.

1) 초기값과 동일 && 최근값과 동일 -> 유지

2) 초기값과 다름 && 최근값과 다름 -> 뒤집기 +1 최근값(temp) 갱신

3) 초기값과 다름 && 최근값과 동일 -> 유지

4) 초기값과 동일 && 최근값과 다름 -> 최근값(temp) 갱신

 

정말 어렵게 풀었지만 그래도 고민한 시간이 가치 있었다고 생각한다...(?)

 

2. 효율적 코드1

package algorithm.BAEKJOON;

import java.util.Scanner;

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

		Scanner sc = new Scanner(System.in);
		String str = sc.next();

		int l = str.length();

		char[] sub = new char[l];

		for (int i = 0; i < l; i++) {
			sub[i] = str.charAt(i);
		}

		int cnt = 0;
		for (int i = 0; i < l - 1; i++) {
			if (sub[i] != sub[i + 1]) {
				cnt++;
			}
		}
		System.out.print((sub[0] != sub[l - 1]) ? (cnt + 1) / 2 : cnt / 2);
	}
}

기준되는 수가 전과 비교해 바뀔 때마다 카운트 하는 방식이다. 단, 카운트 하는 횟수가 홀수인 경우 최종 카운트 값에 1을 더하고 2로 나누어준다.

 

예시 1) 1000011

1->0으로 바뀔 때 카운트 +1

0->1로 바뀔 때 카운트 +1

총 2번 바뀌었으나 0이 연속된 구간만 바뀌면 되니 /2 해서 답은 1이다.

 

예시 2) 1001000

1->0으로 바뀔 때 카운트 +1

0->1으로 바뀔 때 카운트 +1

1->0으로 바뀔 때 카운트 +1

총 3번 바뀌었고 1 구간이나 0구간 2번만 뒤집으면 된다. 

하지만 위의 공식대로 3/2로 하면 정수의 나눗셈으로 결과값이 1이 된다.

이 경우 최종 카운트 값에 1을 더한 후 2로 나누어 결과를 도출한다.

 

이처럼 첫 값과 맨 마지막 값이 같지 않을 경우 짝이 맞지 않을 때의 예외처리를 코드로 구현해줘야 한다.

 

3. 효율적 코드2

package algorithm.BAEKJOON;

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

public class AG_BJ_1439_3 {

	static String str;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		str = br.readLine();
		int totalBunch = 1; // 전체 묶음 개수
		boolean oneSideChk = true; 
        	// 처음으로 달라진수 묶음 체크
		int oneSideNum = 0; 
        	// 처음으로 달라진 수 묶음 개수
		String str_f = str.substring(0, 1);
		for (int i = 1; i < str.length(); i++) {
			String str_s = str.substring(i, i + 1);
			if (!str_f.equals(str_s)) {
				totalBunch++;
				if (oneSideChk) {
					oneSideNum++;
				}
				oneSideChk = !oneSideChk; 
                // 두개 pass의 한번 씩은 false로 바꿔서 카운팅 되지 않도록 함
			}
			str_f = str_s;
		}

		if (totalBunch == 1) {
			System.out.println(0);
		} else {
			System.out.println(Math.min(oneSideNum, totalBunch - oneSideNum));
		}
	}
}

맞힌 제출내역을 확인하다 발견한 코드인데 메모리 사용과 수행 시간이 비교적 적었던 코드이다. 일단 2번째 코드와 동일하게 뒤집힌 경우를 카운트하고 있는데 flag를 활용해서 단순히 /2가 아니라 코드 내에서 카운트하는 횟수를 제한했다. pass를 한번씩 돌면서 true와 false로 번갈아가며 적용된다. 

 

예시 1) 1000011

1->0으로 바뀔 때  true이므로 카운트 +1

0->1로 바뀔 때 false이므로 카운트 유지

총 숫자 묶음은 3개이고, 총 숫자 묶음에서 카운트 횟수를 뺀 값(2)과 카운트 횟수 값(1) 두개 중 작은 값인 후자를 결과로 산출했다. 

 

예시 2) 100101

1->0으로 바뀔 때 true이므로 카운트 +1

0->1으로 바뀔 때 false이므로 카운트 유지

1->0으로 바뀔 때 true이므로 카운트 +1

0->1으로 바뀔 때 false이므로 카운트 유지

총 숫자 묶음은 5개이고, 총 숫자 묶음에서 카운트 횟수를 뺀 값(3)과 카운트 횟수 값(2) 두개 중 작은 값인 후자를 결과로 산출했다. 

 

그런데 전자 값은 왜 산출해서 그 중 최소값을 굳이 구하는지는 좀 더 고민해봐야 할 것 같다...왜지..