BOJ 1439 뒤집기

1. 변수

   int count // 바꾼 횟수 저장할 변수
   

2. 구현로직

   1. greedy는 방법만 찾으면 쉽다고 한다

   2. 01일땐 1번만 바꾸면 돼

      010일때는 1번

      0101일때는 2번

      0101000001 3번

      즉, 0->1로 바뀔때 바뀌는 횟수 count해주면 돼

      (*) 규칙 찾는게 중요해

   3. BufferedReader로 입력받고 String으로 받아서 0부터 string.length()-1만큼 charAt(i)과 charAt(i+1) 비교하면서 0->1 로 넘어가는 순간 count+1

   (***) 틀린 이유 -> 맨 첫 글자가 0으로 시작하는지, 1로 시작하는지도 check해줘야돼

   1로 시작하면 1->0으로 바뀔때,

   0으로 시작하면 0->1로 바뀔때

3. 코드

   package baekjoon.Silver;
      
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
      
   public class BOJ_1439_뒤집기 {
   	public static void main(String[] args) throws IOException {
   		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   		String str = br.readLine();
   		int count = 0;
      
   		if (str.charAt(0) == '0') {
   			if (str.charAt(1) == '1')
   				count += 1;
   			for (int i = 1; i < str.length() - 1; i++) {
   				if (str.charAt(i) == '0' && str.charAt(i + 1) == '1')
   					count += 1;
   			}
   		} else { // 처음 시작이 1이면
   			if (str.charAt(1) == '0')
   				count += 1;
   			for (int i = 1; i < str.length() - 1; i++) {
   				if (str.charAt(i) == '1' && str.charAt(i + 1) == '0')
   					count += 1;
   			}
   		}
   		System.out.println(count);
   	}
   }
      
   

4. 느낀점

   • 방법을 찾는데 스터디원의 도움을 받았지만 다음번엔 스스로 떠올릴 수 있게 greedy 알고리즘 문제를 많이 풀어봐야겠다
   • 반례 찾는 방법 연습해보기! (처음에 문자열 1로 시작할때는 0->1 찾는거 아닌 경우 찾듯이)

문제 링크 : 백준 1439 뒤집기