예상 알고리즘 문제

Two Sum

 

문제 개요:

 

• 배열에서 두 숫자를 찾아서 더했을 때 목표 값이 되는 쌍을 찾는 문제.

 

해결 방법:

 

• 배열을 한 번 순회하면서 현재 숫자의 보완 값(목표값 - 현재값)이 해시맵에 있는지 확인합니다.

• 해시맵에 없다면, 현재 값을 해시맵에 저장합니다. 이렇게 하면 O(n) 시간 복잡도로 해결 가능합니다.

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

 

Merge Intervals

 

문제 개요:

 

• 주어진 여러 간격(interval)을 병합하는 문제.

 

해결 방법:

 

• 먼저 각 간격을 시작점을 기준으로 정렬합니다.

• 각 간격을 순차적으로 순회하면서 겹치는 간격이 있으면 병합하고, 겹치지 않으면 새로운 간격을 결과에 추가합니다.

public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;

    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    List<int[]> result = new ArrayList<>();
    int[] currentInterval = intervals[0];
    result.add(currentInterval);

    for (int[] interval : intervals) {
        if (currentInterval[1] >= interval[0]) {
            currentInterval[1] = Math.max(currentInterval[1], interval[1]);
        } else {
            currentInterval = interval;
            result.add(currentInterval);
        }
    }

    return result.toArray(new int[result.size()][]);
}

 

Longest Substring Without Repeating Characters

 

문제 개요:

 

• 중복되지 않는 가장 긴 부분 문자열을 찾는 문제.

 

해결 방법:

 

• 슬라이딩 윈도우와 해시셋을 이용해, 두 포인터로 윈도우를 확장하면서 중복되는 문자가 있으면 왼쪽 포인터를 이동시켜 해결합니다.

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0, maxLength = 0;

    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(s.charAt(right));
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

Top K Frequent Elements

 

문제 개요:

 

• 배열에서 가장 빈도수가 높은 K개의 요소를 찾는 문제.

 

해결 방법:

 

• 각 숫자의 빈도를 카운팅한 후, 우선순위 큐(힙)를 사용해 빈도수가 높은 K개의 요소를 추출합니다.

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> frequencyMap = new HashMap<>();
    for (int num : nums) {
        frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
    }

    PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> frequencyMap.get(a) - frequencyMap.get(b));

    for (int num : frequencyMap.keySet()) {
        heap.add(num);
        if (heap.size() > k) heap.poll();
    }

    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        result[i] = heap.poll();
    }
    return result;
}

 

Product of Array Except Self

 

문제 개요:

 

• 배열에서 자기 자신을 제외한 모든 요소의 곱을 구하는 문제.

 

해결 방법:

 

• 왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 두 번 순회하면서 곱을 계산합니다. 즉, 나누기 없이 각 요소를 제외한 곱을 구합니다.

public int[] productExceptSelf(int[] nums) {
    int[] result = new int[nums.length];
    int left = 1;

    for (int i = 0; i < nums.length; i++) {
        result[i] = left;
        left *= nums[i];
    }

    int right = 1;
    for (int i = nums.length - 1; i >= 0; i--) {
        result[i] *= right;
        right *= nums[i];
    }

    return result;
}

Maximum Subarray

 

문제 개요:

 

• 연속된 부분 배열에서 가장 큰 합을 구하는 문제.

 

해결 방법:

 

• 카데인 알고리즘을 사용하여 현재까지의 최대 합과 현재 부분 배열의 합을 비교하면서 가장 큰 합을 갱신합니다.

public int maxSubArray(int[] nums) {
    int currentSum = nums[0], maxSum = nums[0];

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

    return maxSum;
}

LRU Cache

 

문제 개요:

 

• 자주 사용되지 않은 항목을 제거하는 캐시를 구현하는 문제.

 

해결 방법:

 

• LinkedHashMap 또는 Doubly Linked List와 HashMap을 사용해 삽입, 삭제, 조회를 O(1)로 구현합니다.

class LRUCache {
    private final int capacity;
    private final Map<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        cache.put(key, value);
    }
}