Wave Array문제의 자바 해결 방법: 효율적인 알고리즘

문제

Problem_Link

문제해결방법

• 주어진 값: 정렬된 어레이
• 조건: 웨이브 타듯 크고작고 크게 정렬
• 조건2: lexicographically smallest.

주어진 값과 조건의 관계를 생각해보았을떄, 조건자체를 검색할 필요없이 정렬된 어레이를 스왑해서 풀면 됨.

lexical이라는 뜻은 compareTo를 사용하라는 뜻임. compareTo는 유니코드를 기반으로 비교하기 떄문.

즉, 따로 무언가를 할필요가 없이. 정렬을 1/2만큼 돌면서 짝수의 이전 값과 스왑하면 됨.

시간복잡도: O(n), 공간복잡도: O(1)

class Solution {
    public static void convertToWave(int n, int[] a) {
        // 인덱스를 1부터 시작하고 2씩 증가시키면서
        // 현재 요소와 이전 요소를 교환합니다.
        for(int i = 1; i < n; i += 2){
            // 현재 요소와 이전 요소를 교환합니다.
            int temp = a[i];
            a[i] = a[i - 1];
            a[i - 1] = temp;
        }   
    }
}