[BOJ 9938] 방 청소(Java, Union-Find, 문제 이해하기)
https://www.acmicpc.net/problem/9938 9938번: 방 청소 처음 6개의 술은 규칙 1에 의해서 1, 3, 5, 7, 9, 2번 서랍에 보관할 수 있다. 7번째 술은 규칙 3을 적용할 수 있다. 1번 서랍에 들어있는 술을 2로, 2번 서랍에 들어있는 술을 3으로, 3번 서랍에 들어있�� www.acmicpc.net ## 접근 서랍에 대한 boolean 배열을 통해서, 서랍의 비어있는 유무를 파악하도록 한다. 서랍이 가득찼을 때, 규칙3과 규칙4에 말하는 다른 서랍의 의미를 파악하는 것이 중요하다. 다른 서랍의 핵심은 기존의 들어있는 술을 옮길 수 있는 서랍이여야 한다. 다른 서랍들에 대한 저장할 수 있는 자료구조가 필요하다. 서랍에 기존의 술이 있을 때, 기존의 술을 옮기기 위..
[BOJ 1717] 여행 가자(Union-Find, Java, 자세한 설명)
## 접근 여행 경로가 가능한지 알아보기 위해서는, 두 점 사이에 경로가 존재하는지 확인해야 한다. 점들을 경유해서 두 점 사이의 경로가 만들어질 수도 있으므로, 가능한 모든 경로를 찾아봐야 한다. 위의 생각은, 점의 갯수가 작을 때는 시간복잡도가 작지만, 점의 개수가 많아지면 시간복잡도로 시간초과가 발생할 수 있다. 따라서, 점들을 경유해서 두 점 사이의 경로가 만들어지면, 두 점의 경로 유무를 저장해줄 수 있는 자료구조가 필요하다. 그렇다면, 두 점 사이의 경로가 있는지 확인하는 방법을 정해야 한다. 만약에, N이 200일 때, 모든 점 사이의 경로를 본다면, 최대 200 ^ 200의 시간 복잡도가 발생한다. 무조건 시간초과이다. 연결이 되는 점들을 모두 같은 집합에 넣는 Union-Find 방식을 ..
[2019 카카오 개발자 겨울 인턴십] 호텔 방 배정(Union-Find, Java, 자세한 설명, 접근법)
## 접근 1. 처음에는 Set 자료구조를 이용해서 문제를 해결하려고 했다. 방번호들을 자료구조에 저장하여, 해당 방번호의 존재 유무를 확인하고 없으면 바로 정답에 넣어주고, 아니면 해당 방번호 + 1부터 가능한 방을 탐색해야 한다. 2. 해당 방번호 + 1에서 시작하여 빈 방을 찾을 때, 순차적으로 접근한다면 k가 10^12이기 때문에 시간복잡도 문제가 발생한다. 3. Set 대신에 Map을 이용해서, 방번호를 Key로서 기억함과 동시에, Value로 다음 방번호를 찾게 하는 역할을 하게 만들고 싶다. 1, 3, 4, 1, 1을 생각해보면, 1 : Map에 미존재, M[1] = 2 3 : Map에 미존재, M[3] = 4 4 : Map에 미존재, M[4] = 5 1 : Map에 존재하므로, M[1]의 ..
[2019 카카오 개발자 겨울 인턴십] 튜플(Java, 깊은 복사, 문자열 처리)
## 접근 1. 주어진 문자열을 {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}의 형태로 변환해야 한다. 이 집합들을 담고 있는 자료구조는 집합의 길이를 기준으로 정렬되어야 한다. * an을 구하기 위해서는, a1 ~ an-1을 알고 있어야 한다. 그래서, 집합의 길이를 기준으로 정렬하면서 a1부터 순차적으로 찾는다. 2. 정렬된 자료구조를 이용해, an을 구한다. {an, an - 1, a1, a2, ...} 식으로 순서가 섞여있더라도, 이미 an-1까지 알고 있으므로 an를 선택할 수 있다 an-1까지를 Set 자료구조를 이용해서 저장한다. ## 유의사항 1. 주어진 문자열들을 집합으로 변환하고, 자료구조에..