백준 28353번: 고양이 카페 문제 풀이

1. 문제 개요

백준 28353번, 고양이 카페 문제는 제한된 **최대 무게(K)**를 초과하지 않도록 고양이들의 무게를 조합하여 가능한 한 많은 쌍을 만들라는 문제입니다. 이를 효율적으로 해결하기 위해 정렬과 투포인터를 활용하는 방법에 대해 알아보겠습니다.

---

2. 접근 방법

문제를 효율적으로 풀기 위해 다음과 같은 방법을 사용했습니다.

1. 무게 정렬: 무게를 오름차순으로 정렬하여 작은 값과 큰 값을 비교하기 쉽게 만듭니다.
2. 투포인터 활용:
   • 양 끝의 포인터 l과 r을 설정합니다.
   • 두 포인터의 합이 최대 무게 K 이하이면 쌍을 만들 수 있으므로 둘 다 포인터를 좁힙니다.
   • 합이 K보다 크면, 오른쪽 포인터(r)를 줄여서 더 작은 값을 탐색합니다.
3. 종료 조건:
   • 두 포인터가 교차하면 반복을 종료합니다.

---

3. 구현 코드

# 입력 받기
N, K = map(int, input().split())  # 고양이의 수와 최대 무게
weight_list = list(map(int, input().split()))  # 고양이 무게 리스트

# 무게 리스트 정렬
weight_list.sort()

# 투포인터 설정
l, r = 0, len(weight_list) - 1
answer = 0

# 투포인터 알고리즘
while l < r:
    tmp_weight_total = weight_list[l] + weight_list[r]  # 양쪽 무게 합
    if tmp_weight_total <= K:
        answer += 1  # 쌍이 성립
        l += 1       # 왼쪽 포인터 이동
        r -= 1       # 오른쪽 포인터 이동
    else:
        r -= 1  # 무게 초과 시 오른쪽 포인터만 이동

# 결과 출력
print(answer)

---

4. 주요 개념

(1) 정렬
정렬을 통해 작은 값과 큰 값을 비교할 수 있습니다. Python의 sort() 메서드는 시간복잡도 O(Nlog⁡N)O(N\log N)로 동작합니다.

(2) 투포인터
투포인터는 양 끝에서 시작하여 특정 조건을 만족하는 경우 한쪽 또는 양쪽 포인터를 이동시키는 기법으로, 시간복잡도 O(N)O(N)으로 문제를 해결할 수 있습니다.

---

5. 장단점

장점

• 시간복잡도가 효율적입니다. 정렬 O(Nlog⁡N)O(N\log N) 후 투포인터 O(N)O(N)를 사용해 **총 O(Nlog⁡N)O(N\log N)**에 문제를 해결할 수 있습니다.
• 직관적이며 구현이 간단합니다.

단점

• 입력이 매우 크면 메모리 사용량에 주의가 필요합니다.

---

6. 적용 예시

입력 예시

6 10
2 3 4 5 6 7

실행 과정

1. 입력 무게 리스트를 정렬: [2, 3, 4, 5, 6, 7]
2. 투포인터 시작:
   • 초기: l=0, r=5 (2+7=9 ≤ 10, 쌍 성립, 이동)
   • 두 번째: l=1, r=4 (3+6=9 ≤ 10, 쌍 성립, 이동)
   • 세 번째: l=2, r=3 (4+5=9 ≤ 10, 쌍 성립, 이동)
3. 종료: 포인터가 교차. 총 3쌍.

출력 결과

3

---

7. 결론

이 문제는 정렬과 투포인터 기법을 익히기에 좋은 예제입니다. 간단하지만 효율적인 알고리즘으로 문제를 해결하며, 실전 코딩 테스트에서 자주 등장하는 유형을 대비할 수 있습니다. 😊