[BOJ] 4779 - 칸토어 집합

💬 문제 설명길이 3^`N`의 문자열을 생성해 출력하는 문제다.시작 문자열은 하이픈(-)으로만 구성되며, 각 단계에서 문자열을 3 등분하여 가운데 1/3 구간을 공백으로 바꾸고, 왼쪽·오른쪽 구간에 대해서 동일 과정을 재귀적으로 반복한다.입력은 EOF까지 여러 줄의 `N`이 주어지며, 각 `N`마다 한 줄씩 결과를 출력한다. 📌 주의 사항 👌 문제 풀이핵심은 문자열 구성의 점화식이다. 길이 n=3^k에 대해 S(n) = S(n/3) + " "(n/3개) + S(n/3) 이 성립한다.베이스는 `n == 1`일 때 "-"를 반환한다. 메인에서는 `N`을 읽고 size = 3^`N`을 계산한 뒤, 위 재귀식을 그대로 구현한 함수의 결과를 출력하면 된다.💻 코드import java.io.BufferedR..

💬 문제 설명주어진 `N`개의 좌표값에 대해 좌표 압축을 수행하는 문제로좌표 압축이란 원래 값의 상대적인 크기 순서를 유지하면서 값들을 0부터 시작하는 연속된 정수로 매핑하는 것을 의미한다. 📌 주의 사항단순 구현 시 시간 초과 발생`List.indexOf()` 같은 메서드는 매번 `O(N)` 시간이 걸리므로 전체가 `O(N²)`이 되어 시간 초과 발생따라서 정렬 + 맵(Map) 자료구조를 활용해 `O(N log N)` 안에 해결해야 함입력 크기가 크므로 `Scanner` 대신 `BufferedReader` 또는 커스텀 입력 클래스를 사용하는 것이 좋음 👌 문제 풀이입력받기배열 `nums`에 원본 좌표값을 저장정렬 복사본 만들기`nums`를 복사해서 `copy` 배열을 만든 후 정렬좌표 압축 매핑 ..

💬 문제 설명숫자가 적힌 카드 묶음이 `N`개 있다. 카드 묶음 두 개를 합치면 두 묶음에 들어 있는 카드 수의 합만큼 비교 횟수가 발생한다. 그리고 새로 합쳐진 묶음은 다시 카드 더미에 들어간다.모든 카드를 하나의 묶음으로 합칠 때 필요한 비교 횟수의 최솟값을 구하라. 📌 주의 사항카드 묶음을 합칠 때마다 그 합이 비용으로 더해진다.중간에 합쳐진 묶음도 다시 다음 연산에 참여해야 한다.따라서 항상 가장 작은 두 묶음을 먼저 합치는 전략이 최적이다.큰 묶음을 먼저 합치면 이후 비용이 더 커진다.이 문제는 전형적인 그리디 + 우선순위 큐(최소 힙) 문제다. 👌 문제 풀이모든 카드 묶음을 우선순위 큐에 삽입한다.큐에 원소가 두 개 이상일 동안 반복:가장 작은 카드 묶음 두 개를 꺼낸다.합쳐서 비용에 더..

💬 문제 설명체인이 `N`개 있다. 각 체인은 여러 개의 고리로 이루어져 있고 고리의 개수가 곧 체인의 길이다.체인 두 개를 연결하려면 한 체인의 고리를 하나 잘라서 다른 체인에 이어야 한다. 즉 연결할 때마다 체인 수는 1 줄어들고 동시에 사용한 체인의 길이가 1 줄어든다.목표는 모든 체인을 하나로 연결하는 것이다. 이때 필요한 최소 연결 횟수를 구하라. 📌 주의 사항연결 횟수의 상한은 항상 `N-1`이다.체인 `N`개를 하나로 합치려면 최소한 `N-1`번은 연결해야 한다.하지만 각 체인의 길이가 짧으면 고리가 빨리 소모돼서 중간에 멈출 수 있다.따라서 실제 연결 횟수는 체인의 길이 분포에 따라 줄어들 수도 있다.문제의 핵심은 체인 길이를 고려하여 최소 횟수를 구하는 것이다. 👌 문제 풀이핵심 아..

💬 문제 설명`N`명의 남자와 `N`명의 여자가 있다. 각 사람은 자신의 키(절댓값)와 원하는 조건(부호)으로 표현된다.- 양수 : 자신보다 키가 큰 이성을 원한다.- 음수 : 자신보다 키가 작은 이성을 원한다. 이때 가능한 최대한 많은 커플을 매칭해야 한다. 📌 주의 사항부호의 의미를 헷갈리면 안 된다.+ : 큰 사람 원함 (`~Up`)- : 작은 사람 원함 (`~Down`)매칭 조건은 두 가지밖에 없다.남자 Up ↔ 여자 Down, 조건 boy 남자 Down ↔ 여자 Up, 조건 boy > girl조건이 딱 맞아야 매칭 가능하다.최대 매칭 수를 구하는 것이 목표다. 👌 문제 풀이입력 분류남자/여자를 각각 wantUp / wantDown 두 그룹으로 나눈다.`abs(height)`를 저장해서 실제..

💬 문제 설명당신은 초콜릿을 먹으려 한다. 초콜릿은 항상 한 변의 길이가 2의 거듭제곱인 정사각형 모양이고 가운데로만 쪼개서 두 개로 나눌 수 있다.초콜릿을 최소 몇 번 쪼개야 정확히 `K`칸을 먹을 수 있을지 필요한 최소 초콜릿 크기와 최소 쪼개기 횟수를 출력한다. 📌 주의 사항초콜릿 크기는 무조건 2의 거듭제곱이어야 함쪼갤 때는 반으로만 쪼갤 수 있음쪼갠 조각을 바로 먹을 수도 있고 더 필요하면 계속 쪼개도 됨쪼개는 횟수를 최소화하는 게 목표 👌 문제 풀이초콜릿 크기 정하기입력 `K` 이상인 가장 작은 2의 거듭제곱을 찾는다.→ 이 값이 곧 초콜릿의 최소 크기쪼개기 과정 (그리디)`piece` = 초콜릿 크기, `rem` = `K` (남은 필요한 칸)`while rem > 0`:만약 `piece..