TigerCow.Door

안녕하세요. 문범우입니다.

이번에는 Hackerrank의 문제를 풀어보았습니다.

문제 이름은 Lily's Homework이며 Medium 난이도에 속해있습니다.

생각외로 rate가 47% 정도로 좀 낮은편 입니다.

해당 문제는 아래 주소에서 풀어보실 수 있습니다.


https://www.hackerrank.com/challenges/lilys-homework/problem


코드에 주석을 통해 설명을 덧붙여 놓았기 때문에 추가적인 설명은 생략하겠습니다.

해당 코드는 아래 github 주소에서도 확인할 수 있습니다.


https://github.com/doorBW/algorithm_practice


보다 궁금한 점이 있으신 분들은 댓글 및 이메일, 카카오톡을 통해 연락주시면 바로 답변드리도록 하겠습니다 :)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
public class Solution {
    static int lilysHomework(int[] arr) {
        // arr을 오름차순 또는 내림차순의 형태로 만들어야 한다.
        // 그때가 문제에서 말한 cost가 가장 적은 경우기 때문에,
        // 이때 문제는, arr을 오름차순으로 만드는데 필요한 swap횟수와
        // arr을 내림차순으로 만드는데 필요한 swap횟수가 다르다.
        // 따라서 오름차순 및 내림차순 두 방법 모두 시행하고 그 중 작은 값을 반환한다.
 
        int answer_asc = 0;
        int answer_desc = 0;
        int idx,temp;
        int arr_length = arr.length;
        // 기존 arr은 오름차순에서 사용될 것
        // 내림차순에서 사용될 arr_desc을 만들고 기존 arr을 복사해서 넣는다.
        int[] arr_desc = new int[arr_length];
        System.arraycopy( arr, 0, arr_desc, 0, arr_length );
 
        // 오름차순으로 정렬된 sorted_arr
        int[] sorted_arr = new int[arr_length];
        System.arraycopy( arr, 0, sorted_arr, 0, arr_length );
        Arrays.sort(sorted_arr);
        
        // 내림차순으로 정렬된 reversed_arr
        int[] reversed_arr = new int[arr_length];
        for(int i=0;i<arr_length;i++){
            reversed_arr[i] = -1 * arr[i];
        }
        Arrays.sort(reversed_arr);
        for(int i = 0; i < arr_length; i++){
            reversed_arr[i] *= -1;
        }
        
        // 오름차순을 위한 hash map
        HashMap<Integer, Integer> idxMap_asc = new HashMap();
        for(int i=0;i<arr_length;i++){
            idxMap_asc.put(arr[i],i);
        }
 
        // 내림차순을 위한 hash map
        HashMap<Integer, Integer> idxMap_desc = new HashMap();
        for(int i=0;i<arr_length;i++){
            idxMap_desc.put(arr_desc[i],i);
        }
        
        // 오름차순을 통한 cost 계산
        for(int i=0;i<arr_length;i++){
            if(sorted_arr[i] != arr[i]){
                idx = idxMap_asc.get(sorted_arr[i]);
                idxMap_asc.put(arr[i],idx);
                temp = arr[i];
                arr[i] = sorted_arr[i];
                arr[idx] = temp;
                answer_asc++;
            }
        }
 
        // 내림차순을 통한 cost 계산
        for(int i=0;i<arr_length;i++){
            if(reversed_arr[i] != arr_desc[i]){
                idx = idxMap_desc.get(reversed_arr[i]);
                idxMap_desc.put(arr_desc[i],idx);
                temp = arr_desc[i];
                arr_desc[i] = reversed_arr[i];
                arr_desc[idx] = temp;
                answer_desc++;
            }
        }
        
        // 더 작은값을 반환한다.
        return answer_asc > answer_desc ? answer_desc : answer_asc;
    }
 
    private static final Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
 
        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
        int[] arr = new int[n];
 
        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
 
        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }
 
        int result = lilysHomework(arr);
 
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
 
        bufferedWriter.close();
 
        scanner.close();
    }
}
 
cs


'Algorithm > Java 풀이' 카테고리의 다른 글

JAVA #3_ The Grid Search  (0) 2018.08.08
JAVA #2_ Lily's Homework  (0) 2018.08.05
Java #1_ 가장 긴 팰린드롬 길이 구하기  (0) 2018.07.12
블로그 이미지

Tigercow.Door

Data-Analysis / AI / back-end / Algorithm / DeepLearning / etc