Java 코딩테스트 완벽 가이드 - Part 2: 필수 메서드 및 시간복잡도 총정리

readyoun

 

코딩테스트를 준비하다 보면 비슷한 메서드를 반복해서 사용하게 된다. 이번에는 카테고리별로 꼭 알아야 할 메서드들과 그 내부 동작 원리를 정리한다.

1. 문자열 처리 메서드

1.1 Static 메서드 vs 인스턴스 메서드

[동작 원리]
String 클래스는 내부적으로 문자들을 char[] 배열로 저장한다. static 메서드인 valueOf()는 입력값을 새로운 문자열로 변환만 하면 되므로 객체 상태가 필요 없어 static으로 구현된다. 반면 substring()과 같은 인스턴스 메서드는 객체가 가진 문자 배열의 특정 부분을 사용해야 하므로 인스턴스 메서드로 구현된다.

String 메서드 종류와 특징

구분	Static 메서드	인스턴스 메서드
대표 메서드	String.valueOf() String.format()	str.substring() str.charAt()
특징	• 객체 생성 없이 사용 • 타입 변환에 주로 사용 • 메모리 효율적	• 문자열 객체 필요 • 문자열 조작에 사용 • 객체 상태 활용

1.2 자주 사용되는 String 메서드

[동작 원리]

String 클래스의 charAt()과 substring() 같은 인스턴스 메서드들은 내부적으로 문자 배열(char[])을 사용한다. 이 문자 배열은 String 객체가 생성될 때 만들어지며, 메서드들은 이 배열의 인덱스를 활용해 작업을 수행한다. 반면 valueOf() 같은 static 메서드는 새로운 String 객체를 생성하는 순수 변환 작업이기 때문에 기존 객체의 상태가 필요하지 않다.

// 1. Static 메서드
String text = String.valueOf(123);    // "123"
String formatted = String.format("%.2f", 3.14159);  // "3.14"

// 2. 인스턴스 메서드
String str = "Hello World";
int length = str.length();           // 11
char ch = str.charAt(0);             // 'H'
String sub = str.substring(0, 5);    // "Hello"
String[] parts = str.split(" ");     // ["Hello", "World"]
String trimmed = str.trim();         // 앞뒤 공백 제거

1.3 String vs StringBuilder

[동작 원리]

String은 불변 객체라서 문자열이 수정될 때마다 새로운 객체를 생성한다. 반면 StringBuilder는 내부적으로 가변 크기의 char[] 배열을 사용하며, 기본 크기(16)를 초과하면 현재 크기의 2배로 자동으로 늘어난다. append() 호출 시 이 배열의 남은 공간에 문자를 추가하기만 하면 되므로 매우 효율적이다.

// String 연산 (비효율적)
String result = "";
for(int i = 0; i < n; i++) {
    result += i;  // 매번 새로운 객체 생성
}

// StringBuilder 사용 (효율적)
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++) {
    sb.append(i);  // 내부 버퍼 재사용
}
String result = sb.toString();

2. 숫자 처리 메서드

2.1 Integer/Long 클래스의 유용한 메서드들

[동작 원리]
parseInt()는 문자열의 각 문자를 순회하면서 '0'~'9'의 ASCII 값을 이용해 실제 숫자로 변환한다. 이때 자릿수에 따른 가중치(1, 10, 100...)를 곱해가며 최종 값을 계산한다. 모든 과정이 입력 문자열만으로 결과가 결정되므로 static 메서드로 구현되어 있다.

// 문자열 변환
int num1 = Integer.parseInt("123");    // 123
String str = Integer.toString(123);    // "123"

// 진법 변환
int num2 = Integer.parseInt("1010", 2);  // 2진수 → 10진수 (10)
String binary = Integer.toBinaryString(10);  // 10진수 → 2진수 "1010"

// 상수
int max = Integer.MAX_VALUE;  // 2147483647
int min = Integer.MIN_VALUE;  // -2147483648

2.2 Math 클래스의 핵심 메서드들

모든 Math 클래스의 메서드는 static이다. 그 이유는:

1. 수학적 연산은 객체의 상태와 무관
2. 동일 입력에 대해 항상 동일한 결과
3. 단순 계산만 수행하므로 객체 생성 불필요

[동작 원리]
Math.pow(x, n)는 내부적으로 분할 정복 방식을 사용한다. 예를 들어 2⁸을 계산할 때 2⁴ × 2⁴로 나누고, 다시 2⁴는 2² × 2²로 나누는 방식이다. 이런 최적화로 O(log n) 시간 복잡도를 달성한다. 모든 Math 메서드는 순수 계산만 하므로 static으로 구현된다.

// 기본 연산
int max = Math.max(5, 10);      // 10
int min = Math.min(5, 10);      // 5
int abs = Math.abs(-5);         // 5
double sqrt = Math.sqrt(16);    // 4.0
double pow = Math.pow(2, 3);    // 8.0

// 올림/내림/반올림
double ceil = Math.ceil(3.14);   // 4.0
double floor = Math.floor(3.14); // 3.0
long round = Math.round(3.14);   // 3

3. 컬렉션 프레임워크의 핵심 메서드

3.1 List 인터페이스의 주요 메서드

[동작 원리]
ArrayList는 내부적으로 Object[] 배열을 사용한다. add()로 요소를 추가할 때 배열에 여유 공간이 없으면, 현재 크기의 1.5배 크기로 새 배열을 만들어 모든 요소를 복사한다. 중간에 요소를 삽입할 때는 해당 위치 이후의 모든 요소를 한 칸씩 뒤로 밀어야 하므로 O(n)의 시간이 걸린다.

List<Integer> list = new ArrayList<>();
list.add(1);                  // 추가
list.add(0, 2);              // 특정 위치에 추가
int val = list.get(0);       // 조회
list.remove(0);              // 제거
int size = list.size();      // 크기
boolean exists = list.contains(1);  // 포함 여부

3.2 Collections 유틸리티 클래스

[동작 원리]
Collections.sort()는 내부적으로 TimSort 알고리즘을 사용한다. TimSort는 삽입 정렬과 병합 정렬을 결합한 하이브리드 알고리즘으로, 이미 정렬된 부분을 찾아 활용하는 방식이다. 자바 7부터는 이 알고리즘을 도입했는데, 평균/최악 시간복잡도가 O(n log n)이며 실제 데이터에서 매우 효율적으로 동작한다.

Collections 클래스의 모든 메서드가 static인 이유:

1. 범용적인 컬렉션 조작 기능 제공
2. 상태를 유지할 필요가 없음
3. 유틸리티성 메서드들의 모음

List<Integer> numbers = new ArrayList<>();
Collections.sort(numbers);              // 정렬
Collections.reverse(numbers);           // 역순
int max = Collections.max(numbers);     // 최댓값
int min = Collections.min(numbers);     // 최솟값
int pos = Collections.binarySearch(numbers, 5);  // 이진탐색

4. Map과 Set의 핵심 메서드

4.1 HashMap의 효율적인 사용

[동작 원리]
HashMap은 내부적으로 버킷이라는 배열을 사용한다. put() 호출 시 key의 hashCode()를 계산하고 이를 버킷 배열의 인덱스로 변환한다. 서로 다른 key가 같은 인덱스를 가리키는 해시 충돌이 발생하면, 해당 버킷에서 연결 리스트(Java 8부터는 트리)로 충돌을 관리한다. 로드 팩터(기본값 0.75)를 초과하면 버킷 배열을 재할당한다.

Map<String, Integer> map = new HashMap<>();

// 데이터 추가/수정
map.put("A", 1);
map.putIfAbsent("B", 2);  // 없을 때만 추가

// 데이터 조회
int val1 = map.get("A");  // 키가 없으면 null
int val2 = map.getOrDefault("C", 0);  // 키가 없으면 기본값

// 순회
for(String key : map.keySet()) { }
for(int value : map.values()) { }
for(Map.Entry<String, Integer> entry : map.entrySet()) { }

4.2 HashSet의 활용

[동작 원리]
HashSet은 내부적으로 HashMap을 사용하는데, 집합의 원소를 HashMap의 key로 저장하고 value는 더미 객체로 채운다. 따라서 contains() 연산은 HashMap의 containsKey()를 호출하는 것과 같다. 이 때문에 HashSet의 add(), remove(), contains() 연산은 모두 평균적으로 O(1)의 시간 복잡도를 가진다.

Set<Integer> set = new HashSet<>();
set.add(1);      // 추가
set.remove(1);   // 제거
boolean has = set.contains(1);  // 포함 여부

// 중복 제거에 활용
List<Integer> list = Arrays.asList(1, 1, 2, 2, 3);
Set<Integer> unique = new HashSet<>(list);

5. 우선순위 큐

5.1 PriorityQueue의 기본 연산

[동작 원리]
PriorityQueue는 내부적으로 이진 힙으로 구현되어 있다. 배열로 표현된 완전 이진 트리에서 부모 노드는 항상 자식 노드보다 우선순위가 높다(최소 힙의 경우 더 작다). offer() 연산은 요소를 마지막에 추가하고 부모와 비교하며 올라가는 상향 이동(up-heap)을, poll() 연산은 루트를 제거하고 마지막 요소를 루트로 가져와 자식과 비교하며 내려가는 하향 이동(down-heap)을 수행한다. 두 연산 모두 O(log n)의 시간 복잡도를 가진다.

// 1. 최소 힙 (기본값: 오름차순)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 2. 최대 힙 (내림차순)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// 3. 기본 연산 예시
minHeap.offer(3);  // [3]
minHeap.offer(1);  // [1, 3]  → 1이 부모와 비교 후 위로 이동
minHeap.offer(2);  // [1, 3, 2]
System.out.println(minHeap.poll());  // 1 출력, [2, 3] → 루트 제거 후 2가 위에서부터 비교하며 내려감

// 4. 커스텀 클래스 우선순위 설정
class Task implements Comparable<Task> {
    int priority;
    String name;

    Task(int priority, String name) {
        this.priority = priority;
        this.name = name;
    }

    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }
}

// 5. 커스텀 클래스 사용
PriorityQueue<Task> taskQueue = new PriorityQueue<>();
taskQueue.offer(new Task(3, "보통 작업"));
taskQueue.offer(new Task(1, "긴급 작업"));
taskQueue.offer(new Task(2, "중요 작업"));

// 6. 실제 우선순위 큐가 유용한 상황
// - 다익스트라 알고리즘
PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);
pq.offer(new Node(1, 0));  // (노드, 비용)

// - 스케줄링
PriorityQueue<Process> scheduler = new PriorityQueue<>((p1, p2) -> 
    p1.deadline - p2.deadline);  // 데드라인이 가까운 순

// - Top K 문제
PriorityQueue<Integer> topK = new PriorityQueue<>(k);  // k개 유지
for(int num : nums) {
    topK.offer(num);
    if(topK.size() > k) topK.poll();  // k개 초과시 가장 작은 값 제거
}

이 코드는 다음과 같은 PriorityQueue의 핵심 특징을 보여준다:

1. 힙의 종류 설정 (최소/최대)
2. 기본 연산의 동작 과정
3. 커스텀 클래스에서의 우선순위 설정
4. 실제 활용 사례 (다익스트라, 스케줄링, Top K)

각 연산의 시간 복잡도:

• offer(): O(log n) - 상향 이동
• poll(): O(log n) - 하향 이동
• peek(): O(1) - 루트 노드 확인
• size(): O(1) - 크기 확인

이런 특성 때문에 우선순위 큐는 "항상 가장 우선순위가 높은 요소에 빠르게 접근해야 하는" 상황에서 매우 유용하다.

6. Arrays 유틸리티 클래스

6.1 배열 조작의 핵심 메서드

// 배열 정렬
Arrays.sort(arr);               // 오름차순 정렬
Arrays.sort(arr, Collections.reverseOrder());  // 내림차순 정렬

// 배열 검색
int index = Arrays.binarySearch(arr, key);     // 이진 검색

// 배열 복사
int[] copied = Arrays.copyOf(arr, newLength);  // 새 길이로 복사
int[] ranged = Arrays.copyOfRange(arr, 1, 4);  // 범위 복사

// 배열 채우기
Arrays.fill(arr, value);        // 모든 원소를 value로

[동작 원리]
Arrays.sort()는 기본 타입 배열의 경우 DualPivotQuicksort(이중 피벗 퀵소트)를 사용하고, 객체 배열은 TimSort를 사용한다. DualPivotQuicksort는 두 개의 피벗을 사용해 배열을 3개의 파트로 나누어 정렬하므로, 전통적인 퀵소트보다 평균적으로 더 빠르다. copyOf()는 native 메서드인 System.arraycopy()를 내부적으로 호출하여 메모리 블록 단위로 빠른 복사를 수행한다.

7. System 클래스의 유용한 메서드

7.1 시스템 레벨 작업

// 현재 시간 측정
long start = System.currentTimeMillis();  // 밀리초 단위
long nano = System.nanoTime();           // 나노초 단위

// 배열 복사
System.arraycopy(src, srcPos, dest, destPos, length);

// 환경 변수
String path = System.getenv("PATH");

// 시스템 속성
String property = System.getProperty("os.name");

[동작 원리]
System.arraycopy()는 JNI(Java Native Interface)를 통해 C로 구현된 메모리 복사 함수를 호출한다. 이는 Java 레벨에서 루프를 돌며 복사하는 것보다 훨씬 효율적이다. currentTimeMillis()는 운영체제의 시스템 시간을 밀리초 단위로 반환하며, nanoTime()은 JVM이 시작된 이후의 상대적 시간을 나노초 단위로 측정한다. 두 메서드 모두 native로 구현되어 있어 시스템의 하드웨어 타이머에 직접 접근한다.

---

Java 코딩테스트 핵심 자료구조 시간복잡도 정리

이러한 시간 복잡도를 이해하고 있으면 상황에 맞는 적절한 자료구조와 메서드를 선택할 수 있다. 예를 들어, 데이터의 빈번한 삽입/삭제가 필요한 경우 ArrayList보다는 LinkedList를 고려할 수 있고, 정렬된 데이터에서의 검색이라면 일반 검색 대신 binarySearch를 사용하는 것이 효율적이다.

ArrayList

연산	평균 시간복잡도	최악 시간복잡도	공간복잡도	특이사항
조회(get)	O(1)	O(1)	-	인덱스로 직접 접근
끝에 추가(add)	O(1)	O(n)	-	배열 재할당 필요할 수 있음
중간 삽입(add)	O(n)	O(n)	-	요소 시프트 필요
중간 삭제(remove)	O(n)	O(n)	-	요소 시프트 필요
검색(contains)	O(n)	O(n)	-	순차 탐색

LinkedList

연산	평균 시간복잡도	최악 시간복잡도	공간복잡도	특이사항
조회(get)	O(n)	O(n)	-	순차 접근 필요
앞/뒤 추가(add)	O(1)	O(1)	-	head/tail 포인터 활용
중간 삽입(add)	O(n)	O(n)	-	위치 탐색 필요
중간 삭제(remove)	O(n)	O(n)	-	위치 탐색 필요
검색(contains)	O(n)	O(n)	-	순차 탐색

HashMap/HashSet

연산	평균 시간복잡도	최악 시간복잡도	공간복잡도	특이사항
삽입(put/add)	O(1)	O(n)	O(n)	해시 충돌 시 성능 저하
삭제(remove)	O(1)	O(n)	-	해시 충돌 시 성능 저하
검색(get/contains)	O(1)	O(n)	-	해시 충돌 시 성능 저하

PriorityQueue

연산	평균 시간복잡도	최악 시간복잡도	공간복잡도	특이사항
삽입(offer)	O(log n)	O(log n)	O(n)	힙 재구성
삭제(poll)	O(log n)	O(log n)	-	힙 재구성
최솟값/최댓값 조회(peek)	O(1)	O(1)	-	루트 노드 확인

Stack/Queue

연산	평균 시간복잡도	최악 시간복잡도	공간복잡도	특이사항
삽입(push/offer)	O(1)	O(1)	O(n)	-
삭제(pop/poll)	O(1)	O(1)	-	-
조회(peek)	O(1)	O(1)	-	-

정렬 알고리즘

알고리즘	평균 시간복잡도	최악 시간복잡도	공간복잡도	특이사항
Arrays.sort()	O(n log n)	O(n log n)	O(n)	Dual-Pivot Quicksort
Collections.sort()	O(n log n)	O(n log n)	O(n)	TimSort(Merge + Insertion)
QuickSort	O(n log n)	O(n²)	O(log n)	불안정 정렬
MergeSort	O(n log n)	O(n log n)	O(n)	안정 정렬
HeapSort	O(n log n)	O(n log n)	O(1)	불안정 정렬

검색 알고리즘

알고리즘	평균 시간복잡도	최악 시간복잡도	특이사항
선형 검색	O(n)	O(n)	정렬 불필요
이진 검색	O(log n)	O(log n)	정렬 필요

String 연산

연산	시간복잡도	특이사항
length()	O(1)	길이 저장됨
charAt()	O(1)	직접 접근
substring()	O(n)	새 문자열 생성
indexOf()	O(n)	순차 검색
contains()	O(n)	순차 검색
concat()	O(n)	새 문자열 생성

StringBuilder 연산

연산	시간복잡도	특이사항
append()	O(1)	분할상환 분석 기준
insert()	O(n)	요소 시프트 필요
toString()	O(n)	새 문자열 생성

 

이러한 시간복잡도를 이해하면 상황에 맞는 자료구조와 알고리즘을 선택할 수 있다.
예를 들어:

• 빈번한 삽입/삭제가 필요하면 ArrayList 대신 LinkedList 사용
• 정렬된 데이터 검색은 선형 검색 대신 이진 검색 활용
• 문자열 연결이 많으면 String 대신 StringBuilder 사용

📌 주의사항

• HashMap/HashSet의 O(1)은 해시 충돌이 없는 경우의 평균 시간복잡도
• ArrayList의 add()는 용량 확장이 필요한 경우 O(n)이 될 수 있음
• String 메서드들은 불변성(immutable) 때문에 새 객체를 생성하는 비용 발생

마무리

Java의 주요 메서드들은 대부분 잘 설계된 이유가 있다. static으로 선언된 메서드들은 객체 상태와 무관한 순수 함수들이며, 인스턴스 메서드들은 객체의 상태를 활용해야 하는 경우에 사용된다. 이러한 설계 원칙을 이해하면 메서드들을 더 효율적으로 활용할 수 있다.

참고자료

• Java API Documentation: String
• Java API Documentation: Math
• Java Collections Framework Documentation: Collections