Aracade Intro #12 SortByHeight

CodeFights, CodeSignal arcade #12 SortByHeight

 Rearrange the people by their heights in a non-descending order without moving the trees. ( -1 would be tree )

 입력받은 사람들의 키와 나무(-1) 값 배열에서, 나무값의 위치는 건드리지 않고 사람들의 키를 오름차순 정렬하라

e.g.

                     a = [-1, 150, 190, 170, -1, -1, 160, 180]

sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190]

함수를 통과하고 정렬된 값

//Process

//1. Input height vector

//2. Iterate from 1 to the end

// 2.1. Gather index in indexVector (If it's not a -1 height)

// 2.2. Iterate IndexVector all (Selection sort)

//  2.2.1. Sort indexVector and also heightVector using index

//3. Output heightVector

//처리과정

//1. 배열을 입력받는다 

//2. 1부터 indexes 의 length 만큼 반복한다.

// 2.1. -1 이 아닌 index 를 따로 배열로 모은다. (Normal height 의 index 배열을 만든다)

// 2.2. 정상 Index 배열의 길이만큼 반복한다. (선택정렬)

//  2.2.1. Index를 정렬하면서 출력vector 를 index에 맞추어 같이 정렬한다. 

//3. 입출력vector를 출력한다.

std::vector<int> sortByHeight(std::vector<int> heightVector) {

    int length = heightVector.size();

    int i = 0;

    

    std::vector<int> indexes;

    

    //Make index vector

    int temp;

    for (int i = 0; i < length; ++i) 

    {

        temp = heightVector.at(i);

        if (temp != -1) 

        {

            indexes.push_back(i);

        }

    }

    

    //Sort index vector and height vector // Selection sort

    length = indexes.size();

    

    int j;

    for (int i = 1; i < length; ++i) 

    {

        temp = heightVector.at(indexes.at(i));

    

        j = i - 1;

        bool isDone = false;

        while (j >= 0 && isDone == false) 

        {

            int frontTemp = heightVector.at(indexes.at(j));

            if (temp <= frontTemp) 

            {

                heightVector.at(indexes.at(j+1)) = frontTemp;

                heightVector.at(indexes.at(j)) = temp;

            }

            else 

            {

                heightVector.at(indexes.at(j+1)) = temp;

                isDone = true;

            }

            --j;

        }

    }

    return heightVector;

}

이 외에도...

2018/10/08 - [Algorithm/Code Signal (Code Fights)] - Aracade Intro #12 SortByHeight

2018/10/06 - [Algorithm/Code Signal (Code Fights)] - Aracade Intro #11 IsLucky

2018/10/03 - [Algorithm/Code Signal (Code Fights)] - Aracade Intro #10 CommonCharacterCount

2018/09/26 - [Algorithm/Code Signal (Code Fights)] - Aracade Intro #9 AllLongestStrings

2018/09/24 - [Algorithm/Code Signal (Code Fights)] - Aracade Intro #8 MatrixElementsSum

2018/09/23 - [Algorithm/Code Signal (Code Fights)] - Aracade Intro #7 AlmostIncreasingSequence

2018/09/22 - [Algorithm/Code Signal (Code Fights)] - Aracade Intro #6 MakeArrayConsecutive2

2018/09/21 - [Algorithm/Code Signal (Code Fights)] - Aracade Intro #5 ShapeArea

2018/09/19 - [Algorithm/Code Signal (Code Fights)] - Aracade Intro #4 AdjacentElementsProduct

2018/09/16 - [Algorithm/Code Signal (Code Fights)] - Aracade Intro #3 CheckPalindrome

2018/09/16 - [Algorithm/Code Signal (Code Fights)] - Aracade Intro #2 CenturyFromYear

2018/09/16 - [Algorithm/Code Signal (Code Fights)] - Aracade Intro #1 Add