BEAKJOON / 백준 - JAVA 28353번 고양이 카페

2024.08.28기준 - 실버3

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 고양이들 중에 2마리를 안을 때 주어진 무게(k) 보다 작거나 같은 짝을 구하는 문제입니다.

 

투 포인터 알고리즘을 이용하여 문제에 접근을 했습니다.

고양이 무게를 저장한 배열을 정렬을 하여 가벼운 고양이와 무거운 고양이 2가지의 분류로 나누어 진행했습니다.

 

1. 가벼운 고양이 기준으로 반복문을 돌리면서 무거운 고양이의 인덱스를 따로 계산을 해주었습니다.

2. 만약 2마리의 고양이 무게의 합이 k보다 크다면 무거운 고양이의 인덱스를 줄여줍니다.

3. 무거운 고양이의 인덱스가 가벼운 고양이의 인덱스보다 작거나 같다면 모든 반복문을 종료시킵니다.

4. 만약, 2마리의 고양이 무게가 k이하라면 count를 올려주어 계산을 진행합니다.

for (int i = 0; i < n; i++) {
    one = arr[i]; // 가벼운 고양이

    while (true) {
        two = arr[back]; // 무거운 고양이

        // 무거운 고양이의 인덱스가 가벼운 고양이의 인덱스를 넘어가면 멈춘다.
        if (back <= i) {
            break;
        }

        // 2마리의 고양이를 들었을 때, 행복할 수 있다면
        if (one + two <= k) {
            count++;
            break;
        } else { // 행복할 수 있는 무게를 초과했다면
            back--;
        }
    }
    back--;

    // 행복할 수 있는 인원 수는 (고양이 수) / 2가 최대이며,
    // 동시에 하나의 고양이를 들 수 없기 때문에
    // 무거운 고양이의 인덱스가 가벼운 고양이 인덱스보다 작으면 안된다.
    if (count >= n / 2 || i >= back) {
        break;
    }
}

 

 

코드

package Main;

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 고양이의 수
		int k = Integer.parseInt(st.nextToken()); // 한 번에 들 수 있는 무게
		
		int[] arr = new int[n]; // 고양이 무게를 저장할 배열
		st = new StringTokenizer(br.readLine()); // 고양이의 무게
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr); // 무게가 적게 나가는 순으로 정렬
		int count = 0; // 행복해지는 인원 수
		int back = n - 1; // 비교를 위해 무거운 고양이의 인덱스
		int one, two; // 2마리의 고양이 무게를 저장할 변수
		
		for (int i = 0; i < n; i++) {
			one = arr[i]; // 가벼운 고양이
			
			while (true) {
				two = arr[back]; // 무거운 고양이
				
				// 무거운 고양이의 인덱스가 가벼운 고양이의 인덱스를 넘어가면 멈춘다.
				if (back <= i) {
					break;
				}
				
				// 2마리의 고양이를 들었을 때, 행복할 수 있다면
				if (one + two <= k) {
					count++;
					break;
				} else { // 행복할 수 있는 무게를 초과했다면
					back--;
				}
			}
			back--;
			
			// 행복할 수 있는 인원 수는 (고양이 수) / 2가 최대이며,
			// 동시에 하나의 고양이를 들 수 없기 때문에
			// 무거운 고양이의 인덱스가 가벼운 고양이 인덱스보다 작으면 안된다.
			if (count >= n / 2 || i >= back) {
				break;
			}
		}
		
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
}