[백준/Baekjoon 28353] 고양이 카페 파이썬(Python) 풀이

문제

 

https://www.acmicpc.net/problem/28353

28353번: 고양이 카페

 

문제핵심

문제의 핵심은 리스트를 오름차순 배열 후 앞쪽과 뒤쪽 리스트를 이용해서 푸는 것이 핵심이다.

이 과정에서 투 포인터, 리스트, 큐 등으로 해결할 수 있다.

여기서의 풀이는 큐 중 하나인 deque를 사용할 것이다.

 

풀이과정

1. N,K의 입력을 받는다.

2. 고양이(cat) 무게를 리스트로  받는다. 그후 오름차순 배열로 만든다.

3. cat를 deque로 받는다.

4. 정답인 변수 cnt를 선언한다. -> 앉힐 수 있는 사람 수를 뜻함

5. while 반복문을 활용한다.-> 조건문 활용 첫번째 + 마지막 고양이 무게가 <=k일때 앞,뒤 고양이를 pop하고 cnt+=1을 한다.(앉힐 수 있음) 만약 >k일경우 cnt는 증가시키지 말고 뒤에 있는 고양이만 pop한다.

주의) 고양이 1마리일때는 비교 대상이 없으므로 break로 반복문 빠져나오자

6. 정답 출력

정답코드

from collections import deque

N, K = map(int, input().split())
cat = list(map(int, input().split()))
cat.sort() 
# 먼저 고양이 몸무게 순으로 만든다.
cat = deque(cat)
# deque를 활용하여 고양이를 조절할 것이다.

cnt = 0  # 앉힐 수 있는 사람 수
# 두 고양이의 무게 < K 앉힐 수 있다.
# 두 고양이의 무게 > K 앉을 수 없다.
while cat:
    if len(cat)==1:
        break
    if (cat[0] + cat[-1]) <= K:
        cat.popleft()
        cat.pop()
        cnt += 1
    else :
        cat.pop()

print(cnt)

문제평 및 새롭게 알게된 것

풀 수 있는 방법이 여러가지 있어서 어렵지 않은 문제였다. 투 포인터로 풀까 하다가 귀찮게 start,end 변수를 증가시키는것보다 deque로 앞 뒤 요소를 pop하는것이 더 좋다라고 생각해서 그렇게 풀었다.