개발자 Lim

<아이디어>

해당 문제의 핵심은 가변적으로 변하는 배열에서 높은 값을 가지는 것을 가져오는 걸 반복해야 한다는 점 이다.

처음에는 자동으로 값을 내림차순으로 정렬해주는 TreeSet<Integer>을 생각했으나 중복된 값이 제거 된다는 문제점이 있어 그 대안으로 조건식에 따라 값을 정렬해서 저장하는 PriorityQueue 우선순위 큐를 생각 할 수 있었다.

<우선 순위 큐>

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

<정답 코드>

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pQueue = new PriorityQueue<>(Collections.reverseOrder());
        for (int stone : stones)
            pQueue.add(stone);
        while(pQueue.size()>1){
            int stone1 = pQueue.remove();
            int stone2 = pQueue.remove();
            int newStone = Math.abs(stone1-stone2);
            if(newStone!=0)
                pQueue.add(newStone);
        }
        return pQueue.size()==0?0: pQueue.peek();
    }
}

의역: 오름차순으로 정렬되어 있는 정수 배열 arr와 정수 k가 주어질 때 자연수 1부터 해당 배열의 요소들을 제외하고 카운트 할때 k번째로 오는 수를 구하라.  

풀이:

1. 자료구조 Set 사용

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public int findKthPositive(int[] arr, int k) {
        HashSet<Integer> map = new HashSet<Integer>();
        int count = 0; int checker = 0;
        for (int unit:arr)
            map.add(unit);
        while(checker!=k)
            if(!map.contains(++count))
                checker++;

        return count;
    }
}

2. OnePass 알고리즘 

class Solution {
    // 시간 복잡도 O(n)
    public int findKthPositive2(int[] arr, int k) {
        for (int i : arr) {
            if (i <= k) k++;
            else break;
        }
        return k;
    }
}

3. 이진 탐색 활용

class Solution {
    // 시간 복잡도 O(log n) 공간복잡도 O(1)
    // 배열 범위 내부에서 k보다 작은 것이 있다면 카운트++ 그러나 카운트가 증가하면서 새롭게
    // 배열 범위 내부에서 작은 값이 생긴다면 카운트++
    public int findKthPositiveOtimal(int []arr, int k){
        int start = 0; int end = arr.length;
        // 해당 이진 탐색으로 찾는 것 -> 1부터 카운트 하며 k까지 증가 할때 해당 값이 k보다 작아 지는
        // 수 들의 갯수
        while(start<end){
            int mid = (start+end)/2;
            // 해당 식을 통해 arr[mid]의 값이 최종적으로 카운트 했을 때의 값보다 작아짐을 확인 가능
            if(arr[mid]-mid-1<k)
                start = mid+1;
            else
                end = mid;
        }
        return k+start;
    }
}

조건:

• 0 <= low <= high <= 10^9

의역: 두 정수를 포함한 사이의 홀 수의 개수를 반환하라.

풀이:

1. 단순 반복 (Time out)

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(1)
    public int countOddsFail(int low, int high) {
        int ans=0;
        for(int i=low;i<=high;i++){
            if(i%2==1) ans++;
        }
        return ans;
    }
}

2. 수학의 경우의 수 

class Solution {
    // 시간 복잡도 O(1) 공간 복잡도 O(1)
    public int countOdds(int low, int high) {
        if(low==high) return low%2==1?1:0;
        int ans = 0;

        if(low%2==0&&high%2==0){
            ans = (high-low)/2;
        }
        else if(low%2==1&&high%2==1){
            ans = (high-low)/2+1;
        }
        else{
            ans = (high-low-1)/2+1;
        }

        return ans;
    }
}

2-1 좀 더 최적화

class Solution {
    // 시간 복잡도 O(1) 공간 복잡도 O(1)
    public int countOddsOtimal(int low, int high){
        // low가 짝수라면 홀수로 바꾸기
        // 어차피 짝수는 no Count 이기 때문에 정답에는 영향을 미치지 않음
        if((low&1)==0){
            low++;
        }

        // 만약 low와 hight둘다 짝수였다면 0이 나오고 그것이 아니라면
        // 둘다 홀수 임으로 두 수 사이의 범위/2 +1 법칙이 성립
        return low>high?0:(high-low)/2+1;
    }
}

<메모>

최대한 나올 수 있는 경우의 수를 공통의 경우로 만들어 줄이자. 

조건:

• 0 <= n <= 30

의역: 피보나치 수를 반환하라 

피보나치 수: 제0항을 0, 제1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 놓는다. 1번째 수를 1로, 2번째 수도 1로 놓고, 3번째 수부터는 바로 앞의 두 수를 더한 수로 정의하는 게 좀더 흔하게 알려져 있는 피보나치 수열이다.

출처: 나무위키

풀이:1. 반복문 사용

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(1)
    public int fib(int n) {
        if(n==0||n==1) return n;
        int first = 0;
        int second = 1;
        int thAns=0;
        for(int i=0;i<n-2;i++){
            thAns = first+second;
            first = second;
            second = thAns;
        }

        return thAns;
    }
}

2. 재귀 사용

class Solution {
    // 시간 복잡도 O(2^n) 공간 복잡도 O(n)
    public int fibRecursive(int n){
        if(n==0||n==1) return n;

        int fnm1 = fibRecursive(n-1);
        int fnm2 = fibRecursive(n-2);

        return fnm1+fnm2;
    }
}

재귀 함수의 시간복잡도에 관한 다른 설명 영상: https://www.youtube.com/watch?v=VcCkPrGaKrs 

fibRecursive 함수 자체의 시간 복잡도를 T(n) 라고 가정 할 때 T(n) = T(n-1) + T(n-2) -> 2T(n-1) 

T(n) = 2 * T(n-1) <근사치>

2 * T(n-1) = 2^2 * T(n-2)  <n -> n-1 대입>

... 반복

2^n-2 * T(2) = 2^n-1 * T(1) 이때 T(1)은 O(1) 임으로

T(2) = 2 (해당 과정 반복)

2^n-3 * T(3) = 2^n-2 * T(2) -> 2^n-2 * 2 -> 2^n-1

T(3) = 2^2

2^n-4 * T(4) = 2^n-3 * T(3) -> 2^n-3 * 2^2 -> 2^n-1

T(4) = 2^3

...

T(n) = 2^n-1 <근사치> -> 2^n

따라서 시간 복잡도는 O(2^n)

3. 동적 프로그래밍 DP

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public int fibDp(int n){
        return fibDp(n,new int[n]);
    }
    public int fibDp2(int n){
        int fb[] = new int[n+1];
        fb[0] = 0;
        fb[1] = 1;
        for(int i=2;i<fb.length;i++)
            fb[i] = fb[i-1]+fb[i-2];
        return fb[n];
    }
}

4. 추후 업데이트 2차원 배열을 이용하여 O(log n)의 시간 복잡도 

class Solution2 {
    //**Time:O(logn)**  //(matrix size is 2*2(constant) so multiplication of matrix will take 2^3
    // time 8 which is constant. overall  Time compexity  :8logn which is Big O(logn) )
    //**Space :O(1)**//constant space (matrix size is fix 2*2 so space is constant)
    public int fib(int N) {
        if(N==0) return 0;
        int[][] matrix={{1,1,},{1,0}};

        int[][] identity={{1,0,},{0,1}};
        while(N!=1){
            if((N&1)!=0){
                identity=multiplication(matrix,identity);
                N--;
            }
            matrix=multiplication(matrix,matrix);
            N>>=1;
        }
        matrix=multiplication(matrix,identity);

        return matrix[1][0];
    }

    public static int[][] multiplication(int[][] matrix,int[][] res){
        int[][] ans=new int[2][2];

        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix.length;j++){

                for(int k=0;k<matrix.length;k++){
                    ans[i][j]+=matrix[i][k]*res[k][j];
                }

            }
        }
        return ans;
    }
}

<메모>

피보나치 수를 구하는 코드 중 가장 빠른 시간 복잡도는 O(log n)이다. 

Constraints:

• 1 <= num <= 108

의역: 정수 num이 Perfect Number 이면 true 아니면 false 를 반환하라

Perfect Number 란?: 자기 자신을 제외한 약수(진약수)들의 합이 자기 자신이 되는 수를 말한다. 예를 들어, 6의 약수는 자기 자신인 6을 제외한 1, 2, 3이고 진약수들의 합은 1 + 2 + 3 = 6, 즉 자기 자신이므로 6은 완전수이다.

예시 1: 28의 약수는 1, 2, 4, 7, 14, 24 여기서 24를 제외한 나머지 숫자들의 합으로 28을 만들 수 있으므로 true 

예시 2: 7의 약수는 1, 7 여기서 7을 제외한 남은 숫자 1만으로는 만드는 것이 불가능 하므로 false

풀이:

1. 브루트 포스 (time over)

class Solution {
	// 시간 복잡도 O(n) 공간 복잡도 O(1)
    public boolean checkPerfectNumberTimeOver1(int num) {
        int save = num;
        for(int i=1;i<num;i++){
            if(num%i==0)
                save-=i;
        }
        return save==0;
    }
}

2. 브루트 포스 최적화 (time over)

class Solution {
	// 시간 복잡도 O(n) 공간 복잡도 O(1)
    public boolean checkPerfectNumber(int num) {
        int save = num;
        for(int i=1;i<=num/2;i++){
            if(num%i==0)
                save-=i;
            if(save<0)
                return false;
        }
        return save==0;
    }
}

 3. 브루트 포스 더 최적화 

class Solution {
    // 시간 복잡도 O(루트n) 공간 복잡도 O(1)
    public boolean checkPerfectNumberClear(int num) {
        if(num==1) return false;
        int save = num;
        for(int i=1;i*i<=num;i++) {
            if (num % i == 0) {
                save -= i;
                if (i * i != num&&i!=1)
                    save -= num / i;
            }
        }
        return save==0;
    }
}

4. 유클리드 오일러 정의 이용 

https://en.wikipedia.org/wiki/Perfect_number

조건:

• n == score.length
• 1 <= n <= 104
• 0 <= score[i] <= 106
• All the values in score are unique.

의역: 각 고유한 값을 가진 정수형 배열이 들어올 때 해당 배열의 인덱스에 맞추어서 1등이면 Gold Medal 2등이면 Silver Medal 3등이면 Bronze Medal 그 외라면 각 순위를 문자열로 담은 문자열 배열을 반환하라.

풀이:

1. 단순 반복

class Solution {
    // 시간 복잡도 O(n^2) 공간 복잡도 O(n)
    public String[] findRelativeRanks(int[] score) {
        String price[] = {"Gold Medal","Silver Medal","Bronze Medal"};
        int indexHighArray[] = new int[score.length];
        String ans[] = new String[score.length];

        for (int i=0;i<score.length;i++){
            int tmp = -1; int index=0;
            for(int j=0;j< score.length;j++){
                if(tmp<score[j]){
                    tmp = score[j];
                    index = j;
                }
            }
            score[index] = -1;
            indexHighArray[i] = index;
        }
        // 만들어 진 것 크기가 큰 수 부터 내림 차순의 인덱스 배열
        for(int i=0;i<score.length;i++){
            if(i<3)
                ans[indexHighArray[i]]=price[i];
            else
                ans[indexHighArray[i]]=(i+1)+"";
        }
        return ans;
    }
}

예상외로 모든 풀이 중 가장 사용 메모리가 적었다.

2. TreeSet, Map 자료구조 활용

import java.util.HashMap;
import java.util.Iterator;
import java.util.TreeSet;

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public String[] findRelativeRanks1(int[] score) {
        String price[] = {"mask","Gold Medal","Silver Medal","Bronze Medal"};
        String ans[] = new String[score.length];
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        TreeSet<Integer> tset = new TreeSet<Integer>();
        // TreeSet을 활용하여 자동 정렬
        for (int num:score)
            tset.add(num);

        Iterator<Integer> it = tset.iterator();
        // map에 key를 배열의 값 value를 배열에서의 값의 순위 정보 저장
        int order = score.length;
        while(it.hasNext()){
            int key = it.next();
            map.put(key,order--);
        }
        // Map에 저장된 순위 정보를 불러와 ans 배열 생성
        for(int i=0;i<score.length;i++){
            int value = map.get(score[i]);
            if(value<=3)
                ans[i]=price[value];
            else
                ans[i]=(value)+"";
        }
        return ans;
    }
}

확실히 시간 복잡도를 O(n^2)을 O(n)으로 줄이니 속도가 개선된 모습 

+ 아래 함수들을 TreeMap 대신 사용하면 더 빠르게 개선이 가능

int[] copy = score.clone();
Arrays.sort(copy);

3. 기수 정렬 이용 Map을 긴 배열로 대체 

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public String[] findRelativeRanks2(int[] score){
        int peapleNum = score.length;
        String[] ans = new String[peapleNum];
        int max = 0;
        for (int num: score)
            max = max<=num? num:max;
        int scoreArray[] = new int[max+1];

        // 가장 큰 수+1 만큼의 길이의 배열을 만들고 각 해당하는 수의 인덱스에 순위정보 저장
        for(int i=0;i<score.length;i++)
            scoreArray[score[i]] = i+1;

        int rank = 1;
        for(int i=scoreArray.length-1;i>=0;i--){
            if(rank> peapleNum) break;
            // scoreArray 배열에서 score 배열에 있는 수 만을 활용 하게끔 하는 조건
            // 자바에서 정수형 배열은 생성 후 따로 값을 초기화 하지 않으면 자동으로 0
            if(scoreArray[i]>0){
                switch (rank){
                    case 1:ans[scoreArray[i] - 1] = "Gold Medal";rank++; break;
                    case 2:ans[scoreArray[i] - 1] = "Silver Medal";rank++; break;
                    case 3:ans[scoreArray[i] - 1] = "Bronze Medal";rank++; break;
                    default: ans[scoreArray[i]-1] = rank+""; rank++; break;
                }
            }
        }
        return ans;
    }
}

메모: 가급적 만들 수 있는 자료구조를 사용하지 않고 해결이 가능하다면 사용하지 말고 풀이 해볼 것

의역: 정수를 7진법으로 바꾼 문자열을 반환해라

(주의점: 실제 진법에서 음수는 보수로 처리하는데 해당 문제에서는 단순히 앞에 - 붙인 걸로 음수를 처리 함) 

풀이:

재귀 함수 사용

(기억해야 할 내용 재귀는 스택과 같이 제일 먼저 호출한 내용을 제일 마지막으로 처리한다.) 

즉 7^0 부터 나누는 것을 처음으로 호출하고 7^i 까지 나누는 걸 호출 한다면

7^i 부터 처리하고 7^0을 마지막으로 처리한다. 

class Solution {
    // 시간 복잡도 O(log7 n) 공간 복잡도 O(1)
    private StringBuilder ans = new StringBuilder();
    private int recusiveNum;
    private void helper(int i){
        int divisor = (int)Math.pow(7,i);
        if(recusiveNum<divisor)
            return;
        helper(i+1);
        int highDigit = recusiveNum/divisor;
        recusiveNum %= Math.pow(7,i);
        ans.append(highDigit);
    }
    public String convertToBase7(int num) {
        if(num==0) return "0";
        recusiveNum = Math.abs(num);
        helper(0);
        if(num<0)
            ans.insert(0,"-");
        return ans.toString();
    }
}

최적화 

class Solution {
    // 시간 복잡도 O(log7 n) 공간 복잡도 O(1)
    public String convertToBase7Otimal(int num){
        if(num<0)
            return "-"+convertToBase7Otimal(-num);
        if(num<7)
            return num+"";
        return convertToBase7Otimal(num/7)+num%7;
    }
}

메모: 재귀는 쉽게 생각하고 간결하게 짜야 한다.

의역: (BST) 자식이 부모와 같은 값을 가질 수 있는 조건이 추가된 이진트리가 주어질 때 해당 트리에서 가장 많이 나온 노드값 들의 배열을 반환하시오  

의역: 첫 번째 예시에서는 2가 가장 많은 노드 값이었기 때문에 2를 반환

두 번째 예시에서는 0이 가장 많은 노드 값이기 때문에 0을 반환

풀이:

1. 전위순회(dfs) + Map

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    // 가장 빈도가 높게 나온 횟 수
    private int maxValue=1;
    private HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    // 전위순회 알고리즘 (DFS)
    public void helper(TreeNode2 root){
    	// HashMap의 contains() 함수를 사용해도 되지만 더 효율적으로 바꾼 것
        if(root!=null){
            Integer value = map.get(root.val);

            if(value!=null){
            	// 최대 빈도 갱신
                if(value+1>maxValue)
                    maxValue = value+1;
                map.put(root.val,value+1);}

            else map.put(root.val,1);
            helper(root.right);
            helper(root.left);
        }
    }
    public int[] findMode(TreeNode2 root) {
        List<Integer> ans = new ArrayList<Integer>();
        helper(root);

        Set<Integer> set = map.keySet();
        Iterator<Integer> it = set.iterator();
        while(it.hasNext()){
            int key = it.next();
            int value = map.get(key);
            // 가장 빈도가 높은 횟수랑 같다면 추가
            if(value==maxValue)
                ans.add(key);
        }
        return  ans.stream()
                .mapToInt(i -> i)
                .toArray();

    }
}

1-1 map을 사용하지 않고 BST의 성질을 이용해 개선 시킨 코드

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(1)
    ArrayList<Integer> ans;
    int maxCount;
    int count;
    TreeNode pre;

    public int[] findMode(TreeNode root) {
        ans = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        helper(root);
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }

    public void helper(TreeNode root) {
        if (root == null) {
            return;
        }
        helper(root.left);

        int rootValue = root.val;
        // 루트 노드인 경우와 값이 달라진 경우
        if (pre == null || rootValue != pre.val) {
            count = 1;
        } else {
            count++;
        }
        // maxCount 최대 빈도 수와 비교 해서 크다면 ArrayList 최신화
        if (count > maxCount) {
            ans.clear();
            ans.add(rootValue);
            maxCount = count;
        } else if (count == maxCount) {
            ans.add(rootValue);
        }
        pre = root;

        helper(root.right);
    }
}

메모: BST 중복값을 허용하는 이진 트리

링크: https://leetcode.com/problems/find-mode-in-binary-search-tree/description/