시간복잡도 가이드

입력 크기별 시간복잡도 판단 기준

입력 크기 100,000 이상

• O(n^2) → 시간 초과 가능성 매우 높음
• O(nlogn), O(n), O(logn) 등으로 해결해야 함

방법 1: 정렬 활용 (O(nlogn))

import java.util.*;

public class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant); // O(nlogn)
        Arrays.sort(completion);  // O(nlogn)

        for (int i = 0; i < completion.length; i++) {
            if (!participant[i].equals(completion[i])) {
                return participant[i];
            }
        }
        return participant[participant.length - 1];
    }
}

방법 2: 해시맵 활용 (O(n))

import java.util.*;

public class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> counter = new HashMap<>();

        for (String name : participant) {
            counter.put(name, counter.getOrDefault(name, 0) + 1);
        }

        for (String name : completion) {
            counter.put(name, counter.get(name) - 1);
        }

        for (Map.Entry<String, Integer> entry : counter.entrySet()) {
            if (entry.getValue() > 0) {
                return entry.getKey();
            }
        }

        return "";
    }
}

입력 크기 약 1,000

• O(n^3) → 위험할 수 있음
• O(n^2), O(nlogn), O(n) 권장

입력 크기 수십 ~ 수백

• 완전탐색 사용 가능
• O(n^3), O(n^4)도 무리 없이 통과 가능

순열·조합을 요구하는 문제

• 일반적으로 O(n!)의 시간복잡도
• 제한사항이 매우 작게 주어짐 (ex. 길이 7 이하)

자주 쓰이는 시간복잡도

알고리즘	시간복잡도	설명
정렬 (기본 sort)	O(nlogn)	대부분의 내장 정렬 함수 사용
해시맵 구축	O(n)	배열을 해시맵으로 변환
해시맵 검색	O(1)	key 기반 조회
이진탐색	O(logn)	정렬된 배열에서 탐색
힙 (우선순위 큐)	O(logn)	삽입/삭제 시마다 log 시간 소요

Two Sum 문제

문제: 정수 배열에서 두 수를 더해 target이 되는 경우가 있는지 확인하라.

방법 1: 완전탐색 (O(n^2))

public class TwoSumChecker {
    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{};
    }
}

• 가장 단순한 방법
• 작은 입력에만 적합

방법 2: 정렬 + 투포인터 (O(nlogn))

import java.util.Arrays;

public class TwoSumChecker {
    public static boolean twoSum(int[] nums, int target) {
        Arrays.sort(nums); // O(nlogn)
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) return true;
            else if (sum < target) left++;
            else right--;
        }

        return false;
    }
}

• 정렬 후 양쪽에서 접근
• 정렬 비용 포함 전체 O(nlogn)

방법 3: 해시맵 이용 (O(n))

import java.util.*;

public class TwoSumChecker {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[]{seen.get(complement), i};
            }
            seen.put(nums[i], i);
        }
        return new int[]{};
    }
}

• 배열을 순회하며 필요한 수를 해시맵에서 조회
• 시간복잡도 O(n)

시간복잡도 활용법

1. 입력 크기 확인 → 가능한 시간복잡도 예측
2. 완전탐색 or 효율적인 알고리즘 판단
3. 여러 가지 풀이 방식 구상
4. 각 방식의 시간복잡도 계산 및 비교
5. 최종 코드 작성