Set

개념

집합은 순서와 중복이 없는 원소들을 갖는 자료구조이다.

집합은 배열을 활용한 트리로 구현한다. 각 집합에는 대표 원소가 있어야 한다.

대표 원소는 집합의 원소 중 집합을 대표하는 역할을 한다.

집합의 형태를 트리로 표현하므로 대표 원소는 루트 노드가 된다.

유니온-파인드 알고리즘

집합 알고리즘에 주로 쓰이는 연산은 합치기와 탐색이다.

보통 합치기는 유니온, 탐색을 파인드라고 하며 이 둘을 묶어 유니온-파인드 알고리즘이라고 한다.

파인드 연산

특정 노드의 루트 노드가 무엇인지 탐색하는 방법이다.

예를 들어 A, B 두 노드가 있는데 이 노드의 루트 노드가 서로 같다면 같은 집합에 속한 것이다.

파인드 연산을 효율적으로 하기 위해서는 집합 형태를 유지하면서도 트리 높이를 줄이면 된다.

유니온 연산

유니온 연산은 두 집합을 하나로 합치는 연산이다.

트리의 깊이가 깊어지면 깊어질수록 유니온 연산의 비용이 커진다. 이를 개선하려면 랭크라는 개념이 필요하다.

랭크란 현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이를 말한다.

랭크 기반의 합치기 연산은 다음과 같다.

1. 두 노드의 루트 노드를 구한다.

2. (1)에서 구한 루트 노드의 랭크를 비교한다.

   1. 랭크값이 다르면 랭크값이 큰 루트 노드를 기준으로 삼는다. 즉, 랭크가 더 큰 루트 노드를 랭크가 더 작은 루트 노드의 부모 노드로 바꾼다.

   2. 랭크값이 같으면 루트 노드를 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크에 1을 더한다.

문제 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() 함수를 완성해주세요.

제약 조건

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.

• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며 항상 짝수입니다.

• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수입니다.

• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지일 때에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 반환하면 됩니다.

입출력의 예

nums	reulst
[3, 1, 2, 3]	2
[3, 3, 3, 2, 2, 4]	3
[3, 3, 3, 2, 2, 2]	2

코드

fun solution(nums: IntArray): Int {
    // 최대로 선택할 수 있는 개수
    val maxSelect = nums.size / 2
    // 중복을 제거한 개수
    val uniqueCount = nums.distinct().size
    // 더 작은 개수 선택
    return minOf(uniqueCount, maxSelect)
}

문제 2. 영어 끝말잇기

설명

1부터 n까지 번호가 붙어 있는 n명의 사람이 영어 끝말잇기를 합니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1. 1번부터 번호 순서대로 한 사람씩 단어를 말합니다.

2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.

3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.

4. 이전에 등장했던 단어는 사용할 수 없습니다.

5. 한 글자인 단어는 인정되지 않습니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words가 매개변수로 주어질 때 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락했는지 반환하는 solution() 함수를 완성해주세요.

제약 조건

• 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.

• words는 끝말잇기에 사용한 단어들이 순서대로 들어 있는 배열이며, 길이는 n 이상 100 이하입니다.

• 단어의 길이는 2 이상 50 이하입니다.

• 모든 단어는 알파벳 소문자로만 이루어져 있습니다.

• 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않아도 됩니다.

• 정답은 [번호, 차례] 형태로 반환해주세요.

• 만약 주어진 단어들로 탈락자가 생기지 않는다면 [0, 0]을 반환하세요.

입출력의 예

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]

코드

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
    }

참고

https://school.programmers.co.kr/learn/courses/30/lessons/1845school.programmers.co.kr

폰켓몬

https://school.programmers.co.kr/learn/courses/30/lessons/12981school.programmers.co.kr

영어 끝말잇기