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

www.acmicpc.net/problem/1439

1439번: 뒤집기

 

 

 

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

 

연속된 숫자를 한번에 뒤집을 수 있는데요 (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))
}

 

 

 

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