MEASURETIME 문제에서 삽입정렬 알고리즘 개선이 어디까지 되는건가요?

  • 정용진
    정용진

    for(int l=1;l {
    int nBase = vecRamdomData[l];
    int m = l;
    while(m > 0 && vecRamdomData[m-1] > nBase)

    {
    nInsertionCount++;
    vecRamdomData[m] = vecRamdomData[m-1];
    --m;
    }

    if(l == m) continue;                
    vecRamdomData[m] = nBase;

    // for(int m=0;m // {
    // if(pRamdomData[m] > pRamdomData[l])
    // nInsertionCount++;
    // }
    }

    시간초과로 실패를 하고 있습니다.
    입력시 시간이 많이 걸릴수 있다하여 cin에서 scanf로 변경했습니다.
    그래도 시간초과가 떠서 결국 삽입정렬 알고리즘 때문인거 같아
    알고리즘을 개선할려고 합니다.
    위에 코드가 삽입정렬 알고리즘 코드인데 저기서 더 발전할 가능성이
    있을까요?
    힌트라도 부탁드립니다.
    *문제의 접근방식 문제인거 같기도한데... 정렬을 하는게 아니라
    카운트에 집중해야하는걸까요... 그래도 정렬이 진행되야.. 카운트가
    나오는게 아닐찌;;


    9년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    직접 정렬하시는 방식으로는 시간 내에 푸실 수 없습니다. 다른 방법을 사용하셔야 합니다.


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.