백준/1439 뒤집기

뒤집기 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

21033

11478

9076

54.629%

문제

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

---

 1. 틀린시도

첫번째,마지막숫자에 대한 처리를 하고

중간에있는 숫자는 해당 숫자 바로 전의 숫자랑 비교해서 다르면에 대한 처리를 해서 풀려고하다 실패

 

2. 스택을 이용

문제의 입력값의 범위를 생각해봤다.

길이가 1개인 문자열이 들어올 수도있고.

길이가 100인 문자열도 들어올 수 있다.

 

갯수가 홀수개일수도, 짝수개일수도 

숫자가 모두 같을수도

와 같은 다양한 경우를 테스트해봤다 ( 예제 입력말고)

 

풀이법

1의 부분집합, 0의 부분집합을 저장할 변수를 만들어줬다. 

문제는 결국 1또는 0의 부분집합의 갯수중 작은걸 뽑으면 되는 문제이다.

 

문자열의 숫자들을 하나씩 스택에 넣어줬다.

스택에서 하나씩 꺼내며 해당 숫자에 대한 

 

package practice;

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        String input = br.readLine();
        int result1 = 0;
        int result0 = 0;

        Stack<Integer> list = new Stack<>();
        for (int i = 0; i < input.length(); i++) {
            int temp = Character.getNumericValue(input.charAt(i));
            list.push(temp);
        }
//        bw.write(list+"\n");

        int ex = -1; //이전의 숫자를 저장할 변수

        while(!list.isEmpty()) //스택이 빌때까지 반복
        {
            int current = list.pop(); //스택에서 하나뽑는다.
            if(ex != -1) //첫번째 숫자가 아니라면
            {
                if (current == ex) { //첫번째 숫자가 아니고 , 이전의 숫자랑 같다면(같은 부분집합이므로 넘어감)
                    continue; // 그냥 넘어간다.
                }
            }
            //첫번째 숫자거나, 첫번째 숫자가 아닌데 이전의 숫자랑 다른애들 -> 부분집합 증가.
            if(current == 0)
            {
                result0++;
                ex = current;
            }
            else {
                result1++;
                ex = current;
            }
        }

        if(result0>result1)
        {
            bw.write(result1+"");
        }
        else{
            bw.write(result0+"");
        }




        bw.flush();
        bw.close();


    }



}

 

 

다른사람 풀이

-> Stringtokenizer를 이용

 

public static void main(String[] args) throws IOException {

        String input = br.readLine();
        int result1 = 0;
        int result0 = 0;

        StringTokenizer st = new StringTokenizer(input,"0"); // 0을 구분자로 토큰을 생성한다.
        result0 = st.countTokens(); // 그럼 0의 부분집합의 갯수가 토큰의 총갯수
        st = new StringTokenizer(input, "1"); // 1을 구분자로 토큰을 생성한다.
        result1 = st.countTokens(); // 그럼 1의 부분집합의 갯수가 토큰의 총갯수

        if (result1 > result0) { // 더 작은걸 출력해준다.
            bw.write(result0+"");
        }
        else{
            bw.write(result1+"");
        }





        bw.flush();
        bw.close();


    }

 

다른사람풀이

안쪽에 있는 부분집합의 갯수를 센다.

11122121121 이라고 봤을때 , 1의 부분집합과 2의 부분집합의 갯수를 셀때

시작하는수와 끝의 숫자가 같을때 안쪽에 존재하는 부분집합의 갯수는 항상 1의 부분집합 갯수보다 작다.

1로 시작하고 1로 끝났을떄 1의 부분집합 -> 111,1,11,1 4개   2의 부분집합 -> 22,2,2 3개

 

112212      처럼 첫번째 숫자와 끝의 숫자가 다를때 부분집합 ->  1의 부분집합과 2의 부분집합의 갯수가 같음

12121212  처럼 첫번째 숫자와 끝의 숫자가 다를때 부분집합 ->  1의 부분집합과 2의 부분집합의 갯수가 같음

그걸 이용한 풀이인듯하다.

첫번째 숫자를 이용해서 다른숫자의 부분집합의 갯수를 센다. 다른숫자의 부분집합의 갯수는 어차피 첫번째 숫자의 부분집합의 갯수와 같거나 더 작을테니까

 

 

public static void main(String[] args) throws IOException {

        String data = br.readLine();

        int answer = 0;
        int index = 1;
        if(data.length()>0) {
            char std = data.charAt(0); // 첫번째수를 저장

            while (index < data.length()) { //input의 길이만큼 반복
                if (data.charAt(index) == std){ //첫번째수와 같은수라면 -> 첫번째 수의 부분집합은 안셀꺼니까
                    index++; // 인덱스 증가시켜주고
                    continue; // continue로 넘긴다.
                }

                answer++; //첫번째수와 같지않은수라면 -> 다른수의 부분집합 시작부분이므로 , 다른수의 부분집합수 증가

                for (int i = index; i < data.length(); i++) { // 해당인덱스부터 끝까지 반복해서 해당부분집합의 끝을 찾는다.
                    if (data.charAt(i) == std) {  // 현재 숫자가 , 첫번째 숫자와 같다? => 다른수의 부분집합이 끝났다.
                        break; // 반복문 탈출
                    }
                    index++; // 아니라면 증가시킨다 -> 증가시킴으로서 부분집합을 탈출.
                }
            }
        }

        System.out.println(answer);






        bw.flush();
        bw.close();


    }

다른풀이 -> 각 부분집합을 직접 나눠서 저장하고 , 총 갯수 비교

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

    ArrayList<String> al0 = new ArrayList<>();
    ArrayList<String> al1 = new ArrayList<>();
    StringBuffer temp0 = new StringBuffer();
    StringBuffer temp1 = new StringBuffer();

    String a = br.readLine();
    for (int i = 0; i < a.length(); i++) {

      if (a.charAt(i) == '0') {
        if (temp1.length() != 0) {
          al1.add(temp1.toString());
          temp1.setLength(0);
        }
        temp0.append("0");
      }

      if (a.charAt(i) == '1') {
        if (temp0.length() != 0) {
          al0.add(temp0.toString());
          temp0.setLength(0);
        }
        temp1.append("1");
      }

    }
    if (temp0.length() != 0) {
      al0.add(temp0.toString());
    } else if (temp1.length() != 0) {
      al1.add(temp1.toString());
    }

    // Iterator iter0 = al0.iterator();
    // Iterator iter1 = al1.iterator();
    // while (iter0.hasNext()) {
    // bw.write("0인부분:" + iter0.next() + "\n");
    // }
    // while (iter1.hasNext()) {
    // bw.write("1인부분:" + iter1.next() + "\n");
    // }

    int result = 0;
    if (al0.size() == 0 | al1.size() == 0) {
      result = 0;
    } else {
      result = Math.min(al0.size(), al1.size());
    }

    bw.write(result + "\n");

    bw.flush();
    bw.close();
  }