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

> 문제설명

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();
    }
}

> 문제설명

leetcode.com/problems/vowel-spellchecker/

문제 내용을 요약하자면 다음과 같다.

목표 String배열 wordlist와 질의 String배열 queries가 주어졌을 때, 각 질의 String배열을 다음과 같은 연산을 통해 정답 String배열을 return하면 된다.

1. 목표 String과 질의 String이 완벽히 일치하면 그대로 정답 배열에 추가.

2. 대소문자에 관계없이 일치하는 경우, 목표 String배열중 가장 앞의 String을 정답 배열에 추가.

3. 대소문자에 관계없이 vowel(모음, [AaEeIiOoUu])이 위치와 개수 상관 없이 다른 경우, 모음을 제외한 자음이 모두 일치하는 String을 목표 String배열의 가장 앞쪽에서 찾아 정답 배열에 추가.

4. 위 경우가 아닌 경우 빈 String을 정답 배열에 추가.

> Solution

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;

class Solution {
    public String[] spellchecker(String[] wordlist, String[] queries) {
        LinkedHashSet<String> wordSet = new LinkedHashSet<>();
        HashMap<String, String> vowelMap = new HashMap<>();
        HashMap<String, String> upperMap = new HashMap<>();

        for(String word : wordlist){
            wordSet.add(word);
            upperMap.putIfAbsent(word.toUpperCase(), word);
            vowelMap.putIfAbsent(word.replaceAll("[AaEeIiOoUu]", "*").toUpperCase(), word);
        }

        ArrayList<String> ansList = new ArrayList<>();
        for(String query : queries){
            if(wordSet.contains(query)) {
                ansList.add(query);
                continue;
            }

            if(upperMap.containsKey(query.toUpperCase())){
                ansList.add(upperMap.get(query.toUpperCase()));
                continue;
            }

            String str = query.replaceAll("[AaEeIiOoUu]", "*");
            if(vowelMap.containsKey(str.toUpperCase())){
                ansList.add(vowelMap.get(str.toUpperCase()));
                continue;
            }

            ansList.add("");
        }
        return ansList.toArray(new String[0]);
    }
}

문제 설명 보기

leetcode.com/problems/reordered-power-of-2/

> Desc

입력된 숫자의 자리를 자유롭게 교체해 2의 제곱 승 꼴의 숫자로 만들수 있는지 물어보는 문제다.

>IDEA

1. 숫자의 위치를 자유롭게 바꾼다.

순열 (Permutation)

2. 2의 제곱 승 꼴의 숫자

비트연산자 활용

>Solution(Permutation)

class Solution {
    boolean permutation(String prefix, String str){
        if(str.length() == 0) {
            if ((Integer.parseInt(prefix) | Integer.highestOneBit((Integer.parseInt(prefix))) )== Integer.highestOneBit((Integer.parseInt(prefix)))) return true;
        }
        for(int idx = 0; idx < str.length(); idx++){
            if (!prefix.startsWith("0")) {
                if (permutation(prefix + str.charAt(idx), str.substring(0, idx) + str.substring(idx + 1)))
                    return true;
            }
        }
        return false;
    }

    public boolean reorderedPowerOf2(int N) {
        String str = String.valueOf(N);
        return permutation("", str);

    }
}

> Result

대충 어떻게 시간초과를 면했는지 모르겠다.

그래서 모범답안을 컨닝해봤다.

class Solution {
    public boolean reorderedPowerOf2(int N) {
        int[] A = count(N);
        for (int i = 0; i < 31; ++i)
            if (Arrays.equals(A, count(1 << i)))
                return true;
        return false;
    }

    // Returns the count of digits of N
    // Eg. N = 112223334, returns [0,2,3,3,1,0,0,0,0,0]
    public int[] count(int N) {
        int[] ans = new int[10];
        while (N > 0) {
            ans[N % 10]++;
            N /= 10;
        }
        return ans;
    }
}

2의 제곱승 꼴의 숫자를 10진수로 표현했을 경우, 사용된 각 자릿수의 숫자의 개수를 세어 비교한다.

>> 문제설명

leetcode.com/problems/keys-and-rooms/

> 0개 이상의 간선을 가진 단일 방향 그래프에서 모든 정점을 탐색할 수 있는지를 묻는 문제입니다.

> BFS, DFS 와 같은 그래프 탐색 알고리즘을 사용하여 모든 정점의 방문 여부를 체크합니다.

> Solution(BFS)

import java.util.Arrays;
import java.util.List;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        LinkedList<Integer> openList = new LinkedList<>();
        HashSet<Integer> isOpened = new HashSet<>();
        
        isOpened.add(0);
        openList.add(0);

        while (!openList.isEmpty()){
            int size = openList.size();
            for(int i = 0; i < size; i++){
                for(int room : rooms.get(openList.pollFirst())){
                    if(!isOpened.contains(room)){
                        openList.add(room);
                        isOpened.add(room);
                    }
                }
            }
        }

        return isOpened.size() == rooms.size() ? true : false;
    }
}

>> 문제설명

leetcode.com/problems/wiggle-subsequence/

> 일차원 배열로 주어진 input에서, 계차수열이 양수와 음수가 번갈아 나오도록 하는 가장 긴 subSequence를 구하는 문제이다.

> 문제 설명 상, 순서를 바꾸지 않는다면 원소를 0개 이상 제거한 것이 주어진 배열에 대한 subSequence다.

> IDEA

배열에서 이전 숫자보다 현재 숫자가 크면 계차가 양수, 아니면 계차가 음수이므로 현재 숫자와 이전 숫자 비교를 선형으로 진행하였다.

이 과정에서, 숫자가 계속 늘어나는건 계차의 부호가 바뀌지 않기 때문에 isGrowing이라는 Boolean 변수를 선언해 상태를 관리했다.

>Solution

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int ans = 1;
        boolean isGrowing =true;
        if(nums.length < 2) return nums.length;
        for(int idx = 1; idx < nums.length; idx++){
            if(nums[idx] > nums[idx-1]){
                if(isGrowing == false){
                    ans++;
                } else if(ans == 1) ans++;
                isGrowing = true;
            } else if (nums[idx] < nums[idx-1]){
                if(isGrowing == true){
                    ans++;
                } else if(ans == 1) ans++;
                isGrowing = false;
            }
        }
        return ans;
    }
}