Problem Solving(126)
-
[BOJ] 18870 - 좌표 압축
💬 문제 설명주어진 `N`개의 좌표값에 대해 좌표 압축을 수행하는 문제로좌표 압축이란 원래 값의 상대적인 크기 순서를 유지하면서 값들을 0부터 시작하는 연속된 정수로 매핑하는 것을 의미한다. 📌 주의 사항단순 구현 시 시간 초과 발생`List.indexOf()` 같은 메서드는 매번 `O(N)` 시간이 걸리므로 전체가 `O(N²)`이 되어 시간 초과 발생따라서 정렬 + 맵(Map) 자료구조를 활용해 `O(N log N)` 안에 해결해야 함입력 크기가 크므로 `Scanner` 대신 `BufferedReader` 또는 커스텀 입력 클래스를 사용하는 것이 좋음 👌 문제 풀이입력받기배열 `nums`에 원본 좌표값을 저장정렬 복사본 만들기`nums`를 복사해서 `copy` 배열을 만든 후 정렬좌표 압축 매핑 ..
2025.09.04 -
[BOJ] 1715 - 카드 정렬하기
💬 문제 설명숫자가 적힌 카드 묶음이 `N`개 있다. 카드 묶음 두 개를 합치면 두 묶음에 들어 있는 카드 수의 합만큼 비교 횟수가 발생한다. 그리고 새로 합쳐진 묶음은 다시 카드 더미에 들어간다.모든 카드를 하나의 묶음으로 합칠 때 필요한 비교 횟수의 최솟값을 구하라. 📌 주의 사항카드 묶음을 합칠 때마다 그 합이 비용으로 더해진다.중간에 합쳐진 묶음도 다시 다음 연산에 참여해야 한다.따라서 항상 가장 작은 두 묶음을 먼저 합치는 전략이 최적이다.큰 묶음을 먼저 합치면 이후 비용이 더 커진다.이 문제는 전형적인 그리디 + 우선순위 큐(최소 힙) 문제다. 👌 문제 풀이모든 카드 묶음을 우선순위 큐에 삽입한다.큐에 원소가 두 개 이상일 동안 반복:가장 작은 카드 묶음 두 개를 꺼낸다.합쳐서 비용에 더..
2025.09.02 -
[BOJ] 2785 - 체인
💬 문제 설명체인이 `N`개 있다. 각 체인은 여러 개의 고리로 이루어져 있고 고리의 개수가 곧 체인의 길이다.체인 두 개를 연결하려면 한 체인의 고리를 하나 잘라서 다른 체인에 이어야 한다. 즉 연결할 때마다 체인 수는 1 줄어들고 동시에 사용한 체인의 길이가 1 줄어든다.목표는 모든 체인을 하나로 연결하는 것이다. 이때 필요한 최소 연결 횟수를 구하라. 📌 주의 사항연결 횟수의 상한은 항상 `N-1`이다.체인 `N`개를 하나로 합치려면 최소한 `N-1`번은 연결해야 한다.하지만 각 체인의 길이가 짧으면 고리가 빨리 소모돼서 중간에 멈출 수 있다.따라서 실제 연결 횟수는 체인의 길이 분포에 따라 줄어들 수도 있다.문제의 핵심은 체인 길이를 고려하여 최소 횟수를 구하는 것이다. 👌 문제 풀이핵심 아..
2025.08.31 -
[BOJ] 2831 - 댄스 파티
💬 문제 설명`N`명의 남자와 `N`명의 여자가 있다. 각 사람은 자신의 키(절댓값)와 원하는 조건(부호)으로 표현된다.- 양수 : 자신보다 키가 큰 이성을 원한다.- 음수 : 자신보다 키가 작은 이성을 원한다. 이때 가능한 최대한 많은 커플을 매칭해야 한다. 📌 주의 사항부호의 의미를 헷갈리면 안 된다.+ : 큰 사람 원함 (`~Up`)- : 작은 사람 원함 (`~Down`)매칭 조건은 두 가지밖에 없다.남자 Up ↔ 여자 Down, 조건 boy 남자 Down ↔ 여자 Up, 조건 boy > girl조건이 딱 맞아야 매칭 가능하다.최대 매칭 수를 구하는 것이 목표다. 👌 문제 풀이입력 분류남자/여자를 각각 wantUp / wantDown 두 그룹으로 나눈다.`abs(height)`를 저장해서 실제..
2025.08.31 -
[BOJ] 2885 - 초콜릿 식사
💬 문제 설명당신은 초콜릿을 먹으려 한다. 초콜릿은 항상 한 변의 길이가 2의 거듭제곱인 정사각형 모양이고 가운데로만 쪼개서 두 개로 나눌 수 있다.초콜릿을 최소 몇 번 쪼개야 정확히 `K`칸을 먹을 수 있을지 필요한 최소 초콜릿 크기와 최소 쪼개기 횟수를 출력한다. 📌 주의 사항초콜릿 크기는 무조건 2의 거듭제곱이어야 함쪼갤 때는 반으로만 쪼갤 수 있음쪼갠 조각을 바로 먹을 수도 있고 더 필요하면 계속 쪼개도 됨쪼개는 횟수를 최소화하는 게 목표 👌 문제 풀이초콜릿 크기 정하기입력 `K` 이상인 가장 작은 2의 거듭제곱을 찾는다.→ 이 값이 곧 초콜릿의 최소 크기쪼개기 과정 (그리디)`piece` = 초콜릿 크기, `rem` = `K` (남은 필요한 칸)`while rem > 0`:만약 `piece..
2025.08.30 -
[BOJ] 17135 – 캐슬 디펜스
💬 문제 설명성 바로 아래에 3명의 궁수를 배치하고 모든 적을 제거하는 게임을 시뮬레이션하는 문제로 규칙은 다음과 같다:1. 매 턴 각 궁수는 가장 가까운 적 하나를 공격한다. - 거리는 맨해튼 거리로 계산 - 가장 가까운 적이 여러 명이면 가장 왼쪽(열이 작은) 적을 우선한다.2. 3명의 궁수가 동시에 공격을 수행한다. (같은 적을 겨냥해도 한 번만 제거됨)3. 공격이 끝나면 적이 한 칸 아래로 이동한다.4. 모든 적이 사라질 때까지 반복하며 제거한 적의 최대 수를 출력해야 한다. 📌 주의 사항타깃 선정: “거리 → 왼쪽 우선” 규칙을 반드시 구현해야 함동시 공격 처리: 각 궁수가 고른 적을 한 번에 제거해야 함적 이동: 라운드마다 맵을 한 칸 아래로 이동시키는 과정이 필요궁수 배치: ..
2025.08.17