Problem

• 문제 링크

nums 배열 안의 숫자 중 합이 target 이 되는 인덱스 두개를 배열로 리턴하면 됩니다.

Solution

for 문을 두번 돌면서 일일이 전부 비교하면 O(n^2) 에 답을 구할 수 있습니다.

Map 자료구조를 사용하여 O(n) 에 푸는 것입니다.

Map 에는 지나온 target - nums[i] 와 index 를 저장합니다.

만약에 map.containsKey 가 존재한다면 현재의 nums[i] 와 더해서 target 이 되는 값이 존재한다는 뜻입니다.

Map 에 있는 값이 무조건 이전 index 이므로 먼저 출력합니다.

Java Code

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return new int[]{map.get(nums[i]), i};
            }

            map.put(target - nums[i], i);
        }

        return new int[]{-1, -1};
    }
}

Kotlin Code

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = HashMap<Int, Int>()

        for ((i, value) in nums.withIndex()) {
            map[target - value]?.let { return intArrayOf(it, i) }
            map[value] = i
        }

        return intArrayOf()
    }
}

Problem

• 문제 링크

주어진 배열에서 가장 큰 구간합을 구하는 문제입니다.

Solution

DP 로 풀면 O(n) 에 구할 수 있습니다.

대신 별도의 배열을 따로 선언할 필요 없이 nums 배열에 덮어씁니다.

현재 값 nums[i] 와 지금까지의 지금까지의 합 nums[i-1] 을 더한 값과 그냥 현재값을 비교하여 어느 값이 더 큰지 확인합니다.

만약 nums[i-1] + nums[i] 값이 더 크다면 구간합이 유지된 상태로 계속 진행한다고 생각하면 됩니다.

만약 nusm[i] 값이 크다면 이전까지의 구간을 초기화 하고 새로운 구간을 시작합니다.

범위를 구하는 것이 아닌 원소의 합만 구하면 되기 때문에 sum 최대값을 저장합니다.

Java Code

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
            sum = Math.max(sum, nums[i]);
        }

        return sum;
    }
}

Problem

• 문제 링크

주어진 트리가 정확히 대칭을 이루는지 확인하는 문제입니다.

Solution

그냥 비교하면 되는 문제입니다.

null 체크만 확실히 합니다.

Java Code

// 1. Recursive
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || isEqual(root.left, root.right);
    }

    public boolean isEqual(TreeNode a, TreeNode b) {
        if (a == null || b == null) return a == b;
        if (a.val != b.val) return false;

        return isEqual(a.left, b.right) && isEqual(a.right, b.left);
    }
}

// 2. Iterative
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root.left);
        q.add(root.right);

        while (!q.isEmpty()) {
            TreeNode a = q.poll();
            TreeNode b = q.poll();

            if (a == null && b == null) continue;
            if (a == null || b == null) return false;
            if (a.val != b.val) return false;

            q.add(a.left);
            q.add(b.right);
            q.add(a.right);
            q.add(b.left);
        }

        return true;
    }
}

Problem

• 문제 링크

계단을 한번에 한개 또는 두개씩 오를 수 있을 때 n 개의 계단을 오르는 모든 경우의 수를 구하는 문제입니다.

Solution

피보나치랑 비슷하게 풀면 됩니다.

재귀로 하면 시간초과가 나기 때문에 DP 로 하거나 정 재귀로 하고싶다면 메모이제이션을 사용하면 됩니다.

Java Code

// using dp solution
class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1; dp[1] = 1;

        for (int i = 2; i < n+1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

// without extra memory
class Solution {
    public int climbStairs(int n) {
        int a = 0, b = 1;
        int res = a + b;

        for (int i = 0; i < n; i++) {
            res = a + b;
            a = b;
            b = res;
        }

        return res;
    }
}

Problem

• 문제 링크

주어진 n 이 Happy Number 에 해당하는 지 찾는 문제입니다.

Happy Number 여부를 판단하기 위해서는 다음과 같은 과정을 거쳐야 합니다.

1. n 을 각 자릿수별로 나눈다.
2. 나눈 수를 각각 제곱한 다음에 더한다.
3. 더한 수가 1이 되면 Happy Number

위 세 과정을 계속해서 반복하며 Happy Number 로 판단되는 경우 true 를 리턴하고 영원히 반복되는 Cycle 을 형성하는 경우 false 를 리턴합니다.

Solution

반복문을 사용해서 풀 수 있습니다.

간단한 풀이는 n 을 계속 계산하면서 HashSet 에 담아서 확인하는 겁니다.

만약 추가 메모리 없이 풀고 싶다면 투포인터를 사용하면 됩니다.

Cycle 을 이룰 경우 slow 와 fast 의 변수가 언젠가 같아지는 순간이 옵니다.

Java Code

class Solution {
    // Space Complexity O(n) using HashSet
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();

        while (n != 1) {
            if (!set.add(n)) {
                return false;
            }

            n = getNext(n);
        }

        return true;
    }

    // Space Complexity O(1)
    public boolean isHappy(int n) {
        int slow = getNext(n);
        int fast = getNext(getNext(n));

        while (slow != 1 && fast != 1) {
            if (slow == fast) {
                return false;
            }

            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }

        return true;
    }

    private int getNext(int num) {
        int sum = 0;

        while (num != 0) {
            sum += (num % 10) * (num % 10);
            num /= 10;
        }

        return sum;
    }
}

Problem

• 문제 링크

Stock 의 가격이 배열로 주어지고 한번만 사고 한번만 팔 수 있을 때 구할 수 있는 가장 큰 이익을 구하는 문제입니다.

Solution

한번만 사고 팔 수 있으므로 가장 싼 값에 사서 가장 비쌀 때 팔면 됩니다.

그런데 단순하게 maxPrice 값을 구하면 스톡을 사기 전 가격이 젤 비싼 경우가 발생합니다.

예제 1번만 봐도 배열의 최대값은 7, 최소값은 1 인데 스톡을 사기도 전에 판다는게 말이 안됩니다.

따라서 구해야될 최대값은 오늘 가격 - 최소 가격 의 최대값입니다.

minPrice 에서는 가장 작은 가격을 구하고 maxProfit 에는 해당 날의 가격에서 최소 가격을 뺀 이익의 최대값을 구합니다.

O(n) 의 시간복잡도가 소요되며, 끝나고 남은 maxProfit 이 답입니다.

Java Code

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }

        return maxProfit;
    }
}

Problem

• 문제 링크

숫자 n 을 이진수로 변환했을 때 1 비트의 갯수를 구하는 문제입니다.

Solution

시프트 연산을 진행하면서 풀면 됩니다.

주의할 점은 음수도 주어질 수 있기 때문에 >>> 연산을 사용해야 합니다.

Java Code

public class Solution {
    public int hammingWeight(int n) {
        int sum = 0;

        while (n != 0) {
            sum += (n & 1);
            n >>>= 1;
        }

        return sum;
    }
}

Kotlin Code

class Solution {
    fun hammingWeight(n:Int):Int = Integer.toBinaryString(n).count { it == '1' }
}

Problem

• 문제 링크

두 배열에서 중복되는 원소들을 모아서 만든 배열을 구하는 문제입니다.

Solution

각 배열에 같은 숫자가 여러 개 존재하면 겹치는 만큼 전부 리턴해야 하기 때문에 일반적인 교집합과는 조금 다릅니다.

결국 각 숫자에 있는 값들을 전부 비교하는 수밖에 없습니다.

원소의 범위가 정해져 있지 않으므로 HashMap 을 사용해서 개수를 비교하면 됩니다.

Folllow up 1 에서 두 배열이 정렬된 상태면 어떻게 최적화 가능하냐는 질문이 있습니다.

각 배열이 정렬된 상태라면 Two pointer 를 사용하여 풀 수 있습니다.

Follow up 2 에서 정렬된 상태이면서 한쪽 배열의 크기가 무조건 작을 경우 어떻게 최적화 하는 지 다시 물어봅니다.

nums1 배열의 크기가 작다면 nums1 배열을 전체 순회하면서 각 원소 값을 nums2 에서 이진 탐색을 이용하여 찾으면 됩니다.

중복된 값 처리 때문에 귀찮아서 구현은 생략합니다.

Java Code

// Normal Solution - Using HashMap O(n + m)
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>(); // <number, count>
        List<Integer> list = new ArrayList<>();

        for (int num : nums1) {
            map.merge(num, 1, Integer::sum);
        }

        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);

            if (count > 0) {
                list.add(num);
                map.put(num, count - 1);
            }
        }

        return list.stream().mapToInt(k -> k).toArray();
    }
}


// Follow up 1 - O(max(n, m))
// What if the given array is already sorted? 
// How would you optimize your algorithm?
// 두 배열이 정렬된 상태면 two-pointer 를 사용해서 최적화 가능
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        int i = 0, j = 0;

        Arrays.sort(nums1);
        Arrays.sort(nums2);

        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                list.add(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }

        return list.stream().mapToInt(k -> k).toArray();
    }
}