📌 풀이 1 (시간 초과) 에라토스테네스의 채 방법 사용 에라토스테네스의 채란? n의 약수의 합을 구할 때 나누는 수를 1부터 N까지 모두 검사한다면? // answer에 약수의 개수 저장 var answer = 0 for (i in 0 until N) { if (N % i == 0) answer += i } 위 식은 시간 복잡도는 O(N)이다. 이때 에라토스테네스의 채라는 방법을 이용하면 시간 복잡도가 획기적으로 줄어드는데 합성수는 그 수의 제곱근보다 작거나 같은 약수를 갖는다 즉 N까지 검사할 것을 루트 N까지만 검사하면 된다는 것 -> 시간 복잡도를 O(√n) 로 만들어준다. 예를 들어 N=10000이라면 10000번 검사할 것을 100번만 검사하면 된다는 것 코드 import kotlin.math..

전형적인 BFS 문제이다. 최대한 함수로 역할을 나누어 분리해 풀이해보려고 노력했다. solution -> check -> bfs 함수 순으로 내려가 보도록 하자. 📌 soloution 함수 fun solution(places: Array): IntArray { var answer = mutableListOf() for (i in (0..4)) { if (check(places[i])) answer.add(1) else answer.add(0) } return answer.toIntArray() } 문제에서 palaces가 2차원 String 배열로 주어지므로 한 줄씩 내려가면서 check 함수 안에 Array을 넣어 만약 확인이 된다면 즉 거리두기를 위반하는 사람이 없다면 answer 리스트에 1을 넣..

다른 사람의 풀이에 정말 배울 가치가 있는 코드가 있어 하나씩 뜯어보며 공부해보려고 한다. 풀이 genres = ["classic", "pop", "classic", "classic", "pop"] playes = [500, 600, 150, 800, 2500] fun solution(genres: Array, plays: IntArray): IntArray { return genres.indices.groupBy { genres[it] } .toList() .sortedByDescending { pair -> pair.second.sumOf { index -> plays[index] } } .map { pair -> pair.second.sortedByDescending { index -> plays[..

📌 풀이 이번 문제는 투 포인터를 생각하며 문제를 풀었다. 예시 2개를 보며 문제를 파악해보자 예시 1) people = [40, 40, 40, 50, 50, 60, 70, 80], limit = 100 이 예시는 보트에 (40, 60), (40, 50), (40, 50), (70), (80) 이렇게 총 5개의 보트가 필요하다. 예시는 애초에 정렬이 되어 있으나 문제의 테스트 케이스는 정렬이 되어 있지 않을 수 있으므로 우선 people을 정렬해주어야 한다. 우선 가장 첫 번째 원소와 가장 마지막 원소의 합을 limit와 비교한다. 40과 80을 비교해 100보다 같거나 작지 않다면 마지막 원소를 pop 해주면서 answer += 1을 해준다. 왜냐면 people은 정렬이 되어있기 때문에 가장 마지막 원..

📌 Heap Heap은 데이터를 정렬된 상태로 저장하기 위해서 사용하는 자료구조이다. 파이썬의 heapq 모듈은 이진트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공한다. min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은 값은 언제나 인덱스 0, 즉, 이진트리의 루트에 위치한다. 내부적으로 min heap 내의 모든 원소(k)는 항상 자식 원소들(2k+1, 2k+2) 보다 크기가 작거나 같도록 원소가 추가되고 삭제된다. 이 문제에서 힙의 최댓값을 제거하는데 약간의 요령이 필요한데 바로 nlargest라는 함수이다. heapq 모듈에 이 용도에 적합한 nlargest()와 nsmallest() 함수가 있다. heapq.nl..