[묘공단] 코딩 테스트 합격자 되기 - 집합

코딩 테스트 합격자 되기 자바편

코딩 테스트 합격자 되기 자바편

책 제목 : 코딩 테스트 합격자 되기 자바편

지은이 : 김희성

 

집합

개념

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

예를들어 구성이 {1, 6, 6, 6, 5, 3}이면 이는 집합으로 생각할 때 중복을 제외해 {1, 6, 4, 3}으로 생각해야한다.

일반적으로 집합 자료구조에서 서로 다른 두 집합의 관계를 상호 배타적 집합이라고 한다.

상호 배타적 집합은 두집합 간의 교집합이 없음을 의미한다.

 

상호 배티적 집합 특징

이 특징은 추후 그래프 알고리즘에서 많이 활용하기 때문인데 그래프 알고리즘은 흔히 사이클을 확인 하는 일이 많기 때문이다.

그 작업에서 상호 배타적 집합 개념을 활용하게 된다.

 

그 외에 위 특징이 활용된는 범위

이미지 분할 : 이미지를 서로 다른 부분으로 나누는데 사용 예를 들어 사람과 배경을 겹치지 않게 분할

 

최소 신장 트리 알고리즘 구현 : 간선을 추가할때 마다 사이클을 형성하는지 여부를 체크할 때 사용한다.

 

게임 개발 : 플레이어간의 캐릭터가 충돌시 겹치지 않도록 캐릭터의 동작을 자연스럽게 구현할 수 있다. 

 

클러스터링 작업 : 각 작업이 서로 겹치지 않도록 구성하여 작업간의 의존관계가 없으면 동시에 여러 작업을 진행할 수 있다.

 

집합의 표현 방법

트리 형식으로 집합 표현

트리로 표현 시 대표 원소가 필요한데 대표원소는 집합을 대표하는 역할이라고 볼 수 있다. ( 루트 노드 )

배열로 표현시 배열의 인덱스는 자신을 의미하고 배열의 값은 부모노드를 의미한다.

예시) 4개의 원소가 들어가 배열 [ 0, 0, 1, 1 ]

 0번 인덱스는 값이 0이기 때문에 자신의 인덱스 == 자신의 값은 루트 노드라고 할 수 있다.

1번 인덱스는 값이 0이기 때문에 0번 인덱스가 부모이며

2번, 3번인덱스는 1번 인덱스가 부모라고 할 수 있다.

 

두 집합을 합치는 방법

유니온-파인드 알고리즘 활용

집합 알고리즘에서 합치기와 탐색을 의미한다.

 

파인드 연산

파인드의 경우 현재 노드에서 부터 시작해 루트 노드까지 거슬러 올라가 찾는 것을 의미한다.

예시)  [ 0, 0, 1, 2, 3] 배열이 존재한다면 5번 인덱스에서부터 시작해서 5번의 값은 3이기 때문에 3번이 부모이고 3번 인덱스는 값이 2이기 때문에 2번 인덱스가 부모이고 ... 이런식으로 부모인덱스와 자신의 인덱스가 같은 루트 인덱스를 찾는 것을 파인드 연산이라고 할 수있다.

 

합치기 연산

두 집합간의 상호 상호 배타적 집합을 합쳐서 한 집합의 루트 노드를 상대편 집합의 루트 노드로 바꿔서 하위로 들어가게 하는 것 이다.

예시 ) -1 은 빈 원소를 의미

1번째 집합 : [ 0, -1, -1. -1, -1, -1, 0, 0 ]

2번째 집합 : [ -1, 1, -1, 1, 1 ]

 

그대로 합친 예시

[ 0, 1, -1, -1, 1, 1, -1, 0, 0 ]

 

한쪽의 루트 노드를 다른 한쪽으로 포함 시켜서 하나의 노드로 연결시키는 예시

[ 0, 0, -1, -1, 1, 1, -1, 0, 0 ] 2번째 집합의 루트 노드인 1번의 값을 1번째 집합의 루트 노드의 값으로 변경 시켜서 포함 시켰다.

 

유니온-파인드 연산을 통한 집합 합치기

 

랭크

이런방식으로 합치기는 경우 트리가 깊어질경우 파인드 연산의 비용이 커지기 때문에 랭크라는 개념이 존재한다.

랭크는  노드의 깊이에 따라서 랭크를 정하는데 제일 하위 노드를 0으로 시작하여 루트 노드까지 한 뎁스씩 +1를 하여 랭크를 정한다.

랭크 값이 가장 높은 노드가 루트노드가 된다.

따라서 두 집합간의 랭크를 알고 있기 때문에 랭크가 낮은 집합이 높은쪽의 루트 노드로 바로 붙을 수 있고 같은 경우 둘중에 하나 루트 노드에 랭크 값을 +1 하면 된다.

랭크를 통한 집합 합치기

 

집합장에 문제 풀이

 

영어 끝말잇기

 

프로그래머스 링크

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

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public static void main(String[] args) {
        int[] solution = solution(2, new String[]{"hello", "one", "even", "never", "now", "world", "draw"});

        for (int n : solution) {
            System.out.println(n);
        }
    }

    static int[] solution(int n, String[] words) {
        int[] answer = new int[2];

        HashSet<String> wordSet = new HashSet<>();

        StringBuilder sb = new StringBuilder();
        // null 체크
        if (words.length > 0) {
            // 내부 반복문에서 연산 최소화를 위해서 미리 값 설정
            sb.append(words[0].charAt(0));
            // 단어만큼 반복            
            for (int i = 0; i < words.length; i++) {
                // 현재 단어
                String curWord = words[i];
                // 현재 set 길이 체크
                int prevSize = wordSet.size();
                // 단어 추가
                wordSet.add(curWord);
                // 단어 추가후 길이 체크
                int afterSize = wordSet.size();

                // 중복 여부 확인 , 마지막 연결 단어 확
                if (prevSize == afterSize || curWord.charAt(0) != sb.charAt(sb.length() - 1)) {
                    answer[0] = (i % n) + 1;
                    answer[1] = (i / n) + 1;
                    return answer;
                } else {
                    // 이전 단어 기준 생성
                    sb.delete(0, sb.length());
                    sb.append(curWord);
                }
            }
        }
        return answer;
    }
}