1. 백준 알고리즘
1.1. 문제
1.2. 문제설명
이번 문제는
- 출력값을 나온 DFS 결과가 올바른 순서 여부 판단
하는 문제였습니다.
💡 여기서 주의할 점!
- 입력 순서대로 진행되지 않아도 된다는 것입니다. (예제 2, 3)
1.3. 접근법
- Stack을 통해 DFS 로직 구현
st.hasNextTokens()을 통해, 예상 Index 파악contains()을 통해, 존재 여부 판단 + count 함수를 통한 접근 제어
1.4. List + contains()
1.4.1. 코드
import java.util.*;
import java.io.*;
public class Main {
static class Node {
int idx, count;
Node(int idx, int count) {
this.idx = idx;
this.count = count;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
int seq = Integer.parseInt(br.readLine());
List<List<Integer>> list = new ArrayList<>();
for(int i = 0; i < seq + 1; i++) {
list.add(new ArrayList<>());
}
StringTokenizer st;
for(int i = 0; i < seq - 1; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
list.get(a).add(b);
list.get(b).add(a);
}
boolean flag = false;
ArrayDeque<Node> stack = new ArrayDeque<>();
st = new StringTokenizer(br.readLine());
if (Integer.parseInt(st.nextToken()) == 1) {
stack.push(new Node(1, 0));
while(st.hasMoreTokens()) {
Node node = stack.peek();
if(list.get(node.idx).size() <= node.count) {
stack.pop();
continue;
}
int nextIdx = Integer.parseInt(st.nextToken());
if (list.get(node.idx).contains(nextIdx)) {
node.count++;
stack.push(new Node(nextIdx, 1));
continue;
}
flag = true;
break;
}
System.out.println(!flag ? 1 : 0);
} else {
System.out.println(0);
}
}
}1.4.2. 결과
1.4.3. 시간초과 원인
- ArrayList는 배열 기반 순차 탐색으로, 시간 복잡도가
O(N)으로 비효율적 - 즉, 최악으로는
O(N^2)만큼 진행, 정점은 100,000까지 가능 - 100,000 * 100,000 => 무조건 2초 이상 => 시간 초과
1.4.4. 해결방안
- HashSet의
contains()는 시간 복잡도가 평균O(1), 최악일 때만O(N)으로 효율적
1.5. Set + contains()
1.5.1. 코드
import java.util.*;
import java.io.*;
public class Main {
static class Node {
int idx, count;
Node(int idx, int count) {
this.idx = idx;
this.count = count;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
int seq = Integer.parseInt(br.readLine());
List<Set<Integer>> list = new ArrayList<>();
for(int i = 0; i < seq + 1; i++) {
list.add(new HashSet<>());
}
StringTokenizer st;
for(int i = 0; i < seq - 1; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
list.get(a).add(b);
list.get(b).add(a);
}
boolean flag = false;
ArrayDeque<Node> stack = new ArrayDeque<>();
st = new StringTokenizer(br.readLine());
if (Integer.parseInt(st.nextToken()) == 1) {
stack.push(new Node(1, 0));
while(st.hasMoreTokens()) {
Node node = stack.peek();
if(list.get(node.idx).size() <= node.count) {
stack.pop();
continue;
}
int nextIdx = Integer.parseInt(st.nextToken());
if (list.get(node.idx).contains(nextIdx)) {
node.count++;
stack.push(new Node(nextIdx, 1));
continue;
}
flag = true;
break;
}
System.out.println(!flag ? 1 : 0);
} else {
System.out.println(0);
}
}
}1.5.2. 결과
2. ArrayList와 HashSet의 contains()
2.1. 왜 HashSet이 빠름?
- HashSet은 내부적으로 HashMap을 사용.
- 객체의
hashCode()를 기반으로 해시 버킷을 찾아가고, 그 안에서equals()로 최종 비교. - 해시 충돌이 적고
hashCode()구현이 잘 되어 있으면 평균 O(1)의 성능을 보장함.
2.2. List, HashSet 정리 표
| 자료구조 | contains() 시간복잡도 | 내부 구조 |
|---|---|---|
| List | O(N) | 배열 기반 순차 탐색 (ArrayList) |
| HashSet | 평균 O(1) / 최악 O(N) | Hash Table 기반, key의 hashCode와 equals로 탐색 |
3. +a : hashCode()는 어디서 정의되어 있을까?
3.1. HashCode()?
hashCode()Object 클래스에 정의된 메소드로, 객체를 식별하는 정수형 해시값(int)을 반환- 객체 일치 ⭕
- 항상 같은 hashCode를 반환
- 객체 일치 ❌
- 가능하면 서로 다른 값을 반환하는 것이 이상적
3.2. 왜 필요할까?
- 해시 자료구조에서 탐색 성능을 향상시키기 위해!
3.3. Object내의 hashCode 함수
자바의 모든 객체는 Object 클래스를 상속, hashCode함수는 아래와 같이 정의되어 있음
public native int hashCode();3.4. native 키워드?
- Java 코드가 아닌 C/C++로 구현된 메서드임을 나타냄.
- JVM 내부의 구현체와 연결되어 있고, 자바에서는 바디가 없음.
- 대표적인 메서드:
hashCode(),wait(),notify(),clone()등
3.5. Why native로 구현?
- 성능이 중요한 로직 (ex. 해시 연산)
- 운영체제 또는 메모리 관리 등 플랫폼 의존 기능 호출
- JVM의 core 기능과 밀접한 부분이기 때문에 자바 외부에서 구현됨
4. 느낀 점 + 깨달은 점
- contains의 시간복잡도
-> 각 자료구조에 따라서contains()의 시간복잡도가 다르다는 걸 까달음
Backend Developer