Problem

• 문제 링크

주어진 리스트 노드가 싸이클을 형성하는 지 찾는 문제입니다.

Solution

토끼와 거북이 알고리즘을 응용하면 됩니다.

주어진 노드를 fast 와 slow 에 옮겨담습니다.

fast 노드는 2 씩 움직이고 slow 노드는 1 씩 움직입니다.

싸이클이 존재한다면 fast 와 slow 는 싸이클에 빠져서 무한히 반복되는데, fast 노드가 slow 노드보다 1 씩 빠르기 때문에 거리가 1 씩 줄어들어 언젠가는 만나게 됩니다.

만약 앞서 나가던 fast 노드가 null 을 마주친다면 싸이클이 존재하지 않는 거라서 false 를 리턴하면 됩니다.

Java Code

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                return true;
            }
        }

        return false;
    }
}

Problem

• 문제 링크

리스트 두 개가 주어졌을 때 두 리스트의 겹치는 부분의 HeadNode 를 리턴하는 문제입니다.

Solution

이 문제에서 핵심은 두 리스트의 길이가 다를 때도 O(N) 시간복잡도에 O(1) 공간복잡도에 구해야 한다는 점입니다.

원래라면 힘들겠지만 가능하도록 만드는 문제의 조건이 여러개 있습니다.

1. A 리스트와 B 리스트의 중복된 부분은 값만 중복되는 게 아니라 주소값 자체가 중복된다.
2. 이 문제에서 만들어지는 모든 리스트는 싸이클이 형성되지 않는다.

간단히 코드 설명을 하면 다음과 같습니다.

각 헤드 노드를 a, b 변수에 담습니다.

while 문으로 a != b 여부를 확인하면서 노드 순회를 진행합니다.

1 번 조건으로 인해 값을 직접 비교하지 않고 주소값을 비교해도 일치 여부를 확인할 수 있습니다.

각 리스트가 끝에 도달하면 다른 리스트의 헤드로 이동합니다

그리고 마찬가지로 노드를 계속 순회하고 끝에 도달하는 순간 종료됩니다.

이렇게 하면 두 리스트의 길이가 달라도 A+B 의 길이는 같기 때문에 동일하게 비교할 수 있습니다.

간단하게 문자로 표현해봅니다.

A: a1 -> a2 -> a3 -> c1 -> c2
B: b1 -> b2 -> c1 -> c2

while 문으로 비교
a1 -> a2 -> a3 -> c1 -> c2 -> b1 -> b2 -> c1 -> c2 -> null
b1 -> b2 -> c1 -> c2 -> a1 -> a2 -> a3 -> c1 -> c2 -> null

2 번 조건으로 문제에서 등장하는 모든 노드는 싸이클이 형성되지 않기 때문에 무조건 마지막에 둘 다 null 값이 되며 반복분이 종료됩니다.

Java Code

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
                ListNode a = headA, b = headB;

        while (a != b) {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }

        return a;
    }
}

Problem

• 문제 링크

주어지는 숫자 n 이 3 의 x 제곱수가 되는지 확인하는 문제입니다.

Solution

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

3 의 배수인지 확인한 후에 3 으로 계속 나눕니다.

계속 나눈 값이 3 의 배수가 아닐 때의 값이 1 이면 3 의 제곱수고 아니면 다른 숫자가 섞여 있는 겁니다.

n == 0 인 케이스만 예외처리 해주면 간단하게 풀리는 문제입니다.

Java Code

// iterative
class Solution {
    public boolean isPowerOfThree(int n) {
        if (n == 0) return false;

        while (n % 3 == 0) {
            n /= 3;
        }

        return n == 1;
    }
}

// recursive
class Solution {
    public boolean isPowerOfThree(int n) {
        return n == 1 || n > 0 && n % 3 == 0 && isPowerOfThree(n / 3);
    }
}

Problem

• 문제 링크

나는 강도고 배열은 내가 털 집의 돈을 순서대로 나타냅니다.

인접한 두 집을 동시에 털면 경찰에 알림이 가기 때문에 피해야 합니다.

하루에 훔칠 수 있는 가장 많은 돈을 구하는 문제입니다.

Solution

DP 로 해결할 수 있습니다.

dp 배열을 선언했다고 가정할 때 dp[i] 는 i 번까지의 집까지 도달했을 때 훔친 돈의 Max 값 이라고 생각하면 됩니다.

그럼 i 번째 집에서 도둑이 얻을 수 있는 Max 의 경우의 수는 다음 둘 중 하나입니다.

1. i - 2 번째 집까지 털었던 Max 값 + i 번째 집의 돈
2. i - 1 번째 집까지 털었던 Max 값

이렇게 마지막 집까지 쭉 확인하고 남은 마지막 인덱스 값이 Max 값이 됩니다.

Java Code

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        nums[1] = Math.max(nums[0], nums[1]);

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

        return nums[nums.length - 1];
    }
}

Kotlin Code

class Solution {
    fun rob(nums: IntArray): Int = when (nums.size) {
        0 -> 0
        1 -> nums.first()
        else -> {
            nums[1] = maxOf(nums[0], nums[1])

            for (i in 2..nums.lastIndex) {
                nums[i] = maxOf(nums[i - 1], nums[i - 2] + nums[i])
            }

            nums.last()
        }
    }
}

Problem

• 문제 링크

주어진 배열을 하나의 숫자로 생각하고 1 을 더한 결과 배열을 리턴하면 됩니다.

[1, 2, 3] 은 123 으로 생각하고 1 을 더한 [1, 2, 4] 배열을 리턴합니다.

[9, 9] 는 100 이 되기 때문에 [1, 0, 0] 을 리턴해야 하고 배열로 [0, 0] 이 주어지기도 합니다.

Solution

배열의 마지막 원소부터 더해줍니다.

만약 1 을 더한 값이 10 미만이라면 추가적인 처리가 필요 없기 때문에 바로 digits 값을 리턴합니다.

만약 10 이 넘는다면 0 으로 변경해줍니다.

인덱스 0 까지 모두 순회 했는데도 메소드가 끝나지 않았다는건 자릿수 변화가 있다는 뜻입니다.

새로운 배열 res 를 선언하고 나머지 res[0] = 1 처리만 해주고 리턴합니다.

처음엔 digits 배열을 덮어쓰려고 했으나 전부 0 으로 바뀌어서 어차피 결과는 동일합니다.

Java Code

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;        

        for (int i = n - 1; i >= 0; i--) {
            digits[i]++;

            if (digits[i] < 10) {
                return digits;
            }

            digits[i] = 0;
        }

        int[] res = new int[n + 1];
        res[0] = 1;

        return res;
    }
}

Problem

• 문제 링크

문자열을 그룹으로 나누어서 {갯수}{숫자}{갯수}{숫자} 형식의 문자열로 다시 만들면 됩니다.

Solution

1 만 고정된 문자열을 리턴하기 때문에 무조건 1 까지 갔다 와야 합니다.

재귀를 이용해서 n-1 의 문자열 값을 구하고 다시 계산해서 리턴합니다.

같은 숫자여도 구간이 다르면 카운트를 따로 해야 하기 때문에 HashMap 에 담으면 안되고 직접 비교하면서 세야 합니다.

Java Code

class Solution {
    public String countAndSay(int n) {
        if (n == 1) return "1";

        StringBuilder sb = new StringBuilder();
        String s = countAndSay(n - 1);
        char value = s.charAt(0);
        int count = 1;

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

            if (value == c) {
                count++;
                continue;
            }

            sb.append(Integer.toString(count)).append(value);
            value = c;
            count = 1;
        }

        sb.append(Integer.toString(count)).sb.append(value);

        return sb.toString();
    }
}

Problem

• 문제 링크

문제에서 주어진 조건대로 Min Stack 을 구현하는 문제입니다.

일반 Stack 과 똑같지만 getMin() 이라는 메소드로 스택의 최소값을 뽑을 수 있습니다.

Solution

바로 떠올릴 수 있는 방법은 Stack 을 두 개 사용해서 구현하는 겁니다.

한 개는 최소값만 보관하고 한 개는 일반적인 스택으로 사용합니다.

공간복잡도를 줄이기 위해 변수 하나만 사용해서 구현하는 방법이 있습니다.

최소값을 보관하는 min 변수를 선언합니다.

이 값에는 getMin() 호출 시에 리턴할 최소값을 유지하고 있습니다.

이제 최소값이 pop 되었을 때, 다음 최소값을 어떻게 알 수 있는지가 문제입니다.

방법은 push 로 인해 최소값이 갱신될 때 min 을 바꾸기 전에 Stack 에 하나 넣어두는 겁니다.

그리고 pop 한 값이 최소값과 동일하면 한번 더 pop 을 해서 min 에 넣어줍니다.

최소값이 pop 된 순간에 바로 밑에는 다음 최소값이 기록되어 있는 셈입니다.

Worst Case 일때는 스택 두개를 쓰는 것과 메모리 사용이 동일하지만 Best Case 일 때는 1/2 밖에 사용하지 않습니다.

Java Code

class MinStack {
    int min;
    Stack<Integer> stack;

    public MinStack() {
        min = Integer.MAX_VALUE;
        stack = new Stack<>();
    }

    public void push(int x) {
        if (x <= min) {
            stack.push(min);
            min = x;
        }

        stack.push(x);
    }

    public void pop() {
        if (stack.pop() == min) {
            min = stack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}

Problem

• 문제 링크

주어진 정렬된 배열에서 중복을 제거하여 배열(길이) 를 리턴하는 문제입니다.

Solution

처음 index 값을 1로 저장해놓습니다.

반복문을 돌면서 nums[i] 와 nums[i+1] 이 달라진다면 중복된 값이 끝났다는 뜻이기 때문에 nums[index] = nums[i+1] 로 새 값을 넣어줍니다.

반복문이 끝난 후 nums 배열의 index 길이만큼 중복이 제거된 상태가 됩니다.

이 문제는 특이하게 int 형을 return 하는데 nums 에서 return 한 길이까지가 제출하는 정답이 되는 것 같습니다.

Java Code

class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 1;

        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] != nums[i + 1]) {
                nums[index++] = nums[i + 1];
            }
        }

        return index;
    }
}