myBlog

>>문제설명

leetcode.com/problems/average-of-levels-in-binary-tree/

>mySolution

class Solution {
    public double getAverage(LinkedList<TreeNode> linkedList){
        long sum = 0;
        for(TreeNode treeNode : linkedList){
            sum += treeNode.val;
        }
        return (double)sum / linkedList.size();
    }

    public List<Double> averageOfLevels(TreeNode root) {
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        LinkedList<TreeNode> nextList = new LinkedList<>();
        List<Double> answerList = new ArrayList<>();
        linkedList.add(root);

        while (!linkedList.isEmpty()){
            answerList.add(getAverage(linkedList));
            nextList.clear();
            while (!linkedList.isEmpty()){
                TreeNode treeNode = linkedList.poll();
                if(treeNode.left != null) nextList.add(treeNode.left);
                if(treeNode.right != null) nextList.add(treeNode.right);
            }
            linkedList.addAll(nextList);
        }

        return answerList;
    }
}

> Result

> Modify

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        List<Double> answerList = new ArrayList<>();
        linkedList.add(root);
        long sum;
        int size;

        while (!linkedList.isEmpty()){
            sum = 0;
            size = linkedList.size();
            for(int idx = 0; idx < size; idx++){
                TreeNode treeNode = linkedList.poll();
                sum += treeNode.val;
                if(treeNode.left != null) linkedList.addLast(treeNode.left);
                if(treeNode.right != null) linkedList.addLast(treeNode.right);
            }
            answerList.add((double)sum / size);
        }
        return answerList;
    }
}

>Result

leetCode 엔진 자체가 같은 코드를 넣어도 결과가 다르게 나온다는 점을 알았다.

문제 설명 보기

>> programmers.co.kr/learn/courses/30/lessons/43238

해당 문제의 핵심은 이것을 이분탐색법을 사용해 해결할 생각을 하는것이다.

문제가 설명한대로 실제 구현을 하게 되면 무조건 time out을 맞게 되어있다.

문제가 원하는 반환값은 시간이며, 시간은 항상 오름차순으로 정렬되어있다고 볼 수 있다.

이분탐색의 핵심인 정렬되어있는 숫자에서 탐색하는 범위를 절반으로 줄여 나가는 방법으로 O(logN)의 시간복잡도로 해결 할 수 있다.

> Solution

class Solution {
    public long solution(int n, int[] times){
        long left = 1;
        long right = (long)1000000000 * (long)1000000000;
        long mid = 0;
        long answer = 1;
        long sum;

        while( right > left ){
            mid = (left + right) / 2;
            sum = 0;
            for(int num : times){
                sum += mid / num;
            }
            if(sum >= n){
                answer = mid;
                right = mid;
            } else if (sum < n){
                left = mid + 1;
            }
        }

        return answer;
    }
}

* right는 입국 심사를 기다리는 10억명이 한명을 심사하는데 10억 분 걸리는 심사관 혼자서 심사하는 경우인, 가질 수 있는 가장 큰 숫자를 지정했다. Long.MAX_VALUE - 1을 사용해보았으나 아무래도 12번째 line에서 overflow가 발생하는 듯 싶어 이와같이 수정하였다.

C++에서 알고리즘 문제를 해결 할 때는 (x, y)형태의 좌표 또는 (시간, 거리) 등을 Pair 클래스를 유용하게 사용했다.

javafx에서 Java도 Pair 객체를 제공하지만 알고리즘 사이트의 컴파일러에서 제공해주지 않거나 해서 해당 클래스를 사용하지 못하게 될 경우 간단하게 Pair Class를 구현 할 수 있다.

private class Pair<L, R>{
    L left;
    R right;
    
    private Pair(L left, R right){
    	this.left = left;
        this.right = right;
    }
}

private 접근제한자로 만들면 다른 클래스에서 사용할 수 없으니 접근제한자는 필요에 따라 구분해준다.

이제 해당 객체를 List 객체를 사용해 관리한다면 다음과 같이 사용할 수 있다.

LinkedList<Pair<Integer, String>> pairArr = new LinkedList<>();

pairArr.add(new Pair<>(1,"aa"));
pairArr.add(new Pair<>(1,"ab"));
pairArr.add(new Pair<>(2,"ac"));
pairArr.add(new Pair<>(2,"ad"));
pairArr.add(new Pair<>(3,"ae"));
pairArr.add(new Pair<>(3,"af"));
pairArr.add(new Pair<>(4,"ag"));
pairArr.add(new Pair<>(4,"ah"));

여기서 LinkedList는 List를 조상 클래스로 두고 있으며 Collections.sort에서 List를 파라미터로 사용하므로 sort를 사용해 커스텀 객체를 편리하게 정렬 할 수 있다.

sort 메서드는 Comparable 인터페이스의 compareTo(Object o) 를 기본으로 사용하며, 파라미터로 Comparator 인터페이스의 구현체를 넘겨주는 방식으로 사용할 수 있다.

사용방법 첫번째는 Comparable 인터페이스를 구현하는 것이다.

private class Pair<L, R> implements Comparable{
    L left;
    R right;
    
    private Pair(L left, R right){
    	this.left = left;
        this.right = right;
    }
    
    public int compareTo(Object o){
    	return this.left != (Pair)o.left ? (Pair)o.left - this.left : (Pair)o.right.compareTo(this.right)); // 내림차순
    }
}

두번째 사용 방법으로 Collections.sort를 호출하여 파라미터에 Pair 객체를 넣어주고 Comparator를 익명 메서드로 작성하여 넣어서 사용해보자.

Comparator를 따로 작성해서 사용해도 된다.

Collections.sort(pairArr, new Comparator<Pair<Integer, String>>() {
	@Override
	public int compare(Pair<Integer, String> o1, Pair<Integer, String> o2) {
		return (o1.left != o2.left ? o2.left - o1.left : o2.right.compareTo(o1.right));
	}
});

위와 같이 Collections.sort를 사용하여 Pair의 left를 내림차순으로, Pair의 left가 같다면 right를 String compareTo를 사용해 사전 내림자순으로 정렬하였다.

해당 방법으로 Triple 등의 객체를 구현해 정렬하는 방법도 가능하며, sorting 알고리즘에 관련된 문제를 손쉽게 해결 할 방법이 될 수도 있다.

[결과]

----------정렬 전
[1, aa]
[1, ab]
[2, ac]
[2, ad]
[3, ae]
[3, af]
[4, ag]
[4, ah]
----------정렬 후
[4, ah]
[4, ag]
[3, af]
[3, ae]
[2, ad]
[2, ac]
[1, ab]
[1, aa]