(24060) 알고리즘 수업 - 병합 정렬 1

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

단계별로 풀어보기

19단계(재귀) 4번째

 

 

 

N은 최대 50만이고 병합 정렬은 O(N log N)이므로 연산 횟수는 많아야 천만 번이다. k의 범위가 1억이긴 하지만 실제로는 1억 번 연산할 리가 없다는 것이다.

흔히 PS환경에서 연산 1억 번을 1초로 계산해서 k가 1억이라고 해도 실제로 그만큼 돌지 않는다는 것을 깨닫는 것이 출제 의도인지는 모르겠지만, 요즘은 컴파일러 성능이 좋고 가벼운 연산이 많아서 사실 진짜 1억번 돌아가는 코드라 해도 (N의 범위가 약 450만) 1초 이내에 돌아갈 가능성이 높다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, k;
  
  cin >> n >> k;
  
  vector<int> A(n), tmp(n);
  
  for(int i=0;i<n;i++)  cin >> A[i];
  
  auto merge= [&](int p, int q, int r){
    int i= p, j= q+1, t= 0;
    
    while(i<=q && j<=r){
      if(A[i]<=A[j])  tmp[t++]= A[i++];
      else  tmp[t++]= A[j++];
    }
    
    while(i<=q)  tmp[t++]= A[i++];
    while(j<=r)  tmp[t++]= A[j++];
    
    i= p, t= 0;
    while(i<=r){
      k--;
      if(k==0){
        cout << tmp[t];
        exit(0);
      }
      A[i++]= tmp[t++];
    }
  };
  
  auto merge_sort= [&](auto& self, int p, int r) -> void {
    if(p<r){
      int q= (p+r)/2;
      
      self(self, p, q);
      self(self, q+1, r);
      merge(p, q, r);
    }
  };
  
  merge_sort(merge_sort, 0, n-1);
  
  if(k>0)  cout << -1;
  
  return 0;
}