[hackerrank] hackerrank challenges Day 14 자바 코드 리뷰

 

14일차 코드 리뷰를 진행해보자.

 

Day 14 결과

 

 

금일 문제는 백준에서 흔히 풀어보던

최댓값 구하는 스타일이라

딱히 어렵지 않게 해결할 수 있었으나

필자의 코드가 알고리즘적으로

최선의 코드는 아닌 것 같아

인터넷을 검색하다 훨씬 간결하고 좋은 알고리즘을 발견해

공유해보려고 한다.

 

그럼

우선 필자가 작성한 코드부터 살펴보자!

 

---

 

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;


class Difference {
    private int[] elements;
    public int maximumDifference;

    int max = 0;
    int diff = 0;

    // Add your code here
    public Difference(int[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length; j++) {
                if (a[i] > a[j]) {
                    diff = a[i] - a[j];
                } else {
                    diff = a[j] - a[i];
                }
                if (diff > max) {
                    max = diff;
                }
            }
        }
    }

    public void computeDifference() {
        maximumDifference = max;
    }

} // End of Difference class

public class Test {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        Difference difference = new Difference(a);

        difference.computeDifference();

        System.out.print(difference.maximumDifference);
    }
}

 

 

우선 이 문제의 경우

필자가 처음 생각했을 때

'조합(Combination)'을 써야한다고 생각했다.

 

조합이 무엇인가?

예를 들어보자.

 

 

array a가 다음과 같다고 생각해보자.

예시 설명 1

 

그럼 위와 같이 3번 값을 비교하면 될 것이고

 

 

array a가 다음과 같이 4개의 값을 가지면

예시 설명 2

 

위와 같이 6번 비교하면 된다!!

 

이렇게 n개의 값 중에서

a개의 묶음으로 값을 뽑아 내는 방법이

'조합(Combination)'이다!

 

허나 필자는 조합만 하면 되는 문제에서

이중 for문을 통해 순열을 썼다.

 

순열은 순서있는 나열으로

조합과 비교하면 다음과 같이 비교된다.

순열과 조합 비교

 

필자 알고리즘의 문제점

 

즉 현재 필자의 알고리즘이

같은(arr a의 값을 비교해 차이를 구하는) 과정을 2번씩 반복 진행하고 있다는 단점이 있다.

 

문제의 요지는 arr a의 모든 값들과 차이를 비교해

가장 큰 차이의 절댓값을 출력하면 되므로

필자의 알고리즘이 '틀린' 알고리즘은 아니지만

그닥 효율적인 알고리즘은 아니었다.

 

그럼 좀 더 효율적인 코드는 어떤 것이 있을까? 🤔

 

 

---

 

두 번재 풀이 방법은

 위에서 말했다 싶이 필자가 인터넷에서 찾아온 풀이 방법이다.

 

링크와 출처를 명백히 밝히고

해당 코드에 대해서도 소개하겠다.

 

링크 및 출처 : https://www.youtube.com/watch?v=TxBwY03ZiNs 

 

소스 코드를 보자.

 

import java.util.Arrays;
import java.util.Scanner;

class Difference {
    private int[] elements;
    public int maximumDifference;

    public Difference(int[] elements) {
        this.elements = elements;
    }

    public void computeDifference() {
        Arrays.sort(elements);
        maximumDifference = elements[elements.length-1]-elements[0];
    }
}
public class Test2 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        Difference difference = new Difference(a);

        difference.computeDifference();

        System.out.print(difference.maximumDifference);
    }

}

 

아주 간단하게 풀 수 있었다!!

 

Arrays.sort();를 이용해

Arrays를 정렬하고

마지막 인덱스 arrays의 값에서 arrays[0] 값을 빼주면 되었다!

 

값 비교에서는 Arrays.sort()가 기본인데

왜 정렬할 생각을 못했을까,,

 

그래도 하나 알아가니 긍정적으로 생각해야겠다!!

 

 

---

 

 

오늘 포스팅의 경우

순열,조합 설명 및

필자 알고리즘의 문제점도 함께 설명하다보니

포스팅 내용이 좀 길어졌다.

 

열심히 설명한 만큼

많은 독자분들이 이해하셨으면 좋겠다!!

 

그럼 내일 Day 15 챌린지로 다시 만나자. 🔥