[HackerRank] Lily's Homework (Java)

해커랭크에 있는 Lily's Homework 문제에 대해 정리해보려고한다.

어떤 알고리즘을 써야 적합한지에 대해서는 생각해냈지만, 구현방식을 생각해내지 못해 몇개의 테스트케이스에서 시간초과가 났다.

 

 

해결 과정

먼저, 문제를 읽고 도출해야하는 것이 크게 두가지라고 생각한다.

1. "인접한 인덱스의 원소의 차가 가장 작게 만들어야한다" -> 오름차순이나 내림차순으로 정렬이 되어야한다는 말이다.

2. "두 인덱스를 최소 횟수로 swap하여 1번 상태를 만들어야한다." -> 정렬 방법 중에 선택 정렬을 한다.

 

그런데,

선택 정렬은 시간복잡도가 O(N^2)이다.

기준 인덱스를 모두 도는 것이 (N) * 나머지 인덱스 중에 가장 작거나 큰 값 찾기 (N-1)

이 문제의 N의 최대값은 10^5이기 때문에 시간초과가 나게된다.ㅠㅠ

 

여기까지 당연히 예상은 했지만, 어떻게 구현을 해야 막을 수 있을지를 생각해내지 못했다.

결국 구글링을 했고,

여기서 깨달은 것은 꼭 다 정렬을 해야하는 것이 아닌, 스왑 횟수만 알면 되기 때문에

가장 작은 값을 찾는 부분을 시간복잡도를 줄이면 될 것이라는 것을 알았다.

 

나머지 인덱스를 모두 돌면서 가장 작은 값을 찾을 것이 아니라, 

자료구조 트리맵을 사용하여 가장 작은 값의 값과 인덱스를 바로 알 수 있게하면 된다.

맵의 key는 리스트의 값을 넣고, value는 해당 인덱스를 넣고 트리맵을 이용하여 정렬을 하면 된다.

 

 

이후에 트리맵을 돌면서 인덱스 0부터 비교를 해주고,

인덱스가 같지 않다면 swap해줘야하기 때문에 카운팅을 해준다.

트리맵을 돌면서 get()을 하는것은 O(logN)이기 때문에 총 시간복잡도는 O(N^2)가 아니라 O(NlogN)이 된다.

 

물론, 오름차순이 스왑횟수가 적은지 내림차순이 적은지는 둘다 해본 후에 비교해야한다.

 

 

결과 코드

import java.io.*;
import java.util.*;
import java.util.Map.Entry;
import java.util.stream.*;
import static java.util.stream.Collectors.toList;

class Result {
    public static int lilysHomework(int n, List<Integer> arr) {
        int cnt1 = countSwap(new ArrayList<>(arr), Comparator.naturalOrder());
        int cnt2 = countSwap(new ArrayList<>(arr), Comparator.reverseOrder());
        return Math.min(cnt1, cnt2);
    }

    private static int countSwap(List<Integer> arr, Comparator<Integer> comparator) {
        Map<Integer, Integer> sortedMap = new TreeMap<>(comparator);

        for(int i = 0; i< arr.size(); i++) {
            sortedMap.put(arr.get(i), i);
        }

        int left = 0, cnt = 0;
        for (Entry<Integer, Integer> en : sortedMap.entrySet()) {
            int idx = en.getValue();

            if(idx != left) {
                int tmp = arr.get(idx);
                arr.set(idx, arr.get(left));
                sortedMap.put(arr.get(left), idx);
                arr.set(left, tmp);
                cnt++;
            }
            left++;
        }
        return cnt;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                .map(Integer::parseInt)
                .collect(toList());

        int result = Result.lilysHomework(n, arr);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

내림차순, 오름차순은 TreeMap을 선언할때 인수로 Comparator 지정해주는부분만 다르고

나머지 코드는 동일하기 때문에 메서드를 따로 빼고, Comparator 종류만 매개변수로 지정해주는 것으로 하여 중복코드를 없앴다.

 

 

 

느낀점

최근에 알고리즘 정렬들의 이론적인 복습을 했었는데,

그게 선택정렬을 떠올리게 한 것 같다.

역시나 cs에 대한 끊임없는 학습은 중요하다고 생각했고,

선택정렬이 O(N^2)라는 생각에만 갇혀있지말고, 위 문제처럼 응용할줄도 알아야겠다고 생각했다.