BOJ 23881 (python) - python3와 pypy3 각각 풀이 비교

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

23881번: 알고리즘 수업 - 선택 정렬 1

이 문제에서 주의할건

1. 정렬을 할 때 뒤에서부터 정렬한다는 것 (max값을 찾아서 정렬)
2. 시간초과

였다.

 

 

정답1 (python 3)

import sys
input = sys.stdin.readline


if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    cnt = 0
    for i in range(N-1, 0, -1):
        max_idx = A.index(max(A[:i+1]))

        if i != max_idx:       
            A[i], A[max_idx] = A[max_idx], A[i]
            cnt += 1
        if cnt == K:
            print(f"{A[max_idx]} {A[i]}")
            sys.exit(0)
    print(-1)

문제를 제대로 안읽고 내 머릿 속 선택 정렬로 생각하고 작은 수 순서대로 정렬했다가 예제와 답이 달라서 뭐지 했는데
문제를 제대로 읽어보니 큰 수를 먼저 찾아서 작은 수 순서대로 찾아서 정렬하는거였다. ^,ㅠ

그리고 시간초과...

 

 

 

시간초과로 오답난 풀이 (근데 PyPy3로 제출하면 통과 된다)

import sys
input = sys.stdin.readline
if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    cnt = 0
    for i in range(N-1, 0, -1):
        max_idx = i

        for j in range(i-1, -1, -1):
            if A[max_idx] < A[j]:
                max_idx = j
        if i != max_idx:    
            A[i], A[max_idx] = A[max_idx], A[i]
            cnt += 1
        if cnt == K:
            print(f"{A[max_idx]} {A[i]}")
            sys.exit(0)
    print(-1)

으아니.. 선택정렬이 원래 시간복잡도가 O(n^2) 이니까 당연히 느린건데 자꾸 시간초과 먹여가지고 열받았다.
결국 for문 하나를 줄여야겠다 싶어서 max값의 index를 찾는 부분을 A.index(max(A[:i+1])) 이걸로 줄여서 통과했다.

 

 

 

 

 

p.s.

혹시나 몰라서 이 풀이를 PyPy3로 수정해서 제출했더니 또 통과가 돼버렸다 ㄴㅇㄱ

pypy3가 python3에 비해 메모리를 많이 먹는 만큼 속도는 빠르다고 한다. 

pypy3는 JIT(Just In Time)컴파일을 도입한 것으로써 자주 쓰이는 코드를 캐싱하기 때문에 인터프리터보다 빠르다. (대신 그만큼 메모리를 많이 먹는다)

 

반복을 사용하는 경우에는 pypy3가 우세한 경우가 많다고 한다. 

pypy3와 python3에 대한 차이는 여기 글을 참고함