백준 1439 - 뒤집기 (Java)

 

문제 개요

 

문제 개요

 

예제 입출력

 

---

 

풀이

 

연속된 문자열 S가 주어지고, 문자열에 "0"과 "1"만이 존재한다고 가정할 때 연속된 일부분을 선택해서 뒤집는 방식으로 모두 같은 문자로 이루어진 문자열을 만든다고 한다.

 

문제를 풀려면 1로 이루어진 문자열 덩어리의 개수와 0으로 이루어진 문자열 덩어리의 개수 중 적은 개수를 출력해주면 된다.

 

단, 여기서 주의할 점은 처음부터 문자열이 모두 같은 한 문자로 이루어진 경우에는 0으로 출력해주는 처리를 해줘야 한다.

 

나는 다음 순서로 알고리즘 해결을 위한 순서를 생각했다.

 

1. 연속된 문자열을 split()을 사용해 배열로 만든다.
2. 그 배열을 향상된 for문으로 차례대로 돌면서 "1"로 이루어진 덩어리와 "0"으로 이루어진 덩어리의 개수를 특정한다.
3. 만약 1덩어리와 0덩어리의 합이 1인 경우 원래부터 하나의 문자로 이루어진 문자열이므로 0을 출력하고 끝낸다.
4. 특정된 덩어리 중 개수가 적은 것을 선택하여 출력한다.

 

---

 

코드

 

import java.io.*;

public class Main {
    public static void main(String[] arg) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split("");
        int one=0; int zero=0;
        String pre = "";

        for (String s : input) {
            if (s.equals(pre))
                continue;

            pre=s;
            if (s.equals("1")) one++;
            else zero++;
        }

        int answer = one > zero ? zero : one;
        if (one + zero == 1)
            answer = 0;

        System.out.println(answer);
        return;
    }
}

 

코드 리뷰

 

1. 입력 값에 split("") 메서드를 실행한 결과 배열을 String[] 타입의 input에 저장한다.
2. 1로 이루어진 덩어리가 저장될 변수 one, 0으로 이루어진 덩어리가 저장될 변수 zero를 생성 및 초기화한다.
3. String 타입의 pre를 선언 및 초기화한다.
   • 반복문에서 이전 값과 비교할 때 사용될 변수이다.
4. 향상된 for문으로 input의 모든 요소를 차례대로 순회한다.
5. 루프를 도는 과정에서 이전 값을 의미하는 pre와 현재 값인 s가 같은 값이라면, 같은 덩어리였다는 의미이므로 continue
6. pre와 s가 다른 경우, continue 되지 않고 아래로 넘어와서 어떤 덩어리로 바뀌었는지 체크 후 해당 덩어리를 카운팅 한다.
   • 0 -> 1이라면 one 즉, 1로 이루어진 덩어리가 한 개 더 많아진 것이므로 카운팅 한다.
7. 반복문을 마치고 출력해줄 int형 변수 answer에 one, zero 중 작은 값을 저장한다. (삼항 연산자)
8. 만약 one + zero가 1이라면 입력 문자열을 순회하면서 문자가 단 하나였다는 의미이기 때문에 answer를 0으로 바꿔준다.
9. answer를 출력한다.

---

 

제출 결과

 

 

다른 사람들의 제출 결과를 봤는데 코드 양도 더 작고 효율도 거의 두 배정도 좋게 제출했길래 나도 조금 더 효율적인 코드를 만들고 싶었지만, 쉽지 않은 싸움이었다..