일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- 구름톤 챌린지
- 지연로딩
- 금 채굴하기
- 완전탐색
- 구름톤 트레이닝
- 백준
- Today I Learned
- 구름톤
- JPA
- 멀록 조명등
- 행복한 수열의 개수
- IT 좀 아는 사람
- 1931번
- til
- 즉시로딩
- spring
- 1005 #ACM craft #백준
- 공부하기 싫어 #그래도 해야해
- 회의실 배정
- 백준 #1010 #다리놓기
- 코드트리
- 코드트리 챌린지
- 공부 기록
- 코딩테스트실력진단
- 최장 공통 부분수열
- TagLibraryValidator
- 동적 계획법
- @EntityGraph
- 코딩테스트
- eager
- Today
- Total
화분
[코드트리 챌린지] 홀수 짝수의 묶음 본문
문제 링크는 다음과 같다 : https://www.codetree.ai/missions/5/problems/odd-even-bundle?&utm_source=clipboard&utm_medium=text
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
이번 문제는 구현 문제이고 처음엔 동적 프로그래밍을 이용해서 푸는게 어떨까 생각했지만 동적 테이블을 만들기가 까다롭고 불가능할거 같아서 다른 접근 방식을 생각해봤다.
이 문제를 풀기 위해 주어진 각 숫자들의 높고 낮음은 무의미하다. 짝수인지 홀수인지가 중요하다. 간단하게 각 숫자들을 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 아래로 떨어지면 잘못된 것이기 때문에 이 경우에 대해서 예외처리를 해줘야 한다. 그러나 코드가 통과된걸로 봐선 이런 경우는 없다고 가정한 것으로 보인다. 그래서 구체적인 예외처리는 안해줬다.
'Study > CODINGTEST' 카테고리의 다른 글
[Baekjoon]2448번 별 찍기 - 11 (0) | 2023.12.20 |
---|---|
[Baekjoon]1107번 리모컨 풀이 (0) | 2023.12.11 |
[코드트리 챌린지] 금 채굴하기 (0) | 2023.09.12 |
[코드트리 챌린지] 트로미노 (0) | 2023.09.11 |
[구름톤 챌린지 19일차] 대체 경로 (0) | 2023.09.10 |