백준 25379번 피하자 Java

https://www.acmicpc.net/problem/25379

문제

---

생각하기

---

• 그리디 문제이다.

동작

그리디 방식으로 문제를 해결해야 한다.
문제에서 요구한 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 을 구현하려면
결국 짝수와 홀수를 구분해서 각자 한쪽으로 몰아야 한다.

그중에 최소 교환 횟수를 구하기 위해서는 짝수를 바꾸는 게 나은지 홀수를 바꾸는 게 나은가를 찾으면 된다.

예시가

4
1 2 3 1

일 때 먼저 홀수를 왼쪽으로 이동시킬 때 몇 번의 횟수가 필요한지 계산한다.

        int count = 0;
        long oddSum = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] % 2 == 1) {
                // 앞에서 나온 짝수의 개수만큼 스왑을 해야한다.
                oddSum += count;
            } else {
                // 0부터 시작해서 만나는 짝수의 개수
                count++;
            }
        }

0부터 시작해서 N - 1까지 배열을 순회하면서 홀 수 앞에 짝수가 몇 개인지 계산하면 각 홀 수는 앞에 있는 짝수만큼을 교환해야 하므로
홀수마다 앞에 있는 짝수 개수를 추가하면 총 교환하는 횟수를 구할 수 있다.

이 방법을 짝수에도 똑같이 적용한 뒤 둘 중 적은 교환 횟수를 선택하면 된다.

결과

코드

---

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static int[] arr;

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int count = 0;
        long oddSum = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] % 2 == 1) {
                // 앞에서 나온 짝수의 개수만큼 스왑을 해야한다.
                oddSum += count;
            } else {
                // 0부터 시작해서 만나는 짝수의 개수
                count++;
            }
        }

        count = 0;
        long evenSum = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] % 2 == 0) {
                evenSum += count;
            } else {
                count++;
            }

            if (evenSum >= oddSum) {
                sb.append(oddSum);
                return sb.toString();
            }
        }

        sb.append(Math.min(oddSum, evenSum));
        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    } // End of input()
} // End of Main class