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

Problem

• 문제 링크

주어진 배열에서 중복되는 값이 있는지 찾는 문제입니다.

Solution

HashSet 을 사용하여 O(n) 에 풀 수 있습니다.

HashSet.add 함수는 이미 중복된 값이 있는 경우 false 를 리턴합니다.

Java Code

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for (int num : nums) {
            if (!set.add(num)) {
                return true;
            }
        }

        return false;
    }
}

Kotlin Code

class Solution {
    fun containsDuplicate(nums: IntArray): Boolean 
        = nums.toList().distinct().size != nums.size
}

Problem

• 문제 링크

주어지는 두 개의 String 이 anagram 을 이루는지 확인하는 문제입니다.

Solution

동일한 문자를 갖고 있는지 확인해야 하기 때문에 O(n) 을 벗어날 수는 없습니다.

조건 중에 알파벳 소문자만 주어진다는 조건을 활용하여 배열을 선언한 뒤 거기에 각 알파벳의 갯수를 담아둡니다.

s 문자열은 + 하고 t 문자열은 - 합니다.

만약 배열의 값이 모두 0 이라면 해당 문자열은 anagram 을 이룬다고 할 수 있습니다.

만약 주어지는 문자열의 범위가 넓어진다면 HashMap 을 사용하면 됩니다.

Java Code

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] stores = new int[26];

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

        for (char c : t.toCharArray()) {
            stores[c - 'a']--;
        }

        for (int e : stores) {
            if (e != 0) return false;
        }

        return true;
    }
}

Kotlin Code

class Solution {
  fun isAnagram(s: String, t: String) 
    = s.groupingBy { it }.eachCount() == t.groupingBy { it }.eachCount()
}

Problem

• 문제 링크

n 개의 균형 잡힌 괄호를 이루는 문자열의 모든 케이스를 구하는 문제입니다.

Solution

재귀를 사용하면 됩니다.

여는 괄호 ( 를 붙이는 경우와 닫는 괄호 ) 를 붙이는 경우에 따라서 재귀로 들어갑니다.

open 변수는 열 수 있는 괄호의 갯수, close 변수는 닫을 수 있는 괄호의 갯수입니다.

균형 잡힌 괄호를 만들어야 하기 때문에 close 변수는 open 변수보다 클 때만 붙일 수 있습니다.

만약 닫는 괄호가 더 많이 사용된 상태라면 이미 균형 잡힌 괄호가 아닙니다.

open 변수와 close 변수를 전부 사용해서 0 이 되버리면 문자열 s 를 결과 리스트에 담습니다.

Java Code

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        recursive(res, "(", n - 1, n);
        return res;
    }

    public void recursive(List<String> res, String s, int open, int close) {
        if (open == 0 && close == 0) {
            res.add(s);
            return;
        }

        if (open > 0) {
            recursive(res, s + "(", open - 1, close);
        }

        if (close > open) {
            recursive(res, s + ")", open, close - 1);
        }
    }
}

Problem

• 문제 링크

트리가 주어졌을 때 inorder 순회한 결과를 리턴하는 문제입니다.

Solution

많이 알려진 재귀로 풀면 O(n) 에 풀리겠지만 Follow up 에 다음 문장이 있었습니다.

Recursive solution is trivial, could you do it iteratively?

iterative 하게 푸는 방법은 Stack 을 이용해서 다음 4 개 플로우를 반복하면 됩니다.

1. 현재 노드의 왼쪽 자식 노드를 전부 Stack 에 담는다.
2. Stack 에서 하나 pop 해서 res 에 담는다. (재귀로 깊게 들어갔다가 빠져 나오면서 넣는 것과 비슷)
3. 현재 노드에서 오른쪽 자식 노드로 이동한다.
4. 현재 노드가 null 이 아니라면 1~3 의 과정을 반복한다.

그림을 통해 표현하면 다음과 같습니다.

녹색으로 칠해진 노드는 현재 노드인 node 를 나타낸다고 생각하시면 됩니다.

1. Root 에서 시작, 왼쪽 자식 노드를 전부 Stack 에 담는다.

[3, 2, 1] 순서로 담기게 되어 pop 할 때는 depth 가 깊은 순인 [1, 2, 3] 순서로 나옵니다.

2. Stack 에서 Pop 하면서 val 을 담는다. (1)

이때 오른쪽 노드의 상태를 확인합니다.

코드상으로는 node = node.right 로 매번 이동하지만, null 값이기 때문에 무시됩니다.

3. Stack 에서 Pop 하면서 val 을 담는다. (2)

4. Stack 에서 Pop 하면서 val 을 담는다. (3)

오른쪽 자식 노드가 null 이 아니기 때문에 이동합니다.

5. 1 번에서 했던 것처럼 현재 노드를 기준으로 왼쪽 자식 노드를 전부 Stack 에 담는다.

이후 과정은 현재 노드에서 1, 2, 3, 4 를 다시 반복하며 inorder 순회가 완성됩니다.

최종적으로는 노드의 숫자 순서대로 전부 출력됩니다.

Java Code

// 1. recursive
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        traverse(res, root);
        return res;
    }

    public void traverse(List<Integer> res, TreeNode node) {
        if (node == null) return;

        traverse(res, node.left);
        res.add(node.val);
        traverse(res, node.right);
    }
}

// 2. iterative
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;

        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.add(node);
                node = node.left;
            }

            node = stack.pop();
            res.add(node.val);
            node = node.right;
        }

        return res;
    }
}

Kotlin Code

class Solution {
    fun inorderTraversal(root: TreeNode?): List<Int> = root?.let {
        inorderTraversal(root.left) + root.`val` + inorderTraversal(root.right)
    } ?: listOf()
}

Problem

• 문제 링크

배열이 주어졌을 때 해당 배열의 모든 순열을 구해서 리턴하는 문제입니다.

Solution

Backtarcking 을 사용해서 풀면 됩니다.

보통 백트래킹을 사용할 때는 방문 체크를 하기위한 boolean 변수를 사용하는데 어차피 List 에 담을 거라면 굳이 그럴 필요 없이 contains 로 체크합니다.

문제에 제시된 조건 중에 nums 의 길이가 최대 6 이라서 상관없겠지만 만약 길이가 길다면 contains 보다는 boolean 배열을 사용하는 게 더 효율적입니다.

첫 번째 방법은 임시 리스트인 list 에다가 값을 담으면서 계속 재귀를 반복합니다.

list 의 사이즈가 nums 의 길이와 같아지면 최종 리턴값인 result 에 넣고 다시 재귀를 벗어날 때 다시 list 의 마지막 원소를 제거합니다.

두 번째 방법은 똑같이 백트래킹을 사용하지만 임시 리스트에 담지 않고 nums 배열의 원소를 swaop 하면서 푸는 방법입니다.

swap 함수를 이용하여 nums 의 원소 위치를 직접 바꾸고 마지막에 리스트에 담아서 result 에 넣습니다.

Java Code

// 1. without Swap
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtracking(nums, result, new ArrayList<>());
        return result;
    }

    public void backtracking(int[] nums, List<List<Integer>> result, List<Integer> list) {
        if (list.size() == nums.length) {
            result.add(new ArrayList<>(list));
            return;
        }

        for (int num : nums) {
            if (list.contains(num)) continue;

            list.add(num);
            backtracking(nums, result, list);
            list.remove(list.size() - 1);
        }
    }
}

// 2. with Swap
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtracking(nums, result, 0);
        return result;
    }

    public void backtracking(int[] nums, List<List<Integer>> result, int start) {
        if (start == nums.length) {
            List<Integer> list = new ArrayList<>();
            for (int num : nums) { list.add(num); }
            result.add(list);
            return;
        }

        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            backtracking(nums, result, start + 1);
            swap(nums, start, i);
        }
    }

    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

Kotlin Code

class Solution {
    fun permute(
        nums: IntArray,
        temp: List<Int> = listOf(),
        numsList: List<Int> = nums.toList()
    ): List<List<Int>> = when (numsList.size) {
        1 -> listOf(temp + numsList)
        else -> numsList.flatMap { num -> permute(nums, temp + num, numsList - num) }
    }
}

Problem

• 문제 링크

1 부터 주어진 n 까지의 숫자들을 순회하며 List<String> 을 만들면 됩니다.

3 의 배수에는 "Fizz", 5 의 배수에는 "Buzz" , 3 과 5 의 배수에는 "FizzBuzz" 넣고 나머지에는 숫자를 채워 넣으면 됩니다.

Solution

단순하게 풀면 됩니다.

Java Code

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>();

        for (int i = 1; i < n + 1; i++) {
            if (i % 15 == 0) {
                list.add("FizzBuzz");
            } else if (i % 3 == 0) {
                list.add("Fizz");
            } else if (i % 5 == 0) {
                list.add("Buzz");
            } else {
                list.add(Integer.toString(i));   
            }
        }

        return list;
    }
}

Kotlin Code

class Solution {
    fun fizzBuzz(n: Int): List<String> {
        return (1..n).map { it ->
            when {
                it % 15 == 0 -> "FizzBuzz"
                it % 3 == 0 -> "Fizz"
                it % 5 == 0 -> "Buzz"
                else -> it.toString()
            }
        }
    }
}

Problem

• 문제 링크

완성된 Linked List 가 이미 존재하면 입력으로 주어진 Node 를 삭제하면 됩니다.

Solution

처음에는 이해가 잘 안될 수도 있는데 Linked List 는 이미 존재하고 Input 으로 주어지는 건 삭제될 Node 한 개 뿐입니다.

처음에는 단순하게 node = node.next 로 하려고 했으나..

현재 Node 의 부모 노드를 prevNode 라고 할 때 prevNode.next 가 가리키고 있는 건 node 의 주소 값입니다.

그래서 현재 node 에 node.next 를 덮어 씌우더라도 prevNode.next 는 여전히 원래의 주소 값을 가리키고 있어서 변경되지 않습니다.

현재 노드의 주소를 변경하지 않은 채로 val 과 next 를 변경해주면 풀립니다.

문제 설명에 주어지는 노드는 tail node 가 아니라는 조건이 있기 때문에 별다른 예외처리는 필요 없습니다.

Java Code

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Kotlin Code

class Solution {
    fun deleteNode(node: ListNode?) {
        node?.`val` = node?.next?.`val`
        node?.next = node?.next?.next
    }
}