Problem

• 문제 링크

Medium 난이도의 문제입니다.

n 이하의 수들이 분모가 되고 각 수가 1 이하가 되도록 하는 수들의 리스트를 구하는 문제입니다.

Solution

단순하게 2중 for문으로 구하면 됩니다.

중복 확인은 Set 을 사용합니다.

Java Code

class Solution {
    public List<String> simplifiedFractions(int n) {
        List<String> result = new ArrayList<>();
        Set<Float> set = new HashSet<>();
        
        for (float i = 2; i <= n; i++) {
            for (float j = 1; j < i; j++) {
                float div = j/i;
                
                if (!set.contains(div)) {
                    int child = (int) j;
                    int parent = (int) i;
                    
                    result.add(child + "/" + parent);
                    set.add(div);
                }
            }
        }
        
        return result;
    }
}

Problem

• 문제 링크

Medium 난이도의 문제입니다.

k 를 만들 수 있는 피보나치의 합들을 찾고 그 중에서 갯수가 가장 작은 값을 구하는 문제입니다.

Solution

Greedy로 문제를 풀 수 있습니다.

k 보다 작은 피보나치 수열을 전부 TreeSet 에 담고 k 보다 작으면서 가장 큰 피보나치 수 를 계속해서 빼면 됩니다.

따로 증명은 안해봤지만 피보나치 수 중에 1, 1, 2, 3 이 있기 때문에

가장 큰 수부터 계속 빼면 어떻게든 0 으로 나누어 떨어질 것으로 생각되었습니다.

TreeSet.floor(n) 은 Set 에 n 이 존재하면 n 을 리턴, 아니라면 n 보다 작으면서 가장 가까운 수를 리턴합니다.

Java Code

class Solution {
    public int findMinFibonacciNumbers(int k) {
        if (k < 2) {
            return 1;
        }
        
        TreeSet<Integer> set = new TreeSet<>();
        
        for (int lo = 0, hi = 1; hi < k;) {
            int sum = lo + hi;
            set.add(sum);
            lo = hi;
            hi = sum;
        }
        
        int count = 0;
        
        while (k > 0) {
            int num = set.floor(k);
            k -= num;
            count++;
        }
        
        return count;
    }
}

Problem

• 문제 링크

2차원 배열 matrix 안에 target 값이 있으면 true

없으면 false 를 return 하는 문제입니다.

matrix 안의 숫자는 왼쪽에서 오른쪽으로 증가하고 위쪽에서 아래쪽으로 증가합니다.

Solution

왼쪽에서 오른쪽으로, 위에서 아래로 증가한다는 사실을 이용하면 O(n + m) 에 풀 수 있습니다.

오른쪽 위 혹은 왼쪽 아래 에서 시작하며 현재 값보다 target 이 크면 커지는 방향으로 이동하고 작으면 작아지는 방향으로 이동하면 됩니다.

예를 들어 왼쪽 아래에서 시작한다면 row = matrix.length - 1 이고 col = 0 에서 시작합니다.

만약 찾는 값이 현재 위치에 있는 값보다 작으면 작은쪽 (위쪽) 으로 이동합니다. (row--)

현재 위치에 있는 값보다 크면 커지는 쪽 (오른쪽) 으로 이동합니다. (col++)

Java Code

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) return false;

        int row = matrix.length - 1;
        int col = 0;

        while (row >= 0 && col < matrix[0].length) {
            int value = matrix[row][col];

            if (target == value) {
                return true;
            } else if (target < value) {
                row--;
            } else {
                col++;
            }
        }

        return false;
    }
}

Problem

• 문제 링크

n 이 주어졌을 때 1 ~ n 까지 숫자들 중에서 첫번째로 나오는 bad version 을 찾는 문제입니다.

bool isBadVersion(version) 함수는 VersionControl 클래스에 존재하고 Solution 클래스가 상속받고 있습니다.

Solution

단순하게 O(n) 으로 제출하면 시간초과가 납니다.

이진탐색 (BinarySearch) 으로 풀어야 하는 문제입니다.

대신 중간값을 구할 때 한가지 주의해야 합니다.

단순히 mid = (lo + hi) / 2 로 짜면 lo + hi 값이 int 범위를 벗어납니다.

안전하게 mid = lo + (hi - lo) / 2 로 하면 통과하기 때문에 앞으로 이진탐색을 사용할 때는 이렇게 구하는 습관을 들이면 좋습니다.

Java Code

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int lo = 1;
        int hi = n;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;

            if (isBadVersion(mid)) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        return lo;
    }
}