Problem

• 문제 링크

nums 배열의 길이가 n 이라고 할 때 0 ~ n 까지의 숫자 중 배열에 없는 숫자를 구하는 문제입니다.

Solution

0 ~ n 의 합에서 배열 원소의 합을 빼면 빠진 숫자가 나옵니다.

Java Code

class Solution {
    public int missingNumber(int[] nums) {
        int sum = nums.length;

        for (int i = 0; i < nums.length; i++) {
            sum += i - nums[i];
        }

        return sum;
    }
}

Kotlin Code

class Solution {
    fun missingNumber(nums: IntArray): Int = nums.foldIndexed(nums.size) { acc, i, num -> acc + i - num }
}

Problem

• 문제 링크

ID, 중요도, 부하직원 리스트를 속성으로 가진 Employee 클래스가 있습니다.

모든 직원들 리스트와 특정 직원의 ID 를 지목했을 때 그 직원을 포함하여 하위 모든 직원들의 중요도 합을 구하는 문제입니다.

Solution

각 직원들이 노드인 트리라고 생각하면 됩니다.

직원들의 ID 를 키로 한 HashMap 을 하나 선언한 뒤, 선택된 id 부터 DFS 또는 BFS 로 순회하며 모든 합을 구하면 됩니다.

Java Code

// BFS
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        employees.forEach(e -> map.put(e.id, e));

        int res = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(id);

        while (!q.isEmpty()) {
            Employee employee = map.get(q.poll());
            res += employee.importance;
            q.addAll(employee.subordinates);
        }

        return res;
    }
}

// DFS
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        employees.forEach(e -> map.put(e.id, e));
        return dfs(map, id);
    }

    public int dfs(Map<Integer, Employee> map, int id) {
        Employee e = map.get(id);
        return e.importance + e.subordinates.stream().mapToInt(subId -> dfs(map, subId)).sum();
    }
}

Problem

• 문제 링크

2차원 배열 nums 가 주어진다.

이 행렬의 값을 r * c 의 새로운 행렬로 바꾸는 문제입니다.

Solution

nums 배열에 있는 값을 전부 Queue 에 담은 후에 r * c 배열에 맞춰서 다시 값을 채워넣으면 됩니다.

나누기와 나머지 연산자를 이용하면 Queue 를 사용하지 않고 문제를 해결할 수 있습니다.

시간 복잡도는 O(r * c) 입니다.

Java Code

// use Queue
class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int[][] res = new int[r][c];
        Queue<Integer> q = new LinkedList<>();

        if (r * c != nums.length * nums[0].length) {
            return nums;
        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i].length; j++) {
                q.add(nums[i][j]);
            }
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                res[i][j] = q.poll();
            }
        }

        return res;
    }
}

// without Extra Memory
class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int a = nums.length, b = nums[0].length;

        if (r * c != a * b) {
            return nums;
        }

        int[][] res = new int[r][c];

        for (int i = 0; i < r * c; i++) {
            res[i / c][i % c] = nums[i / b][i % b];
        }

        return res;
    }
}

Problem

• 문제 링크

자연수 배열 nums 와 숫자 m 이 주어집니다.

배열을 m 개의 부분 배열로 나눕니다.

각 부분 배열의 합 중에서 최대값을 구합니다.

m 개로 나눌 수 있는 모든 경우의 수에서 나오는 부분 배열의 최대값 중에서 가장 작은 값을 구하는 문제입니다.

예를 들어 부분 배열 A, B, C 로 나누는 경우와 D, E, F 로 나누는 경우가 있다고 가정합니다.

A, B, C 의 각 부분 합 중에서 최대 값은 sum(A) 입니다.

D, E, F 의 각 부분 합 중에서 최대 값은 sum(D) 입니다.

sum(A) 와 sum(D) 중에서 더 작은 값인 sum(D) 가 이 문제에서 구하는 답입니다.

min(max(sum(A), sum(B), sum(C)) , max(sum(D), sum(E), sum(F)))

Solution

Binary Search 로 구할 수 있습니다.

일반적인 이진탐색이랑 좀 다르게 여기서는 범위가 인덱스가 아닌 합(sum) 입니다.

해당 배열에서 나올 수 있는 가장 작은 합과 가장 큰 합을 구합니다.

minSum 은 배열의 원소가 하나인 경우이고, 가장 큰 원소 값이 minSum 이 됩니다.

maxSum 은 모든 배열을 더하면 됩니다.

minSum 과 maxSum 을 범위로 하여 이진 탐색을 시작합니다.

중간값 mid 를 기준으로 canSplit 함수를 호출합니다.

canSplit 함수에서는 부분배열의 합을 미리 정해두고 배열을 임의로 나누는 로직이 들어있습니다.

배열의 합을 더해가면서 기준값 targetSum 보다 값이 높아지면 부분 배열의 끝이라고 판단하고 count 를 더해줍니다.

count 가 m 보다 커진다면 지금 targetSum 값으로는 m 개보다 배열이 많이 쪼개진다는 뜻이므로 더 큰 값을 기준으로 삼아야 합니다.

lo = mid + 1;

만약 count 가 m 보다 같거나 작다면 최소값을 구하기 위해 기준을 좀 더 낮춰서 다시 확인합니다.

hi = mid - 1;

이렇게 이진 탐색을 전부 완료하고 남은 값이 배열을 m 개만큼 쪼갠 경우에 구할 수 있는 가장 작은 최대값입니다.

Java Code

class Solution {
    public int splitArray(int[] nums, int m) {
        int minSum = 0, maxSum = 0;

        for (int num : nums) {
            minSum = Math.max(minSum, num);
            maxSum += num;
        }

        int lo = minSum, hi = maxSum;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;

            if (canSplit(mid, nums, m)) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        return lo;
    }

    public boolean canSplit(int targetSum, int[] nums, int m) {
        int count = 1, sum = 0;

        for (int num : nums) {
            sum += num;

            if (sum > targetSum) {
                count++;
                sum = num;  // first element of next subarray

                if (count > m) {
                    return false;
                }
            }
        }

        return true;
    }
}

Problem

• 문제 링크

주어진 String 에서 중복되지 않는 첫 번째 문자의 인덱스를 구하는 문제입니다.

Solution

Note 를 보면 문자열은 소문자로만 이루어져 있기 때문에 26 개의 int 배열을 선언해서 모든 문자의 갯수를 담습니다.

다시 문자를 쭉 돌면서 갯수가 1 인 문자의 인덱스를 리턴하면 O(n) 에 풀 수 있습니다.

만약 소문자만 해당되지 않는다면 HashMap 을 쓰면 됩니다.

Java Code

class Solution {
    public int firstUniqChar(String s) {
        int[] letters = new int[26];

        for (char c : s.toCharArray()) {
            letters[c - 'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (letters[c - 'a'] == 1) {
                return i;
            }
        }

        return -1;
    }
}

Kotlin Code

class Solution {
    fun firstUniqChar(s: String): Int = s
        .groupingBy { it }
        .eachCount()
        .mapTo(mutableListOf()) { it }
        .firstOrNull { it.value == 1 }
        ?.let { s.indexOf(it.key) } ?: -1
}

Problem

• 문제 링크

자연수 numRows 가 주어지면 해당 수를 높이로 갖는 파스칼의 삼각형을 만들면 됩니다.

Solution

주어진 대로 2중 for 문으로 구하면 됩니다.

파스칼 삼각형의 양 끝은 1 이기 때문에 처음과 시작에 1 을 넣고 나머지는 바로 윗 층의 List 를 꺼내서 구합니다.

Java Code

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>(1);

            if (i != 0) {
                row.add(1);
            }

            for (int j = 0; j < i - 1; j++) {
                List<Integer> before = res.get(i - 1);
                row.add(before.get(j) + before.get(j + 1));
            }

            row.add(1);
            res.add(row);
        }

        return res;
    }
}

Problem

• 문제 링크

두 ListNode 를 받으면 합쳐서 오름차순으로 정리된 ListNode 를 return 하면 됩니다.

Solution

return 값이 ListNode 라는 걸 이용해서 재귀로 뒤에 붙이면 됩니다.

Java Code

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

Kotlin Code

class Solution {
    fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? = when {
        l1 == null -> l2
        l2 == null -> l1
        l1.`val` < l2.`val` -> l1.apply { next = mergeTwoLists(l1.next, l2) }
        else -> l2.apply { next = mergeTwoLists(l1, l2.next) }
    }
}

Problem

• 문제 링크

로마 문자가 주어지면 숫자로 바꾸는 문제입니다.

Solution

싫어요가 많을 만한 문제입니다.

별다른 풀이는 없고 그냥 문제에서 주어진 대로 구현하면 됩니다.

주의할 점은 I, X, C 는 바로 뒤에 나오는 문자가 지금 문자보다 크면 숫자를 더하지 말고 빼야 한다는 점입니다.

Java Code

class Solution {
    public int romanToInt(String s) {
        int sum = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int num = getNumber(c);

            if (i + 1 == s.length()) {
                sum += num;
                continue;
            }

            char next = s.charAt(i + 1);

            // 바로 뒤에 나오는 숫자보다 작으면 숫자를 빼야함
            if (num < getNumber(next)) {
                sum -= num;
            } else {
                sum += num;
            }
        }

        return sum;
    }

    public int getNumber(char character) {
        switch(character) {
            case 'V': { return 5; }
            case 'X': { return 10; }
            case 'L': { return 50; }
            case 'C': { return 100; }
            case 'D': { return 500; }
            case 'M': { return 1000; }
            default: { return 1; }
        }
    }
}