myBlog

문제설명

https://leetcode.com/problems/count-complete-tree-nodes/

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

complete binary tree의 노드 수를 반환하세요.

문제에서 complete binary tree란, 마지막 level을 제외하고 모든 노드가 채워진 binary tree를 의미합니다. 그리고 마지막 level은 가능한 왼쪽에 있습니다.

아이디어

1. 마지막 노드를 찾아서 1 + 2^h + 마지막 level의 노드 수를 계산한다.

2. 모든 노드를 방문해서 수를 센다.

2번이 간단하여 2번으로 해결했습니다.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int nodeCnt = 0;
    private int searchTree(TreeNode treeNode){
        nodeCnt++;
        if(treeNode.left != null){
            nodeCnt = searchTree(treeNode.left);
        } else {
            return nodeCnt;
        }
        if(treeNode.right != null){
            nodeCnt = searchTree(treeNode.right);
        }
        return nodeCnt;
    }

    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        return searchTree(root);
    }
}

Result

문제설명

https://leetcode.com/problems/sort-characters-by-frequency/

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

string s에 대해, character의 빈도(출현 수)에 따라 내림차순으로 정렬하세요. 빈도(출현 수)는 string에 나타난 횟수입니다. 다수의 정답이 있으면 그 중 아무거나 return하면 됩니다.

아이디어

문자의 빈도를 알기 위해 String을 한 글자씩 모두 탐색하였으며 Collection을 사용해 정렬했습니다.

https://81shinez.tistory.com/10 포스팅을 참고했습니다.

Solution

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

    public String frequencySort(String s) {
        char[] charArray = s.toCharArray();

        HashMap<Character, Integer> hashMap = new HashMap<>();

        for(char character : charArray){
            if(hashMap.containsKey(character)){
                hashMap.put(character, hashMap.get(character) + 1);
            } else {
                hashMap.put(character, 1);
            }
        }

        ArrayList<Pair<Character, Integer>> pairList = new ArrayList<>();

        for(char key : hashMap.keySet()){
            pairList.add(new Pair<>(key, hashMap.get(key)));
        }

        Collections.sort(pairList, (o1, o2) -> o2.right.compareTo(o1.right));

        StringBuffer sb = new StringBuffer();

        for(Pair<Character, Integer> pair : pairList){
            for(int i = 0; i < pair.right; i++){
                sb.append(pair.left);
            }
        }

        return sb.toString();
    }
}

Result

> 문제 설명 보기

programmers.co.kr/learn/courses/30/lessons/42861

>IDEA

Minimum Spanning Tree(MST)를 구하는 문제이다.

정점을 기준으로 MST를 구하는 Prim의 알고리즘과 간선을 기준으로 MST를 구하는 Kruskal의 알고리즘으로 해당 문제를 해결 할 수 있다.

해당 문제의 input이 간선으로 주어졌으므로, Kruskal의 알고리즘의 코드가 더 짧다.

>Solution (Kruskal's Algorithm)

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs){
        int answer = 0;
        int[] fromIsland = new int[n];

        // 모든 간선을 가중치 오름차순으로 정렬
        Arrays.sort(costs, (o1, o2) -> o1[2] - o2[2]);

        for(int idx = 0; idx < n; idx ++){
            fromIsland[idx] = idx;
        }

        for(int[] cost : costs){
            if(findRoot(cost[0], fromIsland) != findRoot(cost[1], fromIsland)){
                fromIsland[findRoot(cost[0], fromIsland)] = findRoot(cost[1], fromIsland);

                answer += cost[2];
            }
        }

        return answer;
    }

    int findRoot(int nodeNo, int[] fromIsland){
        if(fromIsland[nodeNo] == nodeNo) return nodeNo;
        return findRoot(fromIsland[nodeNo], fromIsland);
    }
}

> Result (Kruskal's Algorithm)

> Solution (Prim's Algorithm)

public int solution(int n, int[][] costs) {
        int answer = 0;

        HashMap<Integer, ArrayList<int[]>> edgeMap = new HashMap<>();
        HashSet<Integer> nodes = new HashSet<>();
        ArrayList<int[]> edges = new ArrayList<>();

        for(int[] cost : costs){
            if(edgeMap.containsKey(cost[0])){
                edgeMap.get(cost[0]).add(new int[]{cost[1], cost[2]});
            } else {
                ArrayList<int[]> insertList = new ArrayList<>();
                insertList.add(new int[]{cost[1], cost[2]});
                edgeMap.put(cost[0], insertList);
            }
            if(edgeMap.containsKey(cost[1])){
                edgeMap.get(cost[1]).add(new int[]{cost[0], cost[2]});
            } else {
                ArrayList<int[]> insertList = new ArrayList<>();
                insertList.add(new int[]{cost[0], cost[2]});
                edgeMap.put(cost[1], insertList);
            }
            nodes.add(cost[0]);
            nodes.add(cost[1]);
        }

        int node = costs[0][0]; // 시작 노드
        edges.addAll(edgeMap.get(node));
        nodes.remove(node);

        while(!nodes.isEmpty()){
            Collections.sort(edges, (o1, o2) -> o1[1] - o2[1]);
            for(int idx = 0; idx < edges.size(); idx++){
                int[] edge = edges.get(idx);
                if(nodes.contains(edge[0])){
                    nodes.remove(edge[0]);
                    edges.remove(idx);
                    edges.addAll(edgeMap.get(edge[0]));
                    answer += edge[1];
                    break;
                }
            }
        }

        return answer;
    }

> Result (Prim's Algorithm)

Prim의 알고리즘이 더 느려보이지만 구현방식에 있어 Collection 객체가 많이 사용되어서 그렇고, 사실은 두 알고리즘의 시간복잡도는 똑같다.

> 문제 설명 보기

programmers.co.kr/learn/courses/30/lessons/42885?language=java

>IDEA

최대 2인승의 구명보트를 가능한 적게 써서 모든 사람을 구출하는 문제다.

가장 무거운 사람이 보트에 탔을 때, 가장 가벼운 사람이 같이 탈수 있다면 둘을 같이 보내고, 아니라면 무거운사람 혼자 보내야 한다.

최대 2인승이기 때문에, 혼자 타거나, 둘이 타는 경우의 수 밖에 없다.

>Solution

import java.util.Arrays;
import java.util.LinkedList;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        LinkedList<Integer> linkedList = new LinkedList<>();

        Arrays.sort(people);
        for(int weight : people){
            linkedList.addLast(weight);
        }

        int weight;
        while(!linkedList.isEmpty()){
            weight = linkedList.pollLast(); // 가장 무거운놈
            if(!linkedList.isEmpty()){
                if(weight + linkedList.peekFirst() <= limit){ // 가장 무거운놈과 가장 가벼운놈이 같이 탈 수 있는 경우
                    linkedList.pollFirst();
                }
            }
            answer++;
        }
        return answer;
    }
}

> Arrays.sort() vs Collections.sort() 성능 비교

Arrays.sort를 사용했을 경우 효율성 테스트

Collections.sort를 사용했을 경우 효율성 테스트

생각보다 성능 차이가 심해서 놀랐다.

컬렉션의 자료구조가 배열보다 무거워서 이런 차이가 발생하는 것 같은데, 간단한 구조인 배열이 훨씬 빠르다는 점을 다시 한번 되뇌었다.

> 문제 설명 보기

programmers.co.kr/learn/courses/30/lessons/42898

>IDEA

중고등학교적 많이 풀던 가장 짧은 거리의 개수를 구하는 문제다.

기본적으로 이전 도달 지점까지의 도달 개수를 다음 지점에서 더해주면 된다.

해당 방법을 기본으로 예외처리 (웅덩이)를 해주며 해결했다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        boolean[][] isPud = new boolean[m][n];
        long[][] map = new long[m][n];


        // Initialize
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j ++){
                map[i][j] = 0;
            }
        }

        for(int[] intArr : puddles){
            isPud[intArr[0] - 1][intArr[1] - 1] = true;
        }

        map[0][0] = 1;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(isPud[i][j]) continue;
                if(j > 0 && i > 0) {
                    if (isPud[i - 1][j] && isPud[i][j - 1]) {
                        isPud[i][j] = true;
                        continue;
                    }
                }
                if(j > 0){
                    if(!isPud[i][j-1]){
                        map[i][j] = (map[i][j] + map[i][j-1]) % 1000000007;
                    }
                }
                if(i > 0){
                    if(!isPud[i-1][j]){
                        map[i][j] = (map[i][j] + map[i-1][j]) % 1000000007;
                    }
                }
            }
        }

        return (int)(map[m-1][n-1]);
    }
}

> 문제 설명 보기

programmers.co.kr/learn/courses/30/lessons/42883

> IDEA

순서를 바꿀수 없는 문자열 형태의 숫자 중 k개를 제거하여 ( = 문자열의 총 길이가 n일 때, n-k개를 선택하여) 가장 큰 수를 만드는 문제이다.

가장 큰 자릿수의 수를 골라야 가장 큰 수를 만들 수 있으므로 왼쪽부터 가장 큰 수를 고르면서, 항상 남아있는 숫자의 개수가 선택해야 하는 수의 개수 이상을 유지하면 된다.

예를들어 "1231234"의 경우, k = 3이라면 4개의 숫자를 선택해야 하는데

첫번째 숫자는 3개의 숫자를 남긴 "1231"에서 가장 큰 수를 골라 3이 되며

두번째는 첫번째 고른 숫자로부터 오른쪽엔 2개의 숫자를 남긴 "12" 중에 가장 큰 수를 골라 2가 되며

세번째는 두번째 고른 숫자로부터 오른쪽엔 1개의 숫자를 남겨 "3"중에 3이 되며

네번째는 세번째 고른 숫자로부터 오른쪽엔 0개의 숫자를 남겨 "4"중에 4가 된다.

따라서 "3234"를 반환하면 된다.

>Solution

class Solution {
    public String solution(String number, int k) {
        char maxVal;
        int pos = 0;
        StringBuffer sb = new StringBuffer();
        for(int cnt = number.length() - k; cnt > 0 ; cnt--){
            maxVal = '0';
            for(int idx = pos; idx < number.length() - cnt + 1; idx++){
                if(number.charAt(idx) > maxVal){
                    maxVal = number.charAt(idx);
                    pos = idx+1;
                }
            }
            sb.append(maxVal);
        }
        return sb.toString();
    }
}

String, StringBuilder, StringBuffer의 성능 차이를 알 수 있는 문제였다.

String은 immutable한 변수이기 때문에 한 번 선언되면 변하지 않고 String끼리 연산하여 String을 만들어 낼 때는 새로운 class를 생성하여 연산 결과를 할당하게 된다. 따라서 다수의 String 연산을 실행하게 되면 속도가 급격히 떨어진다.

StringBuilder와 StringBuffer는 내부적으로 배열 형태로 구현되어 새로운 문자열이 추가될 때, 해당 길이만큼 배열이 남아있다면 그대로 추가하여 사용하고, 모자라다면 두배의 크기로 배열을 할당하기 때문에 String보다 연산 속도가 빠르다.

다만 StringBuiler가 단일 쓰레드에서 연산속도가 더 빠르며 StringBuffer는 Thread-Safe하다.

> String 구현

>StringBuilder 구현

> StringBuffer 구현

> 문제설명

leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/

문제내용 요약

주어진 바이너리 트리에서 노드의 왼쪽 하위노드와 오른쪽 하위노드를 바꾸는 것을 flip이라고 한다.

주어진 바이너리 트리를 pre-order 방식으로 탐색했을 때, 주어진 배열 voyage와 같은 순서로 탐색하기 위해 flip해야 하는 노드의 val값을 리스트에 넣어 반환하라.

>IDEA

바이너리 트리를 pre-order(DFS)로 탐색하며 voyage와 비교한다.

voyage와 pre-order의 순서가 다른 경우 하위 노드를 flip하며 pre-order 탐색을 진행한다.

탐색이 끝난 후 pre-order로 탐색한 순서와 voyage가 같다면 리스트를 출력한다.

>Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int[] travel;
    int travelIdx;
    ArrayList<Integer> answerList = new ArrayList<>();

    boolean flip(TreeNode treeNode){
        if(treeNode.left == null || treeNode.right == null) return false;
        answerList.add(treeNode.val);
        TreeNode tmp = treeNode.left;
        treeNode.left = treeNode.right;
        treeNode.right = tmp;
        return true;
    }

    void preOrder(TreeNode treeNode, int[] voyage){
        travel[travelIdx] = treeNode.val;
        if(travelIdx < voyage.length- 1)travelIdx++;
        else return;
        if(treeNode.left != null){
            if (treeNode.left.val != voyage[travelIdx]) {
                flip(treeNode);
            }
            preOrder(treeNode.left, voyage);
        }
        if(treeNode.right != null){
            if (treeNode.right.val != voyage[travelIdx]) {
                flip(treeNode);
            }
            preOrder(treeNode.right, voyage);
        }
    }

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        travel = new int[voyage.length];
        travelIdx = 0;
        preOrder(root, voyage);
        if(!Arrays.equals(travel, voyage)) {
            answerList.clear();
            answerList.add(-1);
        }
        return answerList;
    }
}

> Result

flip을 없애고 다음과 같이 구현 할 수도 있다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int[] travel;
    int travelIdx;
    ArrayList<Integer> answerList = new ArrayList<>();

    void preOrder(TreeNode treeNode, int[] voyage){
        travel[travelIdx] = treeNode.val;
        if(travelIdx < voyage.length- 1)travelIdx++;
        else return;
        if(treeNode.left != null){
            if (treeNode.left.val != voyage[travelIdx]) {
                answerList.add(treeNode.val);
                if(treeNode.right != null) preOrder(treeNode.right, voyage);
                preOrder(treeNode.left, voyage);
                return;
            }
        }
        if(treeNode.left != null) preOrder(treeNode.left, voyage);
        if(treeNode.right != null) preOrder(treeNode.right, voyage);
    }

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        travel = new int[voyage.length];
        travelIdx = 0;
        preOrder(root, voyage);
        if(!Arrays.equals(travel, voyage)) {
            answerList.clear();
            answerList.add(-1);
        }
        return answerList;
    }
}

> Result

수행 속도가 줄었다.

> 문제설명

leetcode.com/problems/reconstruct-original-digits-from-english/

문제 내용 요약

0부터 9까지의 숫자의 스펠링이 규칙없이 나열된 String에서 숫자를 복원해 오름차순으로 반환한다.

> IDEA

각 숫자가 가질 수 있는 특별한 알파벳을 검사하여 해결할 수 있다.

> Solution

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

class Solution {
    void mapRemove(char c, HashMap<Character, Integer> stringMap){
        if(!stringMap.containsKey(c)) return;
        if(stringMap.get(c) == 1){
            stringMap.remove(c);
        } else {
            stringMap.replace(c, stringMap.get(c) - 1);
        }
    }
    public String originalDigits(String s) {
        ArrayList<Integer> answerList = new ArrayList<>();
        HashMap<Character, Integer> stringMap = new HashMap<>();
        for(int idx = 0; idx < s.length(); idx++){
            if(stringMap.containsKey(s.charAt(idx))){
                stringMap.replace(s.charAt(idx), stringMap.get(s.charAt(idx))+1);
            } else {
                stringMap.put(s.charAt(idx), 1);
            }
        }

        while (!stringMap.isEmpty()){
            if(stringMap.containsKey('z')) {
                answerList.add(0);
                mapRemove('z', stringMap);
                mapRemove('e', stringMap);
                mapRemove('r', stringMap);
                mapRemove('o', stringMap);
                continue;
            }
            if(stringMap.containsKey('w')) {
                answerList.add(2);
                mapRemove('t', stringMap);
                mapRemove('w', stringMap);
                mapRemove('o', stringMap);
                continue;
            }
            if(stringMap.containsKey('u')) {
                answerList.add(4);
                mapRemove('f', stringMap);
                mapRemove('o', stringMap);
                mapRemove('u', stringMap);
                mapRemove('r', stringMap);
                continue;
            }
            if(stringMap.containsKey('x')) {
                answerList.add(6);
                mapRemove('s', stringMap);
                mapRemove('i', stringMap);
                mapRemove('x', stringMap);
                continue;
            }
            if(stringMap.containsKey('g')) {
                answerList.add(8);
                mapRemove('e', stringMap);
                mapRemove('i', stringMap);
                mapRemove('g', stringMap);
                mapRemove('h', stringMap);
                mapRemove('t', stringMap);
                continue;
            }
            if(stringMap.containsKey('o')) {
                answerList.add(1);
                mapRemove('o', stringMap);
                mapRemove('n', stringMap);
                mapRemove('e', stringMap);
                continue;
            }
            if(stringMap.containsKey('t') || stringMap.containsKey('h') || stringMap.containsKey('r')) {
                answerList.add(3);
                mapRemove('t', stringMap);
                mapRemove('h', stringMap);
                mapRemove('r', stringMap);
                mapRemove('e', stringMap);
                mapRemove('e', stringMap);
                continue;
            }
            if(stringMap.containsKey('f')) {
                answerList.add(5);
                mapRemove('f', stringMap);
                mapRemove('i', stringMap);
                mapRemove('v', stringMap);
                mapRemove('e', stringMap);
                continue;
            }
            if(stringMap.containsKey('s')) {
                answerList.add(7);
                mapRemove('s', stringMap);
                mapRemove('e', stringMap);
                mapRemove('v', stringMap);
                mapRemove('e', stringMap);
                mapRemove('n', stringMap);
                continue;
            }
            answerList.add(9);
            mapRemove('n', stringMap);
            mapRemove('i', stringMap);
            mapRemove('n', stringMap);
            mapRemove('e', stringMap);
            continue;
        }

        Collections.sort(answerList);
        StringBuilder sb = new StringBuilder();
        for(int num : answerList){
            sb.append(num);
        }

        return sb.toString();
    }
}