두 배열의 원소 교체

출처:: 국제 알고리즘 대회

 

1. 문제 이해 및 해결과정

 2번 풀이

 - 두 배열의 원소가 최대 백만개 100,000개 까지 입력될 수 있으므로O(NlogN)을 보장하는 정렬알고리즘을 이용해야한다.

 

2. 풀이방법

 1.  정렬 이용

#두 배열의 원소 교체
#
import sys
sys.stdin = open("input.txt","r")
n,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))


A.sort()
B.sort(reverse=True)

for i in range(k):
    if A[i]<B[i]:
        A[i],B[i]=B[i],A[i]
    else:
        break
print(sum(A))

 

3. 오답원인

 1. n이 커지면 풀릴지 모르겠다 - 안풀림

- 10억이면 1초 이상

O(n^2) = 100 000 * 100 000 = 10 000 000 000 백억이므로 2초안에 풀 수 없음 

#두 배열의 원소 교체
#
import sys
sys.stdin = open("input.txt","r")
n,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))


for i in range(k):
    minv= 2147000000
    maxv = -1
    for j in range(n):
        if minv>A[j]:
            minindex=j
            minv=A[minindex]
        if maxv < B[j]:
            maxindex=j
            maxv=B[maxindex]

    A[minindex],B[maxindex] = B[maxindex],A[minindex]

print(sum(A))

 

TIME 비교

4. 알게된 점