[2020 카카오 인턴십] 보석 쇼핑
programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr ## 접근 직관적으로 생각해야 답이 있다. 처음에는, 모든 범위에서 양쪽 범위를 줄여가며 탐색하려고 했다. 하지만 이 경우에는, N * N의 시간복잡도를 가졌다. 정확성 테스트는 통과했지만, 효율성 테스트는 통과하지 못했다. 따라서, N * logN이나 N의 시간복잡도를 가지도록 코드를 설계해야 했다. 보석의 개수를 중복을 제거할 수 있는 자료 구조를 통해서 구한다. 순차적으로, 보석들을 읽어가면서, 보석의 개수가 완성이 됐..
[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. 주어진 문자열들을 집합으로 변환하고, 자료구조에..