Problem

• 문제 링크

주어진 문자열을 섞어서 "balloon" 을 몇 개 만들 수 있는지 구하는 문제입니다.

Solution

String 을 순회하면서 balloon 각 문자의 갯수를 카운트 하면 됩니다.

문자 한 세트가 있어야 한 단어가 만들어지므로 가능한 balloon 의 갯수는 b, a, l, o, n 의 갯수의 최소값입니다.

l 과 o 는 두 번씩 나와야 단어가 완성되므로 나누기 2 해줍니다.

Java Code

class Solution {
    public int maxNumberOfBalloons(String text) {
        int[] count = new int[26];
        int min = Integer.MAX_VALUE;

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

        count['l' - 'a'] /= 2;
        count['o' - 'a'] /= 2;

        for (char c : "balloon".toCharArray()) {
            min = Math.min(min, count[c - 'a']);
        }

        return min;
    }
}

사실 그냥 단순하게 풀어도 됩니다.

class Solution {
    public int maxNumberOfBalloons(String text) {
        int b = 0, a = 0, l = 0, o = 0, n = 0;

        for (char ch : text.toCharArray()) {
            if (ch == 'b') b++;
            else if (ch =='a') a++;
            else if (ch == 'l') l++;
            else if (ch == 'o') o++;
            else if (ch == 'n') n++;
        }

        return Math.min(Math.min(b, a), Math.min(Math.min(l / 2, o / 2), n));
    }
}

Problem

• 문제 링크

이진 트리에서 같은 높이에 있는 노드들의 값을 묶는 문제입니다.

왼쪽에서 오른쪽 순서로 넣어야 합니다.

Solution

단순하게 DFS 로 해결하면 됩니다.

값을 담을 list 를 선언하고 왼쪽부터 차례대로 들어갑니다.

level 변수로 높이를 계속 갖고 들어가며 list.size() 가 level 과 같다면 새롭게 만난 높이이기 때문에 리스트를 추가해줍니다.

Java Code

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        traverse(res, root, 0);
        return res;
    }

    private void traverse(List<List<Integer>> list, TreeNode node, int level) {
        if (node == null) return;
        if (level == list.size()) {
            list.add(new ArrayList<>());
        }
        list.get(level).add(node.val);
        traverse(list, node.left, level + 1);
        traverse(list, node.right, level + 1);
    }
}

Problem

• 문제 링크

n * m 크기의 보드가 주어지고 각 칸에 존재하는 세포가 다음 세대가 되었을 때의 상태를 구하는 문제입니다.

Solution

각 세포는 상하좌우와 대각선까지 해서 총 8 명의 이웃이 있습니다.

문제에 나와있는 세포들의 생존, 사망 조건을 정리하면 다음과 같습니다.

# 살아있는 세포
  - 이웃이 2 명 미만이면 사망
  - 이웃이 3 명 초과면 사망
  - 이웃이 2, 3 명이면 현재 상태 그대로 진행
# 죽은 세포
  - 이웃이 3 명이면 생존
  - 그 외에는 현재 상태 그대로

단순하게 이중 for 문을 돌면서 8 방향 확인하면 됩니다.

주의해야 할 점은 변경된 세포의 상태를 바로 갱신해버리면 옆에 있는 세포의 조건을 검사할 때 꼬일 수 있다는 점입니다.

임시로 2차원 배열을 선언해서 해결할 수도 있지만 Follow up 에서 in-place 로 해결해보라고 나와있습니다.

board 의 값을 바로바로 갱신하되, 0 과 1 대신에 3 과 2 로 갱신해줍니다.

현재 죽음 - 다음 세대에 살아남 ⇒ 3
현재 생존 - 다음 세대에 죽음 ⇒ 2

이렇게 변경해주면 숫자만 보고 현재 상태와 다음 세대를 알 수 있습니다.

모든 검사가 끝나면 %2 연산으로 상태를 갱신해주면 됩니다.

Java Code

class Solution {
    public void gameOfLife(int[][] board) {
        int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
        int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};
        int n = board.length, m = board[0].length;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int lives = 0;

                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];

                    if (x < 0 || x >= n || y < 0 || y >= m) continue;
                    if (board[x][y] == 1 || board[x][y] == 2) lives++;
                }

                if (board[i][j] == 0 && lives == 3) board[i][j] = 3;
                if (board[i][j] == 1 && (lives < 2 || lives > 3)) board[i][j] = 2;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] %= 2;
            }
        }
    }
}

Problem

• 문제 링크

주어진 링크드 리스트를 홀수 번째 노드를 앞으로 짝수 번째 노드를 뒤로 하는 링크드 리스트를 만드는 문제입니다.

Solution

단순하게 반복하면 됩니다.

홀수 번째 노드를 순회하는 odd 와 짝수 번째 노드를 순회하는 even 노드를 선언합니다.

짝수 노드의 헤드는 evenHead 에 따로 저장해두고 odd 와 even 을 끝까지 이동시킵니다.

그리고 while 문이 끝난 후에는 odd 는 가장 마지막 값이기 때문에 evenHead 를 붙이고 맨 처음 저장된 head 를 리턴하면 됩니다.

Java Code

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) return head;

        ListNode odd = head, even = head.next, evenHead = even;

        while (odd.next != null && even.next != null) {
            odd.next = odd.next.next;
            even.next = even.next.next;
            odd = odd.next;
            even = even.next;
        }

        odd.next = evenHead;
        return head;
    }
}

Problem

• 문제 링크

nums 배열의 중복된 숫자를 찾는 문제입니다.

중복된 숫자는 여러번 나올수 있으며 나머지 숫자들은 전부 한번만 등장합니다.

nums 배열의 길이가 n 이라고 할 때 등장하는 숫자들의 범위는 1 ~ n 입니다.

Solution

토끼와 거북이 알고리즘으로 풀 수 있습니다.

nums 에 있는 값들을 인덱스로 취급해서 계속 이동합니다.

중복된 값이 최소 한개는 존재하기 때문에 반드시 싸이클이 생깁니다.

Input: [1,3,4,2,2]
1 -> 3 -> 2 (싸이클 시작점) -> 4 -> 2 (두번째 2) -> 4 -> 2 -> 4 -> ..

Input: [3,1,3,4,2]
3 (싸이클 시작점) -> 4 -> 2 -> 3 (두번째 3) -> 4 -> 2 -> ...

Input: [1,1]
1 (싸이클 시작점) -> 1 (두번째 1) -> 1 -> ...

Input: [1,1,2]
1 -> 1 -> 1 -> ...

Input: [4,1,2,3,4]
4 -> 4 -> 4 -> ...

토끼와 거북이 알고리즘을 사용하면 싸이클을 찾을 수 있을 뿐만 아니라 싸이클의 시작 지점을 찾을 수 있습니다.

싸이클은 중복된 숫자 인덱스부터 시작되기 때문에 싸이클의 시작 지점 값이 중복 값이 됩니다.

Java Code

class Solution {
    public int findDuplicate(int[] nums) {
        // find cycle
        int slow = nums[0], fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        // find cycle start point        
        int index = 0;
        while (slow != index) {
            index = nums[index];
            slow = nums[slow];
        }

        return index;
    }
}

Problem

• 문제 링크

String[] strs 값이 주어지면 Anagrams 을 이루는 단어들을 한 리스트로 묶어서 출력하는 문제입니다.

Anagrams 이란 문자의 순서를 바꾸어서 만들 수 있는 다른 문자를 말하며

간단히 생각하면 같은 숫자의 문자들로 이루어진 String 들을 하나로 묶으면 됩니다.

주어지는 값은 모두 소문자이며 출력 순서는 상관 없다는 조건이 있습니다.

Solution

Hash 로 문제를 해결할 수 있습니다.

주어진 문자열이 소문자 알파벳만으로 이루어졌다는 사실을 통해서 해시를 구현할 수 있습니다.

길이 26 의 int 배열을 선언한 뒤에 알파벳 숫자만큼 카운팅 합니다.

예를 들어 bacc 라는 문자열을 받았을 때 이걸 keyArray 로 변환한다면

[1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

이런 문자열이 됩니다.

accb 도 변환한다면 위와 같은 문자열이 됩니다.

Arrays.toString(int[] arr) 을 통해 배열을 통째로 String 으로 변환할 수 있습니다.

내부적으로 for 문과 StringBuilder 를 사용하기 때문에 시간복잡도는 O(N * K) 가 됩니다.

두 번째 솔루션은 다른 사람들의 Submission Code 를 참고했습니다.

두번째 솔루션과 같은 해시지만 배열 String 을 그대로 키 값으로 사용했던 것과 달리 Long 값을 사용합니다.

26 개의 소수값을 배열에 미리 넣어둔 뒤 알파벳의 갯수만큼 hashKey 값에 곱해줍니다.

이와 같은 풀이가 가능한 이유는 소수의 곱이라 다른 Anagrams 값과 중복될 일이 전혀 없기 때문입니다.

시간복잡도는 동일하게 O(N * K) 지만 Array to String 과정이 없기 때문에 세번째 솔루션이 미세하게 더 빠릅니다.

Java Code

// 1. 배열 자체를 String 으로 만들어서 키값으로 사용
// k 값이 작아서 그런건지 키값 String 길이가 길어서 그런건지 소트보다 속도는 느림
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            int[] count = new int[26];
            for (char c : str.toCharArray()) count[c - 'a']++;
            String key = Arrays.toString(count);

            if (!map.containsKey(key)) {
                map.put(key, new LinkedList<>());
            }

            map.get(key).add(str);
        }

        return new ArrayList<>(map.values());
    }
}


// 2. 소수값을 이용하여 hash key 값을 만듬
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 
                        23, 29, 31, 37, 41, 43, 47, 53, 
                        59, 61, 67, 71, 73, 79, 83, 89, 
                        97, 101};

        Map<Long, List<String>> map = new HashMap<>();

        for (String str : strs) {
            long hashKey = 1;
            for (char c : str.toCharArray()) {
                hashKey *= (long) primes[c - 'a'];
            }

            if (!map.containsKey(hashKey)) {
                map.put(hashKey, new LinkedList<>());
            }
            map.get(hashKey).add(str);
        }

        return new LinkedList<>(map.values());
    }
}

Problem

• 문제 링크

n * n 행렬을 90 도 회전하는 문제입니다.

새로운 배열을 사용하지 말고 in-place 로 풀어야 합니다.

Solution

위 아래 배열을 먼저 뒤집고 대각선 숫자들을 뒤집으면 됩니다.

Java Code

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // reverse up and down
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;

            }
        }

        // reverse diagonally
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

Problem

• 문제 링크

Input 배열이 주어졌을 때 Output 배열을 출력합니다.

Output 배열은 Input 배열과 길이가 같고 output[i] 는 input[i] 를 제외한 모든 input 배열 값들의 곱입니다.

Note 와 Follow up 을 보면 나누기를 쓰지 않고 O(n) 시간복잡도와 O(1) 공간복잡도로 구해야 합니다.

Solution

나누기를 쓰지 말라고 한 이유는 nums 배열의 모든 값을 곱한 뒤 for 문을 돌면서 / nums[i] 만 해주면 되기 때문입니다.

처음 위의 표를 Input 값 기준으로 왼쪽, 오른쪽으로 나누면 아래에 있는 표 처럼 바꿀 수 있습니다.

left -> right 에서는 이전 인덱스까지의 누적 곱을 넣어줍니다.

right -> left 에서는 반대방향으로 똑같이 곱해서 넣어줍니다.

처음에 Arrays.fill(res, 1) 를 사용하여 다 1 값으로 채운 뒤에 왼쪽에서 오른쪽으로 구할 때도 acc 변수를 사용했습니다.

그런데 Arrays.fill 하나 때문에 그런지 2ms 가 나와서 안쓰는 방향으로 구현했더니 1ms 100% 가 나왔습니다.

Java Code

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];

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

        int acc = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            acc *= nums[i + 1];
            res[i] *= acc;
        }

        return res;
    }
}