(JAVA) 백준 1439번 : 뒤집기

 

 

https://www.acmicpc.net/problem/1439

1439번: 뒤집기

 

 

 

쉬운 문제.

 

 

 

핵심은

 

  1.  연속된 같은 숫자들이 있으면 하나로 생각

  

  2.  0 과 1 중 연속된 같은 숫자들의 종류 개수가 작은 것이 정답

 

 

ex)

0011100 일 때,

 

            00 / 111 / 00

-> 종류   0 /   1  /  0

 

-> 개수 : 0 - 2개, 1 - 1개 이므로 1번만 뒤집으면 모든 숫자를 같게 할 수 있음.

 

*** 참고로, 종류 개수 셀 때 맨 마지막 문자까지 세야 하므로 for문 종료 후 맨 마지막 문자를 보고 알맞게 count 해준다.

 

 

 

매커니즘

---

1)  첫 input(입력) 받을 때 for문 실행

 

2)  문자 하나씩 index 순회하며 진행. 이 때, 첫 번째 문자를 별도의 변수에 저장하고 두 번째부터 순회한다.

*** 무조건 1개 이상의 문자가 입력으로 들어오기 때문

 

3)  2)번 진행 시

      - 현재 index의 문자가 이전 문자와 다르면 -> 이전 문자 count, 현재 진행 문자를 별도의 변수에 저장

      - 현재 index의 문자가 이전 문자와 같으면 -> 다음 문자 탐색

 

 

 

 

 

감사합니다.

 

 

소스코드

---

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	// 뒤집기 문제
	// 쉬움
	public class p1439 {
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String str = br.readLine();
	char[] chars = str.toCharArray();
	int n = chars.length;
	int ascii = 48;
	int[] count = new int[2]; // 0: zeroCount, 1: oneCount
	char lastCh = chars[0]; // 임시 시작 문자 -> 안쓰는 9로 설정
	for(int i = 1; i < n; i++) {
	if(lastCh != chars[i]) {
	count[lastCh - ascii]++;
	lastCh = chars[i];
	}
	}
	// 연속된 문자의 끝을 파악해서 count + 1 해야 함
	count[lastCh - ascii]++;
	System.out.println(Math.min(count[0], count[1]));
	}
	}

view raw p1439.java hosted with ❤ by GitHub