Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees. People can be very tall!

Example

For a = [-1, 150, 190, 170, -1, -1, 160, 180], the output should be

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

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] array.integer a

  If a[i] = -1, then the ith position is occupied by a tree. Otherwise a[i] is the height of a person standing in the ith position.

  Guaranteed constraints:

  1 ≤ a.length ≤ 1000,

  • 1 ≤ a[i] ≤ 1000.

• [output] array.integer

  Sorted array a with all the trees untouched.

풀이

• -1 이 존재하는 인덱스는 -1 이 필
• -1 이 아닌 자리의 수는 정렬하여 차례대로 수 지정

int[] solution(int[] a) {
    // -1 이 존재하는 위치를 고정시키기 위한 배열 생성
    int [] result = new int [a.length];
    
    // -1 위치 지정
    for (int i = 0; i < result.length; i ++) {
        if (a[i] == -1) result[i] = -1;
    }
    
    // 파라미터 배열 정렬
    Arrays.sort(a);
    
    // 정렬된 배열을 탐색할 인덱스 설정
    int idx = 0;
    
    // 순회시작
    for (int i = 0; i < result.length; i++) {
        // -1 고정 배열의 원소가 -1 이면 다음 단계로
        if (result[i] == -1) continue;
        
        // -1 보다 크면 while 반복시작
        while (true) {
            // 정렬된 배열의 원소가 -1 이 아니라면
            if (a[idx] > -1) {
                // result 배열에 값 추가
                result[i] = a[idx ++];
                // while 탈출
                break;
            }
            
            // 인덱스 증가
            idx ++;
        }
    }
    
    return result;
}