Problem

• 문제 링크

숫자만 존재하는 오름차순 배열이 주어집니다.

모든 값들은 2개씩 존재하고 단 하나의 값만 1개 존재합니다.

1개만 존재하는 값을 찾는 문제입니다.

Solution

그냥 Map 을 사용해도 되는 문제지만 추가 조건으로 O(log n) time and O(1) space 의 복잡도를 요구합니다.

이 조건을 만족하기 위해선 이분탐색이 필요합니다.

하지만 이 문제는 일반적인 이분탐색과 다르게 찾아야 하는 값이 따로 주어지지 않습니다.

그럼 범위를 절반으로 나누었을 때 왼쪽과 오른쪽 중 찾으려는 값이 있는 곳을 알 수 있을까요?

힌트는 "모든 숫자는 반드시 두개씩 존재한다" 입니다.

반드시 두개씩 연달아 존재하기 때문에 인덱스 위치를 파악해서 숫자를 비교하면 단 하나만 있는 값의 위치를 알 수 있습니다.

대신 현재 index 가 홀수인지 짝수인지에 따라 비교해야 하는 대상이 바뀌기 때문에 그 부분만 체크해주면 됩니다.

Java Code

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;

        while (left < right) {
            mid = (left + right) / 2;

            if (mid % 2 == 0 && nums[mid] == nums[mid + 1]) {
                // mid 위치가 짝수면 오른쪽 값이랑 비교하고 같으면 single 은 오른쪽에 있음
                left = mid + 2;
            } else if (mid % 2 == 1 && nums[mid] == nums[mid - 1]) {
                // mid 위치가 홀수면 왼쪽 값이랑 확인하고 같으면 single 은 오른쪽에 있음
                left = mid + 1;
            } else {
                // 위에 전부 해당 안되면 single 은 왼쪽에 있음
                right = mid;
            }

        }

        return nums[left];
    }
}

Problem

• 문제 링크

n 개의 rating 순서가 주어질 때, 만들어질 수 있는 팀의 갯수를 구하는 문제입니다.

팀을 만드려면 3 개의 rating 이 오름차순 또는 내림차순으로 존재해야 합니다.

Solution

팀의 인원은 반드시 3 명이라는 점에 주목할 수 있습니다.

3 명이라면 어떤 값을 가운데 기준으로 잡았을 때, 왼쪽에 있는 값은 더 작고 오른족에 있는 값은 더 커야 오름차순이 됩니다.

또는 반대가 되면 내림차순이 됩니다.

아래와 같은 순서로 코드를 작성하면 해결할 수 있습니다.

1. ratings 를 전체 순회하면서 가운데 기준값을 잡는다.
2. 기준값 기준으로 왼쪽에서 더 작은 값 갯수, 오른쪽에서 더 큰 값 갯수를 구해 곱한다 (오름차순인 팀 경우의 수)
3. 기준값 기준으로 왼쪽에서 더 큰 값 갯수, 오른쪽에서 더 작은 값 갯수를 구해 곱한다 (내림차순인 팀 경우의 수)
4. 두 값을 더하면 만들어질 수 있는 모든 팀의 수가 나온다.

예를 들어 그림으로 표현하면 위와 같습니다.

6 을 기준으로 오름차순은 168, 368, 568 이 존재하고 내림차순은 962, 964, 762, 764 이 존재합니다.

오름차순으로 봤을 때 왼쪽에는 1, 3, 5 세개가 있고 오른쪽에는 8 하나가 존재하기 때문에 오름차순 팀이 만들어질 수 있는 경우의 수는 1 * 3 입니다.

내림차순을 보면 왼쪽에 9, 7 이 존재하고 오른쪽에 4, 2 가 존재하기 때문에 내림차순 팀이 만들어질 수 있는 경우의 수는 2 * 2 입니다.

그러므로 가운데 숫자가 6 일때 만들 수 있는 팀은 7 개가 됩니다.

이런식으로 앞에서부터 모든 숫자에 하나씩 가운데 숫자를 대입하면서 끝까지 돌면 만들 수 있는 모든 팀의 갯수를 구할 수 있습니다.

Java Code

class Solution {
    public int numTeams(int[] rating) {
        int teamCount = 0;

        for (int mid = 0; mid < rating.length; mid++) {
            int leftSmaller = 0;
            int leftLager = 0;
            int rightSmaller = 0;
            int rightLager = 0;

            for (int left = 0; left < mid; left++) {
                if (rating[left] < rating[mid]) {
                    leftSmaller++;
                } else {
                    leftLager++;
                }
            }

            for (int right = mid + 1; right < rating.length; right++) {
                if (rating[right] < rating[mid]) {
                    rightSmaller++;
                } else {
                    rightLager++;
                }
            }

            teamCount += (leftSmaller * rightLager) + (leftLager * rightSmaller);
        }

        return teamCount;
    }
}

Problem

• 문제 링크

삼각형의 꼭대기부터 가장 아래로 가는 최단 거리를 구하는 문제입니다.

위에서 아래로 내려갈 때 이동할 수 있는 곳은 인접한 대각선 밖에 없습니다.

Solution

현재까지 이동한 거리를 누적해서 더해나가다가 마지막에 최소값을 구하면 됩니다.

사실 이 문제는 위에서 아래로 내려가는 것보다 아래에서 위로 올라가는 Bottom Up 방식이 더 쉽게 구현할 수 있습니다.

우선 누적합을 저장해두는 accSum 배열을 선언합니다.

그리고 아래층부터 step 을 따라 올라가며 이동할 수 있는 거리를 구합니다.

양쪽 모두에서 이동할 수 있으므로 두 숫자 중 최솟값과 현재 step 값을 더하는 방식으로 쭉쭉 올라가면 됩니다.

Java Code

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // init 0
        int[] accSum = new int[triangle.size() + 1];

        // bottom up
        for (int i = triangle.size() - 1; i >= 0; i--) {
            List<Integer> step = triangle.get(i);

            for (int j = 0; j < step.size(); j++) {
                int min = Math.min(accSum[j], accSum[j + 1]);
                accSum[j] = min + step.get(j);
            }
        }

        return accSum[0];
    }
}

Problem

• 문제 링크

로봇이 존재합니다.

로봇은 3 개의 명령어만 듣습니다.

• G: 앞으로 한칸 이동
• L: 왼쪽으로 90 도 회전
• R: 오른쪽으로 90 도 회전

로봇이 수행해야하는 일련의 명령어 리스트인 instructions 이 주어졌을 때, 이 로봇이 영원히 같은 위치를 순회하는 지 판단하는 문제입니다.

Solution

로봇을 움직이는건 굉장히 단순합니다.

(0, 0) 좌표에서 시작하여 처음 방향은 0 으로 설정합니다.

모든 행동을 완료한 후에 로봇의 상태만 확인하면 됩니다.

1. 행동을 완료했을 때 (0, 0) 위치에 있다면 몇번을 해도 같은 자리를 반복한다.
2. 행동을 완료했을 때 (0, 0) 위치는 아니지만 다른 방향을 보고 있다.

1 번은 너무 당연한 겁니다.

2 번은 example 3 에도 나와 있습니다.

다른 위치에 도달했을 때, 다른 방향을 보고 있다면 두번째 instructions 은 그 위치와 방향에서 새로 시작합니다.

그렇기 때문에 최대 4 번을 반복하면 원래 위치로 돌아옵니다.

반복문을 4 번 돌리면서 (0, 0) 위치에 돌아왔는지 확인해도 되지만, 위와 같은 방식으로 쉽게 확인할 수 있습니다.

Java Code

class Solution {
    public boolean isRobotBounded(String instructions) {
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        int x = 0, y = 0, dir = 0;

        for (char instruction : instructions.toCharArray()) {
            if (instruction == 'G') {
                x += dx[dir];
                y += dy[dir];
            } else if (instruction == 'L') {
                dir = (dir + 1) % 4;
            } else {
                dir = (dir + 3) % 4;
            }
        }

        // 1. 싸이클 완료후에 (0, 0) 에 있는지
        // 2. 또는 위치가 바꼈더라도 초기 방향과 다른 방향을 보고 있다면 
        //    4번 순회했을 시 원래 자리로 돌아옴
        return x == 0 && y == 0 || dir != 0;
    }
}

Problem

• 문제 링크

주어진 배열을 3 등분 합니다.

나뉘어진 각 부분배열들의 모든 합이 똑같게 되도록 3등분 할 수 있는지 묻는 문제입니다.

Solution

아이디어를 알면 쉽게 풀 수 있는데 모르면 굉장히 복잡해집니다.

가장 중요한 포인트는 다음 세개입니다.

1. non-empty 배열. 즉, 부분 배열에는 최소 하나의 원소가 존재
2. n 등분이 아니라 3 등분으로 숫자가 고정되어 있음
3. 모든 부분 배열의 합은 같음

위 조건들로 우리는 몇 가지 사실을 알 수 있습니다.

1. 주어진 배열의 합이 정확히 3 으로 나누어 떨어져야 함
2. 부분 배열의 합은 sum / 3 으로 고정되어 있음

부분 배열의 합을 미리 알고 있기 때문에 좀더 수월하게 답을 구할 수 있습니다.

각 부분 배열의 누적합 partition 이 목표값인 goal 에 도달하면 갯수를 하나씩 증가시킵니다.

count 가 3 이 되는 순간 조건이 성립합니다.

혹시 남은 원소가 있더라도 부분 배열의 합이 무조건 goal 이기 때문에 남은 원소의 합은 0 이 될 겁니다.

Java Code

class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int sum = 0;
        for (int a : arr) { sum += a; }

        // 3등분 했을 때 모두 같아야 하기 때문에 한 파트의 합은 무조건 sum/3 이다.
        int goal = sum / 3; 

        if (sum % 3 != 0) return false;

        int partition = 0, count = 0;
        for (int a : arr) {
            partition += a;

            if (partition == goal) {
                partition = 0;
                count++;
            }

            if (count == 3) {
                return true;
            }
        }

        return false;
    }
}

Problem

• 문제 링크

2진수 두개를 받아서 합한 결과를 리턴하는 문제입니다.

Solution

처음에는 2진수 -> 10진수 변환 후 더하려고 했는데 2진수 길이가 너무 길어서 그런지 NumberFormatException 이 발생했습니다.

그래서 그냥 1 의 자리부터 더한 다음에 뒤집는 방식으로 구현했습니다.

Stack 자료구조를 써도 됩니다.

Java Code

class Solution {
    public String addBinary(String a, String b) {
        int aIdx = a.length() - 1;
        int bIdx = b.length() - 1;

        int sum = 0;
        StringBuilder sb = new StringBuilder();

        while (aIdx >= 0 || bIdx >= 0) {
            if (aIdx >= 0) sum += a.charAt(aIdx--) - '0';
            if (bIdx >= 0) sum += b.charAt(bIdx--) - '0';

            sb.append(sum % 2);
            sum /= 2;
        }

        if (sum == 1) sb.append(sum);
        return sb.reverse().toString();
    }
}

Problem

• 문제 링크

주어진 배열의 원소 하나만 바꿔서 Non-decreasing Array 를 만드는 문제입니다.

문제에서 정의하는 Non-decreasing Array 란 그냥 오름차순 배열을 의미합니다.

Solution

생각보다 실수하기 쉬운 문제입니다.

우선 for 문을 돌면서 increasing 구간을 찾습니다.

하나도 없으면 true 를 리턴하고, 두 개 이상 나온다면 false 를 리턴합니다.

만약 increasing 구간이 한 개라면 nums[i] 와 nums[i + 1] 중 하나를 바꿔줘야 합니다.

• nums[i] 만 바꿨을 때의 반례 : [5,7,1,8]
• nums[i + 1] 만 바꿨을 때의 반례 : [4,2,3]

그래서 nums[i] 를 바꾼 경우의 배열 과 nums[i + 1] 를 바꾼 경우의 배열 두 가지를 각각 만들어서 체크해야 합니다.

하지만 배열을 두개나 만들어서 또 체크하는 건 시간적으로나 공간적으로 비효율적입니다.

우선 두 가지 사실을 생각해야 합니다.

1. nums[i] 값은 다음 차례에서는 확인하지 않는다.
2. nums[i] 값은 nums[i -1] 보다 커야한다.

1 번을 예를 들면 nums[0] 과 nums[1] 을 비교하고 난 후에는 nums[1] 과 nums[2] 만 비교합니다.

nums[0] 은 바뀌든 말든 의미가 없기 때문에 굳이 바꿔줄 필요가 없습니다.

2 번은 nums[i] 값과 nums[i + 1] 값 중 어느 값을 바꿔야 할지 결정할 수 있게 해줍니다.

결국 두 값 중 하나를 바꿔줘야 하는데 이걸 비교하는 시점에서는 nums[i] > nums[i + 1] 조건이 보장된 상태입니다.

만약 nums[i - 1] > nums[i + 1] 인데 nums[i] = nums[i + 1] 처리를 해버리면 무조건 false 상태가 됩니다.

nums = [10, 15, 5]

nums[i - 1] = 10
nums[i] = 15
nums[i + 1] = 5

// 설명
nums[i] 와 nums[i + 1] 중 하나를 무조건 바꿔줘야 하는데
nums[i] 를 5 로 바꿔버리면 nums[i - 1] 보다 작아진다.

Java Code

class Solution {
    public boolean checkPossibility(int[] nums) {
        boolean modified = false;

        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (modified) return false;
                modified = true;

                // 다음에 비교할 nums[i + 1] 값만 바꿔주면 됨
                if (i > 0 && nums[i - 1] > nums[i + 1]) {
                    nums[i + 1] = nums[i];
                }
            }
        }

        return true;
    }
}

Problem

• 문제 링크

각 돌들의 무게가 배열로 주어집니다.

가장 무거운 돌 하나와 두 번째로 무거운 돌 하나를 선택해서 둘을 부딪힙니다.

둘의 무게가 같다면 둘다 사라지고 한쪽이 더 크다면 작은 쪽은 사라지고 큰 놈은 두 돌의 무게의 차이 만큼 남습니다.

돌이 하나만 남을 때까지 반복했을 때 마지막으로 남은 돌의 무게는 얼마인지 구하는 문제입니다.

Solution 1 - 우선순위 큐

우선순위 큐를 사용합니다.

일반적으로 PriorityQueue<Integer> 는 작은 숫자가 먼저 나오기 때문에 Collections.reverseOrder() 를 사용하여 큰 수가 먼저 나오도록 선언합니다.

우선순위 큐가 비거나 size 가 1 이 될 때까지 두번씩 poll 하며 돌의 무게를 비교합니다.

둘이 같은 경우는 사라져야 하기 때문에 pq 에 추가하지 않습니다.

만약 돌의 무게가 다르다면 먼저 뽑은 y 가 더 큰 돌이므로 y - x 값을 pq 에 넣습니다.

pq 에 하나만 남는다면 무게를 리턴하고 아니면 0 을 리턴합니다.

Java Code 1

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int stone : stones) {
            pq.add(stone);
        }

        while (pq.size() > 1) {
            int y = pq.poll();
            int x = pq.poll();

            if (y != x) {
                pq.add(y - x);
            }
        }

        return pq.isEmpty() ? 0 : pq.poll();
    }
}

Solution 2 - 정렬

방법 자체는 단순하게 두 돌을 구한 뒤 한쪽은 없애고 차이만 남기면 됩니다.

그렇다면 문제는 돌 두개를 어떻게 고르느냐 하는 건데 전 그냥 정렬을 사용했습니다.

정렬하면 가장 끝에 있는 두 돌이 가장 무거운 돌들입니다.

정렬 후 : [..., x, y]

x 와 y 를 부딪히면 x 는 같거나 작기 때문에 무조건 없어지고 y = y - x 가 됩니다.

y - x 값을 배열에 다시 넣고 Arrays.copyOf 으로 마지막 인덱스를 없애줍니다.

이런식으로 쭉 반복하면 마지막에는 돌 하나만 남게됩니다.

Java Code 2

class Solution {
    public int lastStoneWeight(int[] stones) {
        for (int i = stones.length - 1; i > 0; i--) {
            Arrays.sort(stones);
            stones[i - 1] = stones[i] - stones[i - 1];
            stones = Arrays.copyOf(stones, i);
        }

        return stones[0];
    }
}