백준 1083번 - 소트 (C++)

해결 방법

일단 문제 해설이 굉장히 난해한데 예제마저 겁나 대충줘서 이해하는데 상당히 애먹었다.
예제 보고 처음엔 그냥 앞에서 부터 n번 버블정렬 하는 문제인줄..
"사전순으로 가장 뒷서는 것"이라는 표현을 처음 봤는데 그냥 맨 큰 숫자가 맨 앞에 오라는 말이였다.
질문 게시판 보면 "사전순이면 10보다 작지만 맨 앞자리가 더 큰 9 10 9가 10 9 9보다 앞 아닌가요?" 라고 하던데 맞는말 아닌가? 싶다. 문제에 간단한 예시나 풀어서 설명을 조금 해줬으면 좋았을텐데 넘 아쉽...

암튼 결론은 현재 교환 가능한 범위 이내에서 맨 앞으로 옮길 수 있는 가장 큰 숫자를 옮기면 된다. = 그리디

아쉬웠던 점

간만에 해서 입출력 테스트 하려고 cin 아래에 바로 cout << count 해줬었는데,
까맣게 잊고 테스트 케이스 넣으면서도 음.. rider에서는 처음 입력된 값이 한번 출력되는 버그가 있네....
하면서 진행. 결과는....

분명 맞는데 왜 입구컷이 나냐고!!!!

분명 테스트 케이스 다 맞는데 계속 입구컷나서 넘 당황.. 실수는 실력이다...
괴상한 실수 하지 맙시다.. 

코드

배열 크기 최대가 50이라 사실 그냥 매번 버블소트 해주면서 풀어도 상관없지만, 정렬문제를 매번 정말 정렬 해주면서 풀면 나중가면 시간초과로 막혀서 고생하는 일이 많아 미리미리 연습하기 위해 정렬하며 풀지는 않았다.
그래서 이 방법이 깔끔하다고 생각하진 않지만 반환용 returnNumbers를 하나 만들어서 정렬된 값은 해당 배열에 앞에서부터 채워넣고, 기존 배열에서는 -1로 수정하여 스킵하여 계산할 수 있도록 코드를 짰다.

#include <iostream>
using namespace std;
 
int main(int argc, char* argv[])
{
    int count, changeCount;
    cin >> count;
    
    int numbers[50], returnNumbers[50];
    for (int i = 0; i < count; i++)
        cin >> numbers[i];
        
    cin >> changeCount;
 
    int Start = 0;
    while (changeCount > 0 && Start < count-1)
    {
        int max, maxIndex, numCount= 0, c = 0;
 
        //가장 앞의 원소로 미리 사전 세팅
        for (int i = 0; i < count; i++)
        {
            if (numbers[i] != -1)
            {
                maxIndex = i;
                max = numbers[i];
                break;
            }
        }
 
        // 남은 교환횟수 이내에서 맨 앞으로 끌어올 수 있는 가장 큰 수 찾기.
        int passCount = 0; 
        for(int i = 0; i < (changeCount+passCount+1 > count ? count : changeCount+passCount+1); ++i)
        {
            if(numbers[i] == -1)
            {
                passCount++; // 이미 -1인 칸은 스킵하고 해당 칸 수 만큼 추가로 탐색.
                continue;
            }
            
            if(max < numbers[i])
            {
                c = numCount;
                max = numbers[i];
                maxIndex = i;
            }
            numCount++;
        }
 
        returnNumbers[Start] = numbers[maxIndex];
        numbers[maxIndex] = -1;
        changeCount-=c;
        Start++;
    }
    
    for (int i = 0; i < Start; i++)
        cout << returnNumbers[i] << " ";
    for (int i = 0; i < count; i++)
        if(numbers[i] != -1)
            cout << numbers[i] << " ";
    
    return 0;
}