Problem

• 문제 링크

총 학생의 수, 체육복을 도난 당한 학생, 체육복을 더 가져온 학생 리스트가 주어졌을 때

체육 수업에 참여할 수 있는 학생의 수를 구하는 문제입니다.

체육복은 인접한 학생에게밖에 빌려주지 못하며 무조건 1벌의 여벌밖에 없습니다.

여벌의 체육복을 가져온 사람도 체육복을 하나 도난당할 수 있습니다.

Solution

학생 수만큼 clothes 배열을 선언하여 상태를 정의합니다.

lost 배열에 있으면 -1 하고 reserve 배열에 있으면 +1 합니다.

만약 여벌의 체육복이 있는데 도난당한 학생은 0 으로 본인의 체육복만 소지한 상태가 됩니다.

그 다음에 clothes 배열을 한번 돌면서 -1 인 index 의 앞 뒤를 확인하면서 1 이 있다면 0 으로 만들어주면 됩니다.

최종 결과는 배열에서 -1 값의 갯수를 리턴해줍니다.

Java Code

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] clothes = new int[n+2];
        int count = 0;

        for (int i : lost)    clothes[i]--;
        for (int i : reserve) clothes[i]++;
        
        for (int i = 1; i< n+1; i++) {
            if (clothes[i] == -1) {
                if (clothes[i-1] == 1) {
                    clothes[i-1]--;
                    clothes[i]++;
                } else if (clothes[i+1] == 1) {
                    clothes[i+1]--;
                    clothes[i]++;
                }
            }
            
            if (clothes[i] != -1) {
                count++;
            }
        }
        
        return count;
    }
}

Problem

• 문제 링크

난이도 Easy 문제입니다.

문자열이 주어졌을 때 이웃해있는 두 문자가 같은 문자면 제거해야합니다.

만약 제거한 후의 문자열에서 같은 케이스가 발견되면 계속 삭제합니다.

최종적으로 이웃하면서 중복된 문자가 없을때까지 반복해줍니다.

Solution 1

문자열 S 의 길이는 최대 20,000 이기 때문에 O(n) 시간복잡도로 푸는게 좋습니다.

일반적으로 풀면 S 한번 쭉 보면서 중복 제거, 다시 또 한번 보면서 중복 제거.. 이러면 O(n^2) 입니다.

시간을 줄이는 핵심적인 방법은 문자 두개를 제거했을 때

그 자리에 바로 이웃한 중복된 문자가 생기는지 확인하면 됩니다.

removed 배열을 하나 선언하여 문자열이 삭제되었는지 아닌지 체크합니다.

for 문을 돌면서 before 인덱스를 하나 선언한 뒤, 이웃한 두 문자를 삭제

이후 before--; i++; 로 그 다음으로 이웃한 두 문자를 계속 삭제하면 됩니다.

Java Code 1

class Solution {
    public String removeDuplicates(String S) {
        boolean[] removed = new boolean[S.length()];
        
        for (int i = 1; i < S.length(); i++) {
            int before = i-1;
                        
            while (!removed[before] && !removed[i] && S.charAt(before) == S.charAt(i)) {
                removed[before] = true;
                removed[i] = true;
                
                while (before > 0 && removed[before]) {
                    before--;
                }
                
                while (i < S.length()-1 && removed[i]) {
                    i++;
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < S.length(); i++) {
            if (!removed[i]) {
                sb.append(S.charAt(i));
            }
        }
        
        return sb.toString();
    }
}

Solution 2

Stack 으로 간단하게 푸는 방법도 있습니다.

for 문 돌면서 stack.peek() 값과 같으면 바로 이전에 있던 문자와 같은 문자이기 때문에 pop() 해줍니다.

만약에 같지않으면 그냥 push() 만 하면 됩니다.

Java Code 2

class Solution {
    public String removeDuplicates(String S) {
        Stack<Character> stack = new Stack<>();
                
        for (char c : S.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (char c : stack) {
            sb.append(c);    
        }
        
        return sb.toString();
    }
}

가끔 알고리즘 문제를 풀다보면 2차원 배열을 90도 회전시켜야 하는 문제가 있습니다.

2차원 배열을 90도, 180도, 270도 회전시키는 방법을 알아봅니다.

N * N 배열에서의 90도 회전

가로, 세로가 같은 n * n 배열에서는 좀더 쉽게 회전시킬 수 있습니다.

심지어 별도의 배열을 선언하지 않고 해당 배열의 값을 직접 회전시킬 수 있습니다.

아래 그림처럼 기준 선을 잡고 맞은편의 숫자들을 한번씩 교환해주면 됩니다.

Java Code

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

90도 회전

회전시키려는 arr 2차원 배열이 있습니다.

이 배열을 직사각형처럼 생각하면 90도 회전시켰을 때 가로, 세로가 바뀌게 됩니다.

따라서 가장 먼저 할 일은 배열의 n, m 을 바꾼 rotate 배열을 선언합니다.

그 후에 이중 for 문을 돌면서 rotate[i][j] = arr[n-1-j][i] 식으로

rotate 배열을 전부 채워주면 됩니다.

Java Code

// 90 rotate
static int[][] rotate(int[][] arr) {
    int n = arr.length;
    int m = arr[0].length;
    int[][] rotate = new int[m][n];

    for (int i = 0; i < rotate.length; i++) {
        for (int j = 0; j < rotate[i].length; j++) {
            rotate[i][j] = arr[n-1-j][i];
        }
    }

    return rotate;
}

90도, 180도, 270 도 회전

사실 90도 회전만 알아도 2번, 3번 반복으로 180도, 270도를 할 수 있지만

내친김에 나머지도 구현해보았습니다.

rotate 함수에서 degree 파라미터로 90, 180, 270 을 받아

회전시키는 함수입니다.

Java Code

static int[][] rotate(int[][] arr, int degree) {
    int[][] rotate;
    int n = arr.length;
    int m = arr[0].length;

    switch (degree) {
        case 90:
        case 270:
            rotate = new int[m][n];
            break;
        case 180:
            rotate = new int[n][m];
            break;
        default:
            throw new IllegalArgumentException();
    }

    for (int i = 0; i < rotate.length; i++) {
        for (int j = 0; j < rotate[i].length; j++) {
            switch (degree) {
                case 90:
                    rotate[i][j] = arr[n-1-j][i];
                    break;
                case 180:
                    rotate[i][j] = arr[n-1-i][m-1-j];
                    break;
                case 270:
                    rotate[i][j] = arr[j][m-1-i];
                    break;
            }
        }
    }

    return rotate;
}

전체 소스코드

class Main {
    public static void main(String[] args) {
        int[][] arr = {
            {1, 0, 0},
            {1, 1, 1},
            {1, 0, 1},
            {1, 0, 1}
        };

        print(arr);

        int[][] rotateArr;

        System.out.println("\n90");

        // 90 rotate
        rotateArr = rotate(arr, 90);
        print(rotateArr);

        System.out.println("\n180");

        // 180 rotate
        rotateArr = rotate(arr, 180);
        print(rotateArr);

        System.out.println("\n270");

        // 270 rotate
        rotateArr = rotate(arr, 270);
        print(rotateArr);

        System.out.println("\n360 (90 rotate)");

        // 90 rotate
        rotateArr = rotate(rotateArr);
        print(rotateArr);
    }

    static int[][] rotate(int[][] arr, int degree) {
        int[][] rotate;
        int n = arr.length;
        int m = arr[0].length;

        switch (degree) {
            case 90:
            case 270:
                rotate = new int[m][n];
                break;
            case 180:
                rotate = new int[n][m];
                break;
            default:
                throw new IllegalArgumentException();
        }

        for (int i = 0; i < rotate.length; i++) {
            for (int j = 0; j < rotate[i].length; j++) {
                switch (degree) {
                    case 90:
                        rotate[i][j] = arr[n-1-j][i];
                        break;
                    case 180:
                        rotate[i][j] = arr[n-1-i][m-1-j];
                        break;
                    case 270:
                        rotate[i][j] = arr[j][m-1-i];
                        break;
                }
            }
        }

        return rotate;
    }

    // 90 rotate
    static int[][] rotate(int[][] arr) {
        int n = arr.length;
        int m = arr[0].length;
        int[][] rotate = new int[m][n];

        for (int i = 0; i < rotate.length; i++) {
            for (int j = 0; j < rotate[i].length; j++) {
                rotate[i][j] = arr[n-1-j][i];
            }
        }

        return rotate;
    }

    static void print(int[][] arr) {
        for (int i=0; i<arr.length; i++) {
            for (int j=0; j<arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}

출력

1 0 0 
1 1 1 
1 0 1 
1 0 1 

90
1 1 1 1 
0 0 1 0
1 1 1 0

180
1 0 1
1 0 1
1 1 1
0 0 1

270
0 1 1 1
0 1 0 0
1 1 1 1

360 (90 rotate)
1 0 0
1 1 1
1 0 1
1 0 1

Problem

• 문제 링크

무게추의 갯수와 무게가 주어졌을 때 주어진 무게추들로 만들 수 없는 가장 최소무게를 구하는 문제입니다.

Solution

문제 예시 3 1 6 2 7 30 1 를 정렬하면 1 1 2 3 6 7 30 이 됩니다.

반복문으로 정렬한 숫자들을 하나씩 더해가면서 누적합을 구합니다.

만약 다음 원소값이 누적합 + 1 보다 크다면 누적합 + 1은 만들지 못하는 무게입니다.

처음에는 누적합까지의 무게는 전부 다 만들 수 있다는 전제가 어떻게 만들어진지 이해가 되지 않았습니다.

그런데 직접 해보면서 손으로도 따라해보니 어렴풋이 이해가 됩니다.

누적합 이라고 생각하지 말고 주어진 무게추들로 만들 수 있는 최댓값 이라고 생각하면 됩니다.

예를 들어 위 예시에서 1 1 2 까지의 누적합은 4 입니다.

1, 2, 3, 4 까지는 주어진 추 세개 1 1 2 로 전부 만들 수 있습니다.

그리고 여기에 새로운 무게추 3 이 추가된다면 누적합은 7 이 됩니다.

4 까지는 전부 만들수 있다는 걸 이전에 확인을 했고

새로운 5, 6, 7 은 각각 2+3, 3+3, 4+3 이 되고 2, 3, 4 는 1 1 2 의 추로 전부 구할 수 있었고 새로 추가된 3 무게추까지 있다면 5, 6, 7을 만들 수 있습니다.

시간복잡도는 정렬이 있기 때문에 O(n * logn) 이고 공간복잡도는 O(n) 입니다.

Java Code

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] weight = new int[n];

        for (int i=0; i<n; i++) {
            weight[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(weight);

        int sum = 0;
        for (int i=0; i<n; i++) {
            if (sum + 1 < weight[i]) {
                break;
            }

            sum += weight[i];
        }

        System.out.println(sum + 1);
    }
}

Problem

• 문제 링크

난이도 Medium 문제입니다.

빨간색, 파란색, 하얀색이 각각 0, 1, 2 로 주어지고 이 숫자들을 정렬하는 문제입니다.

단, 라이브러리에서 제공하는 정렬 함수를 사용하면 안됩니다.

Solution

문제에서는 Counting Sort 로 O(2n) 만에 풀 수 있다고 언급했습니다.

0, 1, 2 의 갯수를 센 다음에 0, 0, 1, 1, .. 이렇게 주르륵 나열하면 됩니다.

O(n) 시간복잡도와 O(1) 공간복잡도로 문제를 풀려면 문제에 제시된 조건을 파악해야합니다.

이 문제는 단 세가지 숫자 0, 1, 2 만으로 이루어져 있습니다.

포인터 세개를 이용하여 양 끝에 두개의 포인터를 두고 나머지 하나는 증가시키면서 0 과 2를 양끝으로 보내면 됩니다.

0 을 만나면 왼쪽으로, 2를 만나면 오른쪽으로 보내고 1은 신경쓰지 않습니다.

0과 2가 다 보내지고 나면 1은 자동으로 가운데에 남아있게 됩니다.

그리고 증가하던 i 포인터가 right 포인터와 만나면 더이상 swap 할 게 없기 때문에 종료합니다.

포인터의 위치를 신경쓰며 구현만 잘 해주면 풀 수 있습니다.

Java Code

class Solution {
    public void sortColors(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        for (int i=0; i<=right; i++) {
            if (nums[i] == 0) {
                swap(nums, i, left++);
            }
            
            if (nums[i] == 2) {
                swap(nums, i--, right--);
            }
        }
    }
    
    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

Problem

• 문제 링크

난이도 Easy 문제입니다.

배열이 주어졌을 때 한 숫자를 제외한 나머지는 모두 한 쌍으로 존재합니다.

중복되지 않는 숫자를 찾아서 리턴하는 문제입니다.

단, 추가 조건에 추가적인 메모리 사용 없이 O(n) 에 풀어보라고 나와있습니다.

Solution

O(n) 에 푸는건 쉽게 할 수 있습니다.

Map, Set, Array 등을 활용하여 중복된 숫자를 체크하면서 for 문 한번만 돌면 됩니다.

변수 하나로 풀려면 문제의 조건을 잘 봐야 합니다.

중복된 숫자는 무조건 한쌍입니다.

그리고 비트 연산자 중에 XOR 연산이라는 게 있습니다.

XOR 은 두 비트가 같으면 0 다르면 1 을 리턴해줍니다.

그리고 이 XOR 에는 같은 숫자에 대해 XOR 연산을 두번하면 자기 자신이 된다는 특징이 있습니다.

위에 강조한 두 가지를 이용하여 쉽게 풀 수 있습니다.

Java Code 1

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;

        for (int num : nums) {
            result ^= num;
        }

        return result;
    }
}

Java Code 2

// without using extra memory
class Solution {
    public int singleNumber(int[] nums) {
        for (int i=1; i<nums.length; i++) {
            nums[0] ^= nums[i];
        }

        return nums[0];
    }
}

Kotlin Code

class Solution {
    fun singleNumber(nums: IntArray) = nums.reduce { acc, i -> acc.xor(i) }
}

Problem

• 문제 링크

난이도는 Easy 입니다.

이진 트리가 주어지면 가장 큰 depth, 즉 트리의 height 를 구하는 문제입니다.

Solution

재귀로 간단하게 구할 수 있습니다.

root 에서 0 으로 시작하여 depth 를 계속 끌고 내려가면서 max 값을 구하면 됩니다.

node 가 null 이 되는 leaf node 에서는 depth 를 반환하기 때문에 가장 큰 depth 값을 구할 수 있습니다.

Java Code

class Solution {
    public int maxDepth(TreeNode root) {
        return goDepth(root, 0);
    }
    
    public int goDepth(TreeNode node, int depth) {
        if (node == null) return depth;
        
        return Math.max(goDepth(node.left, depth + 1), goDepth(node.right, depth + 1));
    }
}

Kotlin Code

class Solution {
    fun maxDepth(root: TreeNode?): Int {
        return goDepth(root, 0)
    }
    
    fun goDepth(node: TreeNode?, depth: Int): Int {
        node ?: return depth
        
        return maxOf(goDepth(node.left, depth + 1), goDepth(node.right, depth + 1))
    }
}