백준 6159번 코스튬 파티

 

문제 링크:

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

6159번: 코스튬 파티

 

 

 

간단 회고:

	O	X
내가 직접 풀었나?	✔
다른 사람 풀이를 참고 하였나?	✔
어려웠나?		✔
푸는데 오래걸렸나?		✔

푸는데 16분 정도 걸렸다. 시간 복잡도 문제를 pypy3로 해결한 부분을 제외하곤 어려운 알고리즘이 필요한 문제는 아니었다.

 

시간 복잡도 부분을 해결하기 위해 다른 사람 풀이를 참고하였다.

 

내 풀이에서 시간 복잡도를 높이는 주요 요인이 arr의 원소를 del함수로 조작한다는데 있는 것 같다.

 

https://wayhome25.github.io/python/2017/06/14/time-complexity/

위 링크를 참고하면 del은 O(N)의 시간 복잡도를 가진다. 결과적으로 한쪽 끝의 원소를 제거하는 내 알고리즘 특성상, pop()을 (O(1)) 사용하도록 수정하면 더욱 빨라질것 같다. 다만 pop(i)는 del과 똑같이 O(N)의 시간이 든다.

 

맞았습니다!!

125616

680

PyPy3 / 수정

376

pypy3 기준 pop()을 사용해 시간을 줄였지만 여전히 python3로는 시간초과가 뜬다.

 

맞았습니다!!

125616

524

PyPy3 / 수정

if 문을 추가해 테스트 할 필요가 없는 나머지 반의 경우를 제거해서 시간을 단축시켰다. 하지만 여전히 python3로는 시간초과가 뜬다.

 

결국 2중 for 문의 문제인것으로 보인다. 내 알고리즘은 짝하나하나 비교하지만, 답의 경우는 최대 짝이 될경우 그 사이의 짝들은 모두 성립된 다는 점을 이용해 필요없는 연산을 없앴다.

 

 

 

내 풀이:

bdbest72

125616

724

PyPy3 / 수정

import sys
input = sys.stdin.readline

cow_n, costume_s = map(int,input().split())
arr = []
for i in range(cow_n):
    cow_size = int(input().rstrip())
    if cow_size < costume_s:
        arr.append(cow_size)

arr.sort()

cnt = 0
for _ in range(len(arr)):
    temp = arr[0] 
    del arr[0]
    for j in arr:
        if j <= (costume_s - temp):
            cnt += 1


print(cnt)

 

맞았습니다!!

125616

524

PyPy3 / 수정

import sys
input = sys.stdin.readline

cow_n, costume_s = map(int,input().split())
arr = []
for i in range(cow_n):
    cow_size = int(input().rstrip())
    if cow_size < costume_s:
        arr.append(cow_size)

arr.sort(reverse=True)

cnt = 0
for _ in range(len(arr)):
    temp = arr.pop()
    if temp > (costume_s // 2):
        break
    for j in arr:
        if j <= (costume_s - temp):
            cnt += 1

print(cnt)

 

 

참고한 타 풀이 및 출처(있다면)

https://www.acmicpc.net/source/34951211

n, s = map(int,input().split())
arr = []
for _ in range(n):
    arr.append(int(input()))
arr.sort()
cnt = 0
st, e = 0, n-1
while st < e:
    if arr[st] + arr[e] <= s:
        cnt = cnt + e -st
    else:
        e -= 1
        st -= 1
    st += 1
print(cnt)

dhrudgns529

29708

864

Python 3