Set
집합 자료구조에 대한 개념과 문제 풀이
1. 개념
집합은 순서와 중복이 없는 원소들을 갖는 자료구조이다.
집합은 배열을 활용한 트리로 구현한다. 각 집합에는 대표 원소가 있어야 한다.
대표 원소는 집합의 원소 중 집합을 대표하는 역할을 한다.
집합의 형태를 트리로 표현하므로 대표 원소는 루트 노드가 된다.
1.1. 유니온-파인드 알고리즘
집합 알고리즘에 주로 쓰이는 연산은 합치기와 탐색이다.
보통 합치기는 유니온, 탐색을 파인드라고 하며 이 둘을 묶어 유니온-파인드 알고리즘이라고 한다.
1.2. 파인드 연산
특정 노드의 루트 노드가 무엇인지 탐색하는 방법이다.
예를 들어 A, B 두 노드가 있는데 이 노드의 루트 노드가 서로 같다면 같은 집합에 속한 것이다.
파인드 연산을 효율적으로 하기 위해서는 집합 형태를 유지하면서도 트리 높이를 줄이면 된다.
1.3. 유니온 연산
유니온 연산은 두 집합을 하나로 합치는 연산이다.
트리의 깊이가 깊어지면 깊어질수록 유니온 연산의 비용이 커진다. 이를 개선하려면 랭크라는 개념이 필요하다.
랭크란 현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이를 말한다.
랭크 기반의 합치기 연산은 다음과 같다.
- 두 노드의 루트 노드를 구한다.
- (1)에서 구한 루트 노드의 랭크를 비교한다.
- 랭크값이 다르면 랭크값이 큰 루트 노드를 기준으로 삼는다. 즉, 랭크가 더 큰 루트 노드를 랭크가 더 작은 루트 노드의 부모 노드로 바꾼다.
- 랭크값이 같으면 루트 노드를 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크에 1을 더한다.
2. (문제) 폰켓몬
2.1. 설명
당신은 폰켓몬을 잡기 위한 오랜 여행 끝에 홍 박사님 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 N마리의 폰켓몬 중 N/2 마리를 가져가도 좋다고 했습니다. 홍 박사님은 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가집니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고 각 폰켓몬의 번호가 [3번, 1번, 2번, 3번] 이면 이는 3번 폰켓몬 2마리, 1번 폰켓몬 1마리, 2번 폰켓몬 1마리가 있음을 나타냅니다. 이때 4마리의 폰켓몬 중 절반인 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.
- 3번, 1번 폰켓몬을 선택
- 3번, 2번 폰켓몬을 선택
- 3번, 3번 폰켓몬을 선택
- 1번, 2번 폰켓몬을 선택
- 1번, 3번 폰켓몬을 선택
- 2번, 3번 폰켓몬을 선택
이때 3번 폰켓몬과 3번 폰켓몬을 선택하는 방법은 한 종류의 폰켓몬만 가지는 것이지만 다른 방법은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 지금 예에서는 가질 수 있는 폰켓몬 종류 수 최댓값이 2가 됩니다. 당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에 최대한 많은 종류의 폰켓몬을 얻을 수 있는 N/2 마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때 N/2 마리의 폰켓몬을 선택하는 방법 중 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아 폰켓몬 종류 번호의 개수를 반환하는 solution() 함수를 완성해주세요.
2.2. 제약 조건
- nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
- nums의 길이(N)는 1 이상 10,000 이하의 자연수이며 항상 짝수입니다.
- 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수입니다.
- 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지일 때에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 반환하면 됩니다.
2.3. 입출력의 예
| nums | reulst |
|---|---|
| [3, 1, 2, 3] | 2 |
| [3, 3, 3, 2, 2, 4] | 3 |
| [3, 3, 3, 2, 2, 2] | 2 |
2.4. 코드
1
2
3
4
5
6
7
8
fun solution(nums: IntArray): Int {
// 최대로 선택할 수 있는 개수
val maxSelect = nums.size / 2
// 중복을 제거한 개수
val uniqueCount = nums.distinct().size
// 더 작은 개수 선택
return minOf(uniqueCount, maxSelect)
}
3. (문제) 영어 끝말잇기
3.1. 설명
1부터 n까지 번호가 붙어 있는 n명의 사람이 영어 끝말잇기를 합니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.
- 1번부터 번호 순서대로 한 사람씩 단어를 말합니다.
- 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
- 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
- 이전에 등장했던 단어는 사용할 수 없습니다.
- 한 글자인 단어는 인정되지 않습니다.
사람의 수 n과 사람들이 순서대로 말한 단어 words가 매개변수로 주어질 때 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락했는지 반환하는 solution() 함수를 완성해주세요.
3.2. 제약 조건
- 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
- words는 끝말잇기에 사용한 단어들이 순서대로 들어 있는 배열이며, 길이는 n 이상 100 이하입니다.
- 단어의 길이는 2 이상 50 이하입니다.
- 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
- 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않아도 됩니다.
- 정답은 [번호, 차례] 형태로 반환해주세요.
- 만약 주어진 단어들로 탈락자가 생기지 않는다면 [0, 0]을 반환하세요.
3.3. 입출력의 예
| n | words | result |
|---|---|---|
| 3 | [“tank”, “kick”, “know”, “wheel”, “land”, “dream”, “mother”, “robot”, “tank”] | [3,3] |
| 5 | [“hello”, “observe”, “effect”, “take”, “either”, “recognize”, “encourage”, “ensure”, “establish”, “hang”, “gather”, “refer”, “reference”, “estimate”, “executive”] | [0,0] |
| 2 | [“hello”, “one”, “even”, “never”, “now”, “world”, “draw”] | [1,3] |
3.4. 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
fun solution(n: Int, words: Array<String>): IntArray {
val result = intArrayOf(0, 0)
// 사용된 단어들을 저장할 HashSet 초기화
val hashSet = HashSet<String>()
// 현재 라운드를 저장할 변수 count (0으로 초기화)
var count = 0
// 이전 단어를 저장할 변수 before (빈 문자열로 초기화)
var before = ""
// words 배열을 순회하며 검사
for (i in words.indices) {
println("before: $before, hashSet: $hashSet, word: ${words[i]}")
// 새로운 라운드의 시작이면 count 증가
if (i % n == 0) count++
// 첫 번째 단어인 경우
if (before.isEmpty()) {
hashSet.add(words[i])
} else {
// 이전 단어의 마지막 문자와 현재 단어의 첫 번째 문자가 일치하지 않을 경우
if (before.last() != words[i].first()) {
return intArrayOf(i % n + 1, count)
}
// 이미 사용된 단어인 경우
if (!hashSet.add(words[i])) {
return intArrayOf(i % n + 1, count)
}
}
// 현재 단어를 before에 저장
before = words[i]
}
return result
}