[boj 1092.python] '배' 풀이 (feat. 언어만 바꿔도 통과, Python3와 PyPy3의 차이)

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

 

 

1차 시도 👉 시간 초과 실패

N = int(input()) # 크레인 갯수
cranes = list(map(int, input().split())) # 각 크레인의 무게 제한
M = int(input()) # 박스의 갯수
boxes = list(map(int, input().split())) # 각 박스의 무게

cranes.sort(reverse = True)
boxes.sort(reverse = True)

# 예외 처리
if boxes[0] > cranes[0]:
    print(-1)

# 시간이 얼마나 걸리는지 계산
time = 0
while boxes:
    time += 1
    for crane in cranes:
        # 각 크레인이 들 수 있는 박스 찾기
        for i in range(len(boxes)):
            if crane >= boxes[i]:
                # 박스를 옮기고 리스트에서 제거
                boxes.pop(i)
                break
print(time)

 

1. 크레인과 박스 정렬: 먼저 크레인과 박스를 내림차순으로 정렬시켰다. 무거운 박스를 처리할 수 있는 크레인이 무거운 박스를 우선 처리하도록 해서 최대한 효율적으로 작업할 수 있게 했다. (알고리즘으로 꼽자면 그리디 방식)
2. 크레인으로 박스 처리: 각 크레인에 대해 가장 무거운 박스를 들 수 있으면, 그 박스를 처리하고 리스트에서 제거한다.모든 크레인이 동시에 동작하므로 한 번에 최대한 많은 박스를 옮길 수 있다.
3. 박스가 모두 처리될 때까지 반복: 박스가 남아있는 동안 시간(time)을 증가시키면서 반복한다.

박스나 크레인 개수가 각각 최대 10,000과 50이므로, 매번 박스를 찾는 작업에서 O(N*M)의 복잡도를 가진다. 반복되는 사이클의 횟수가 크면 클수록 (반복 사이클 횟수가 T라고 했을 때) 최악의 시간 복잡도는 O(T*N*M)이 되서 불리할 수 있겠다 생각했지만 일단.. ㅋㅋ 했는데 시간초과가 떴다.

쩝

 

2차 시도 👉 PyPy3로 언어만 변경했더니 성공 (?)

 

아무리 고민을 해봐도 어떻게 시간복잡도를 줄일 수 있을지 감이 안잡혀서 구글링 찬스를 썼는데 .. Python3으로 제출했을 때는 시간초과로 통과가 안되던 코드가 PyPy3로 제출하니 통과됐다는 글들을 여러 개 접할 수 있었다.

 

그래서 Python3랑 PyPy3랑 뭐가 다르길래? 시간초과가 뜨는 코드가 통과가 되는거지? 하고 이 둘의 차이점을 찾아보기로 했다.

통과라니!

 

++) Python3와 PyPy3의 차이

 

결론부터 말하자면 PyPy3는, Python3을 실행시 시간이 매우 오래 걸린다는 단점이 있어 그것을 개선하고자 JIT컴파일 방식을 도입해 만든 언어라고 한다. 하나씩 살펴보자.

 

Python3

• CPython은 Python의 기본 구현체로, 인터프리터 방식이다.
• 인터프리터 방식은 소스 코드를 한 줄씩 읽고 바로 실행하므로, 반복적인 작업이나 리스트를 다루는 연산이 많을 경우 성능이 떨어질 수 있다. (1092번 문제같은 경우 내가 짠 코드는 2중 for문)
• 특히 지금처럼 for 루프와 pop 연산을 자주 사용하는 경우 시간이 많이 걸린다.

PyPy3:

• PyPy는 Python 코드를 JIT(Just-In-Time) 컴파일 방식으로 실행한다.
• JIT 컴파일러는 프로그램을 실행하기 전에 컴파일 하는 대신, 프로그램을 실행하는 시점에서 필요한 부분들을 즉석으로 컴파일 하는 방식이다.
• 인터프리트 하면서 자주 쓰이는 코드를 캐싱하기 때문에 인터프리터의 느린 실행속도를 개선할 수 있다. (JVM에서도 바이트 코드를 기계어로 번역할 때 JIT 컴파일러를 사용한다)
• 이러한 특성 때문에 PyPy는 Python3에 비해 반복문이 많거나 메모리 관리를 자주 해야 하는 프로그램에서 훨씬 더 성능이 좋다고 한다.

즉! 정리하면 PyPy3에서는 실행 시 자주 쓰이는 코드들을 캐싱하는 기능이 있기 때문에 실행 속도를 개선할 수 있다. 그래서 반복이 자주 발생하는 코드에서는 PyPy3가 더 우세하다. 하지만, 이 경우 코드를 캐싱하면서 메모리를 조금 더 사용하기 때문에 반복이 없는 간단한 코드에서는 메모리, 속도 측에서 Python3가 우세할 수 있다는 것이다.

 

정리

코드 상황에 맞춰서 Python3, PyPy3 이 두 구현체를 적절하게 사용하면 될 듯. 진짜 이 문제가 아니었다면 몰랐을 (혹은 한참 뒤에 알았을?ㅎ) 이 두 구현체의 차이를 알게되서 럭키비키잖아 🍀

 

---

References

https://ralp0217.tistory.com/entry/Python3-%EC%99%80-PyPy3-%EC%B0%A8%EC%9D%B4

https://www.acmicpc.net/board/view/57353