백준 22988 재활용 캠페인 파이썬 문제풀이 (python 투포인터)

문제 보러가기

 

백준 재활용 캠페인 파이썬 문제풀이

결국 이것도 투 포인터를 이용하는 문제인데,

단순히 생각하면 합이 넘으면 두 포인터를 모두 안쪽으로 옮기고,

넘지 않으면 작은 인덱스를 증가시키는 로직으로 떠올렸다.

 

물론 반복은 a와 b가 있을 때 a<b인 조건에서 반복하고

같아지거나 a>b가 되면 끝낸다.

 

n,x = map(int, input().split())
bottles = list(map(int, input().split()))
a = 0
b = n-1
cnt = 0
while a < b:
    sum = bottles[a] + bottles[b]
    # 합이 넘으면
    if sum >= x/2:
        a+=1
        b-=1
        cnt+=1
    # 합이 안넘으면
    else:
        a+=1
print(cnt)

생각대로 짰지만 틀렸다.

뭔가 더 있는 모양이다. 

 

문제를 잘못 이해했다. 두 병을 가지고 합쳐 채운 바꾸고 나서,

또 다시 바꿔온 병들을 합쳐 교환할 수 있었다.

 

또한 이미 병들 중 꽉 채워진 병이 있으면 교환하지 않고 놔두면 된다.

이거한 세세한 조건들이 있었다. 

 

정말 놓칠 수 있는 포인트가 있는데,

그것은 나머지 병들에 대한 것이다.

 

작아서 지나친 나머지 병들이나 마지막 하나남은 병들에 대해서

작은 병 두 개를 합치면 절반을 채워주니, 절반을 채운 상태에서 하나 더 즉 세 개가 모이면 꽉찬 병이 된다는 것. 

이들을 고려해서 코드를 작성하자. 

 

정답 코드

n,x = map(int, input().split())
bottles = list(map(int, input().split()))
bottles.sort()
a = 0
b = n-1
cnt = 0
remain = 0
while a <= b: # 교차되면 정지
    # 이미 꽉찬 병
    if bottles[b] >= x:
        b-=1
        cnt+=1
        continue

    # 포인터가 같으면
    if a == b:
        remain+=1 # 나머지 추가
        continue

    if bottles[a] + bottles[b] >= x/2:
        cnt+=1
        a+=1
        b-=1
    else: # 합쳐도 안되는 작은 것들은 나머지
        a+=1
        remain +=1

print(cnt + remain//3)

코드에서 주의할 점이 몇가지 있다면,

먼저 이미 꽉찬 병을 만나면 continue로 나머지 조건을 넘기고,

 

포인터가 같으면. 즉 남은 병이 하나 남으면 나머지로 추가한뒤

마찬가지로 나머지 조건을 넘겨야한다.

 

그렇지만 왜인지 시간초과가 뜬다.. 

 

n,x = map(int, input().split())
bottles = list(map(int, input().split()))
bottles.sort()
a = 0
b = n-1
cnt = 0
remain = 0
while a <= b: # 교차되면 정지
    # 이미 꽉찬 병
    if bottles[b] >= x:
        b-=1
        cnt+=1
        continue

    # 포인터가 같으면
    if a == b:
        remain+=1 # 나머지 추가
        break

    if bottles[a] + bottles[b] >= x/2:
        cnt+=1
        a+=1
        b-=1
    else: # 합쳐도 안되는 작은 것들은 나머지
        a+=1
        remain +=1

print(cnt + remain//3)

포인터가 같은 경우를 continue로 해서 무한 반복이 돌았다.

break로 바꾸어서

바로 탈출하게 하였다. 

 

 

정답이다.

조건을 세밀하게 검토하고, 고민해보자.