[백준, Java] 22988번, 재활용 캠페인(투 포인터, 정렬)

문제 링크

22988번: 재활용 캠페인

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. N개의 헤어 에센스는 X크기의 용기가 존재하며, 용기마다 헤어 에센스가 들어있습니다.

2. 헤어 에센스 용기를 2개를 재활용 할 때, 용량이 가득차지 않으면 용기의 절반(X/2)만큼 채워서 줍니다.

3. 헤어 에센스를 합칠 때, 가득 찬 용기를 구할 수 있는 최대 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 헤어 에센스 용기를 합치는 최적의 경우를 진행합니다.

 

3. 최적의 경우에서 얻은 가득찬 용기의 개수를 결과로 출력합니다.

 

 

최적의 경우

 

이 문제에서 최적의 경우를 탐색할 때

 

1. 헤어 에센스 3개를 합치면 무조건 가득찬 헤어 에센스를 만들 수 있습니다.

 

Why??

 

헤어 에센스 2개를 합쳤을 때 가득차지 않더라도 2/X만큼 채워주기 때문에 절반은 항상 채워져 있습니다.

 

합친 에센스와 새로운 에센스를 합치면 한 번더 2/X를 채워지기 (2/X + 2/X)가 항상 성립하기 때문에 무조건 가득찬 헤어 에센스를 만들 수 있습니다.

 

2. 헤어 에센스가 기본적으로 가득찬 용기는 합치지 않아도 됩니다.

 

3. 헤어 에센스을 합치는 경우 큰 값은 조건에 만족하는 작은 값과 합쳐야 합니다.

 

Why?

 

헤어 에센스 용기에 많은 양이 담겨져 있는 것을 최대한 활용해야 가득찬 헤어 에센스 용기를 최대로 만들 수 있기 때문입니다.

 

그래서, 헤어 에센스 양의 큰 값을 기준으로 최소값들을 찾는 경우가 최대 개수를 구하는 방법입니다.

 

조건에 만족하는 큰 값에 기준하는 최소값을 결정할 때 저는 투 포인터를 사용하였습니다.

 

투 포인터 탐색

 

min : 용량이 절반이 채워질 때 가득 찬 용기로 만들 수 있는 최소 양

 

X가 홀수 일 때

min = X / 2 + 1

 

X가 짝수일 때

min = X/2

 

투 포인터 탐색할 때 2가지 경우

 

S + E  >= min

- 두 용기를 합치면 하나의 가득찬 헤어 에센스가 만들어집니다.

result + 1

S + 1

E - 1

 

S + E < X

- 두 용기를 합쳐도 하나의 가득찬 헤어 에센스가 만들어지지 않습니다.

S + 1

큰 값에서 최소값을 찾아야 하기 때문에 S값만 증가합니다.

 

X = 18
min = 9

 

1	5	7	7	18
S			E	(이미 가득찬 용기)

 

S(1) + E(7) = 8

S + E >= min(9)

S++

 

1	5	7	7	18
	S		E	(이미 가득찬 용기)

 

S(5) + E(7) = 12

S + E >= min(9)

result++

S++

E--

 

... 아래와 같이 진행한 뒤

 

result +=  사용하지 않은 남은 용기 / 3

 

Why?

 

사용하지 않는 용기도 3개를 사용하면 항상 1개의 가득찬 용기로 만들 수 있기 때문에 3으로 나눈 값이 가득찬 용기의 개수입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 7

 

X : 13

0	1	2	3	5	8	13
S					E	(가득 찬 용기)

 

2. 헤어 에센스 용기를 합치는 최적의 경우를 진행합니다.

 

X는 홀수

min = 13 / 2 + 1 = 7

 

0	1	2	3	5	8	13
S					E	(가득 찬 용기)

 

S(0) + E(8) = 8

S + E >= min(7)

 

S + 1

E - 1

 

0	1	2	3	5	8	13
	S			E		(가득 찬 용기)

S(1) + E(5) = 6

S + E < min(7)

 

S + 1

 

0	1	2	3	5	8	13
		S		E		(가득 찬 용기)

S(2) + E(5) = 7 

S + E >= min(7)

S + 1

E - 1

 

0	1	2	3	5	8	13
			S, E			(가득 찬 용기)

S와 E의 값이 같아져서 2개의 헤어 에센스를 합치는 경우가 더 이상 발생하지 않기 때문에 탐색을 종료합니다.

 

사용하지 않은 에센스 : 2개,  { 0, 3 }

 

3. 최적의 경우에서 얻은 가득찬 용기의 개수를 결과로 출력합니다.

 

가득차 헤어 에센스 : 3개, { 0 + 8, 5 + 2, 13} 

 

남은 헤어 에센스로 가득 찬 용기 만드는 개수 : 2/3 = 0개

 

 

가득 찬 헤어 에센스 개수 3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 인형의 정보를 띄어쓰기 기준 구분합니다.
• X의 값에 따른 min값 계산합니다.
• Collections.sort()을 이용해서 용량 기준 오름차순 정렬합니다.
• 투 포인터와 조건을 이용해서 최적의 경우일 때 가득찬 용기의 개수를 구합니다.
• 사용하지 않은 용기를 3개 합쳐서 가득찬 용기로 만듭니다.
• 최적의 경우에서 얻은 가득찬 용기이 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

 

결과코드

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

class Main {
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        long X = Long.parseLong(st.nextToken());
        long min = 0;
        //용기 절반을 채워줄 때 가득찰 수 있는 최소 용량
        if(X%2 == 0){	//짝수일 때
            min = X/2;
        }else{		//홀수 일 때
            min = X/2 + 1;
        }
        st = new StringTokenizer(br.readLine()," ");
        long result = 0;
        //헤어 에센스 정보 저장
        List<Long> list = new ArrayList<>();
        for(int i=0;i<N;i++){
            long num = Long.parseLong(st.nextToken());
            if(num >= X){
                result++;
                continue;
            }
            list.add(num);
        }
        //헤어 에센스 용량 오름차순 정렬
        Collections.sort(list);
        //투 포인터을 이용한 최적의 경우 탐색
        int s = 0;
        int e = list.size()-1;
        int cnt = 0;
        while(s <= e){
            //용기 합치는 값 계산
            long sum = list.get(s) + list.get(e);
            if(s < e && sum >= min){	//가득찬 용기 만들 때
                result++;
                s++;
                e--;
            }else{		//가득찬 용기 만들지 못할 때
                cnt++;
                s++;
            }
        }
        //합치지 않은 용기 3개 합쳐서 가득찬 용기 만들기
        result += cnt/3;
        //가득찬 헤어 에센스 개수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}