[코드트리 챌린지] 홀수 짝수의 묶음

문제 링크는 다음과 같다 : https://www.codetree.ai/missions/5/problems/odd-even-bundle?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이번 문제는 구현 문제이고 처음엔 동적 프로그래밍을 이용해서 푸는게 어떨까 생각했지만 동적 테이블을 만들기가 까다롭고 불가능할거 같아서 다른 접근 방식을 생각해봤다.

이 문제를 풀기 위해 주어진 각 숫자들의 높고 낮음은 무의미하다. 짝수인지 홀수인지가 중요하다. 간단하게 각 숫자들을 2로 나눈 나머지인 1과 0으로 생각해보면 조금 더 간단하게 느껴질 수도 있다. 이 문제를 풀려면 (짝수 갯수) - (홀수 갯수) 가 0과 같거나 크고 1과 같거나 작아야 한다. 그렇지 않을 경우 여러가지 방법을 통해 기존 짝수나 홀수를 줄이고 서로 합해줘서 갯수를 1 차이 미만으로 줄여야 한다. 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        int odd = 0;
        int even = 0;
        int newOdd = 0; //짝수 한개와 홀수 한개를 하나의 홀수로 합친 것
        int newEven = 0;//홀수 두개를 하나의 짝수로 합친 것
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr= new int[N];
        String[] temp = br.readLine().split(" ");
        for(int i = 0; i < N; i++){
            if(Integer.parseInt(temp[i]) % 2 == 1)
                odd += 1;
            else
                even += 1;
        }
        //even - odd 는 0보다 같거나 커야 하고 1과 같거나 1보다 작아야 한다.

        if(even - odd > 1){ // 짝수가 필요 이상으로 많을때
            while((even + newEven) - (odd + newOdd) > 1){               
                even -= 1;
                odd -= 1;
                newOdd += 1;
                if(odd < 0 || even < 0)
                    break;       //주어진 짝수와 홀수가 newOdd를 만드느라 0이하로 떨어졌을 경우        
            }
        }
        else if(even - odd < 0){//홀수가 필요이상으로 많을때
            while((even + newEven) - (odd + newOdd) < 0  || (even + newEven) - (odd + newOdd) > 1){
                if((even + newEven) - (odd + newOdd) < 0){
                odd -= 2;
                newEven += 1;
                }
                else if((even + newEven) - (odd + newOdd) > 1){
                    newEven -= 1;
                    odd -= 1;
                    newOdd += 1;
                }
            }
        }
        System.out.println(odd + newOdd + even + newEven);

    }
}

 

처음 숫자들을 입력 받을때 짝수인지 홀수인지 구분해서 각각의 변수의 수치를 1씩 증가시켜줬다. 그리고 조건에 맞는 while문 안에 들어가 짝수와 홀수 비율을 비슷하게 만들어주는 작업을 한다.

 

문제는 이렇게 풀었으나 다양한 케이스도 고려해볼 수 있다. 가령 수치를 맞추는 작업을 하는 도중 odd와 even이 0 아래로 떨어지면 잘못된 것이기 때문에 이 경우에 대해서 예외처리를 해줘야 한다. 그러나 코드가 통과된걸로 봐선 이런 경우는 없다고 가정한 것으로 보인다. 그래서 구체적인 예외처리는 안해줬다.