Problem

• 문제 링크

배열이 주어졌을 때 가장 많이 나오는 숫자를 찾아 리턴하는 문제입니다.

가장 많이 나오는 빈도는 문제에 명시된 대로 배열의 길이 / 2 입니다.

Solution

여러가지 풀이가 존재할 수 있습니다.

시간 복잡도만 고려해서 HashMap 을 사용해서 숫자들의 카운트를 기록했는데 Discuss 를 보니 Moore Voting Algorithm 라는 더 좋은 해답이 있었습니다.

Sort 는 그냥 길이가 짧고 신기해서 넣었습니다.

Java Code

// 1. Using HashMap - Time: O(n), Space: O(n)
class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);

            if (count > nums.length / 2) {
                return num;
            }
        }

        return 0;
    }
}

// 2. Using Sort - Time: O(n logn), Space: O(1)
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

// 3. Using Moore Voting Algorithm (From Discuss)
// Time: O(n), Space: O(1)
class Solution {
    public int majorityElement(int[] nums) {
        int curr = 0;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                curr = num;
            } 

            count += (curr == num) ? 1 : -1;
        }

        return curr;
    }
}

Kotlin Code

class Solution {
    fun majorityElement(nums: IntArray): Int {
        return nums.groupBy { it }
                   .filterValues { it.size > (nums.size / 2) }
                   .keys
                   .first()
    }
}

Problem

• 문제 링크

Excel 의 행이 문자열로 주어지면 몇 번째 행인지 계산하는 문제입니다.

Solution

문자열 뒤에서부터 계산해도 되는데 저는 앞에서부터 했습니다.

ABZ 라는 문자열을 받았다고 가정합니다.

수식으로 변경하면 다음과 같습니다.

(A * 26 * 26) + (B * 26) + Z

*26 을 밖으로 빼서 정리해서 다시 수식을 표현할 수 있습니다.

(((A * 26) + B) * 26) + Z

위 수식을 바탕으로 for 문을 돌립니다.

1. 시작 값은 0 이다.
2. 26 을 곱한다.
3. 문자를 더한다.

Java Code

class Solution {
    public int titleToNumber(String s) {
        int ret = 0;

        for (char c : s.toCharArray()) {
            ret *= 26;
            ret += c - 64;
        }

        return ret;
    }
}

Kotlin Code

class Solution {
    fun titleToNumber(s: String): Int {
        return s.toCharArray().fold(0) { total, num -> total * 26 + num.toInt() - 64 }
    }
}

Problem

• 문제 링크

난이도는 Easy

오름차순으로 정렬되어 있는 int 배열이 주어지면 높이가 1 이상 차이나지 않는 BST 를 만드는 문제입니다.

Solution

이분탐색 하듯이 트리를 순회하면 됩니다.

배열이 오름차순으로 되어 있기 때문에 중앙에 있는 값이 무조건 root 가 되야 합니다.

부모 노드 nums[mid] 를 만들고 나면 왼쪽 서브트리는 0 ~ mid - 1 로 만든 트리고 오른쪽 서브트리는 mid + 1 ~ nums.length - 1 로 만든 트리입니다.

Java Code

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return traverse(nums, 0, nums.length - 1);
    }

    public TreeNode traverse(int[] nums, int low, int high) {
        if (low > high) return null;

        int mid = low + (high - low)/2;

        return new TreeNode(
            nums[mid],
            traverse(nums, low, mid - 1),
            traverse(nums, mid + 1, high)
        );
    }
}

Kotlin Code

class Solution {
    fun sortedArrayToBST(
        nums: IntArray, 
        low: Int = 0, 
        high: Int = nums.size - 1
    ): TreeNode? {
        if (low > high) return null

        val mid = low + (high - low) / 2;

        return TreeNode(nums[mid]).apply {
            left = sortedArrayToBST(nums, low, mid - 1)
            right = sortedArrayToBST(nums, mid + 1, high)
        }
    }
}

Problem

• 문제 링크

nums 배열에 있는 각 숫자에 + 또는 - 중 하나를 선택해서 전부 계산할 경우 S 와 같은 값이 나오는 경우의 수는 몇 가지인지 찾는 문제입니다.

Solution

DFS 를 이용해서 모든 경우의 수를 찾아주면 됩니다.

index 를 하나씩 증가시키면서 nums[index] 를 더하는 경우, 빼는 경우를 차례대로 확인합니다.

Java Code

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        return dfs(nums, S, 0, 0);
    }
    
    private int dfs(int[] nums, int S, int index, int sum) {
        if (index == nums.length) {
            return S == sum ? 1 : 0;
        }
        
        return dfs(nums, S, index + 1, sum + nums[index]) +
               dfs(nums, S, index + 1, sum - nums[index]);
    }
}

Problem

• 문제 링크

Medium 문제입니다.

주어진 문자열 S 를 나누었을 때 각 파트는 다른 파트와 중복된 문자가 없어야 합니다.

예를 들어 a, b, c 세 파트로 나눈다면 a 파트에 존재하는 문자는 b, c 파트에 존재하지 않아야 합니다.

위 조건을 만족하면서 최대한 많은 파트로 쪼갰을 때 각각의 길이를 List 에 담아 리턴하면 됩니다.

Solution

for 문을 총 두번 돕니다.

첫 번째 for 문에서는 각 문자들이 마지막으로 등장하는 index 를 저장해둡니다.

두 번째 for 문에서는 현재 지나고 있는 문자들 중 가장 마지막에 나오는 문자의 index 를 저장해둔 뒤 i 가 그 index 에 도달했을 때, 더 이상 중복되는 문자는 나오지 않는다고 판단하여 길이를 저장합니다.

주어진 문자 "ababcbacadefegdehijhklij" 로 예를 들면

"ababcbaca" 문자열이 진행되는 동안 farRight 변수는 8 입니다.

마지막 'a' 를 만나는 순간 i == farRight 가 되고 지금까지 나온 문자들은 이후에는 절대 나오지 않는다 라는 걸 알 수 있습니다.

리스트에 start 부터 farRight 까지의 길이를 넣어두고 다음 문자부터 다시 위 과정을 반복하면 됩니다.

Java Code

class Solution {
    public List<Integer> partitionLabels(String S) {
        int[] lastIndexs = new int[26];

        for (int i = 0; i < S.length(); i++) {
            lastIndexs[S.charAt(i) - 'a'] = i;
        }
        
        List<Integer> list = new ArrayList<>();
        int start = 0;
        int farRight = 0;
        
        for (int i = 0; i < S.length(); i++) {
            farRight = Math.max(farRight, lastIndexs[S.charAt(i) - 'a']);
            
            if (i == farRight) {
                list.add(farRight - start + 1);
                start = i + 1;
            }
        }
        
        return list;
    }
}

Problem

• 문제 링크

Easy 문제입니다.

문자열 s 가 특정 substring 의 반복으로만 이루어진 경우를 찾는 문제입니다.

Solution

substring 을 구한 후 반복해서 붙인 다음 s 와 비교하면 됩니다.

순서대로 나열하면 다음과 같습니다.

1. substring 의 길이를 s 의 절반부터 시작해서 1 까지 확인한다. (절반보다 길면 substring 이 반복될 수가 없음)
2. s 의 길이가 substring 의 길이와 나누어 떨어지는 지 확인한다.
3. substring 을 반복해서 붙인 다음 s 와 비교한다.
4. 일치하는게 나올 때까지 확인한다.

Java Code

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        for (int len = s.length() / 2; len > 0; len--) {
            if (s.length() % len != 0) {
                continue;
            }
            
            int repeatCount = s.length() / len;
            String pattern = s.substring(0, len);
            StringBuilder sb = new StringBuilder();
            
            while (repeatCount-- > 0) {
                sb.append(pattern);
            }
            
            if (sb.toString().equals(s)) {
                return true;
            }
        }
        
        return false;
    }
}

Problem

• 문제 링크

Easy 문제입니다.

트리가 주어졌을 때 가장 아래쪽에 있고 가장 왼쪽에 있는 노드의 값을 구하는 문제입니다.

Solution

단순하게 풀면 됩니다.

최고 깊이 maxDepth 와 리턴할 결과값 result 를 인스턴스 변수로 선언합니다.

Preorder 로 트리를 순회하면 depth 가 1 높아졌을 때 마주하는 노드가 가장 왼쪽에 있는 노드입니다.

depth 가 1 높아지는 순간의 노드값을 저장해두면서 트리를 모두 순회하면 됩니다.

시간복잡도는 O(n) (n 은 노드의 갯수) 입니다.

Java Code

class Solution {
    int maxDepth = 0;
    int result = 0;
        
    public int findBottomLeftValue(TreeNode root) {
        goChild(root, 1);
        return result;
    }
    
    public void goChild(TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        
        if (depth > maxDepth) {
            result = node.val;
            maxDepth = depth;
        }
        
        goChild(node.left, depth + 1);
        goChild(node.right, depth + 1);
    }
}

Problem

• 문제 링크

Easy 난이도의 문제입니다.

주어진 숫자 n 을 이진수로 바꾸었을 때 0 과 1 이 연속으로 나오는 구간이 있는지 없는지 판단하는 문제입니다.

Solution

n 을 이진수로 바꾸어 줍니다.

길이가 1 이라면 반복되는 구간이 없기 때문에 항상 true 입니다.

인덱스 0 에 해당하는 문자 even 을 구하고 이와 반대되는 문자 odd 를 구합니다.

이진수 String 을 순회하며 인덱스가 짝수일 때와 홀수일 때 각각 even 과 odd 와 일치하는 지 확인합니다.

시간복잡도는 O(n) 입니다.

Java Code

class Solution {
    public boolean hasAlternatingBits(int n) {
        String bit = Integer.toString(n, 2);
        
        if (bit.length() == 1) {
            return true;
        }
        
        char even = bit.charAt(0);
        char odd = even == '0' ? '1' : '0';
        
        for (int i = 0; i < bit.length(); i++) {
            if (i % 2 == 0 && even != bit.charAt(i)) {
                return false;
            }
            
            if (i % 2 != 0 && odd != bit.charAt(i)) {
                return false;
            }
        }
        
        return true;
    }
}