관리 메뉴

막내의 막무가내 프로그래밍 & 일상

[알고리즘] 백준 1439 뒤집기 -그리디- 자바 코틀린 본문

알고리즘/그리디

[알고리즘] 백준 1439 뒤집기 -그리디- 자바 코틀린

막무가내막내 2021. 4. 9. 18:10
728x90

www.acmicpc.net/problem/1439

 

1439번: 뒤집기

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

www.acmicpc.net

 

 

 

백준 그리디유형의 문제인 뒤집기를 풀어봤습니다. ㅎㅎ

 

연속된 숫자를 한번에 뒤집을 수 있는데요 (0 or 1)

최소한으로 뒤집어서 모두 같은 숫자를 만들어야합니다.

 

풀이방법은 0과 1의 연속된 숫자의 묶음이 더 적은 쪽의 묶음의 개수를 답으로 출력해주면 됩니다.

 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

class Main {
    private static String S;
    private static int[] nums;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        S = sc.next();
        nums = new int[S.length()];
        for (int i = 0; i < S.length(); i++) {
            nums[i] = Integer.parseInt(String.valueOf(S.charAt(i)));
        }
        int zeroCnt = 0;
        int oneCnt = 0;
        int prevNum = -1;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (num != prevNum) {
                if (num == 0) {
                    zeroCnt++;
                } else { //1
                    oneCnt++;
                }
            }
            prevNum = num;
        }
        System.out.println(Math.min(zeroCnt, oneCnt));

    }
}

 

[Kotlin]

import java.util.*

private lateinit var S: String
private lateinit var nums: IntArray

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    S = sc.next()
    nums = IntArray(S.length)
    for (i in S.indices) {
        nums[i] = S.get(i).toString().toInt()
    }
    var zeroCnt = 0
    var oneCnt = 0
    var prevNum = -1
    for (i in nums.indices) {
        val num = nums[i]
        if (num != prevNum) {
            if (num == 0) {
                zeroCnt++
            } else { //1
                oneCnt++
            }
        }
        prevNum = num
    }
    println(Math.min(zeroCnt, oneCnt))
}

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!

728x90
Comments