쉽게 쉽게

📌 핵심 요약힙 하나로는 안 된다 — PriorityQueue는 루트 한쪽 끝만 정렬을 보장한다. 최소 힙에서 최댓값의 위치는 알 수 없다.풀이 1: TreeMap — 값을 키, 개수를 밸류로 저장한다. firstKey와 lastKey로 양쪽 끝을 각각 O(log n)에 얻는다.풀이 2: 두 개의 힙 — 최소 힙과 최대 힙에 같은 값을 넣고, 한쪽에서 꺼낸 값을 다른 쪽에서 remove로 지운다.차이는 삭제 비용 — PriorityQueue.remove(Object)는 선형 탐색이라 O(n)이다. TreeMap 쪽이 최악의 경우에 안전하다. 목차1 문제프로그래머스 #42628이중우선순위큐operations.length ≤ 1,000,000난이도: Lv.3최댓값과 최솟값을 모두 꺼낼 수 있는 큐를 구현하..

📌 핵심 요약야근 지수는 제곱 합 — 작업량 x를 1시간 처리하면 지수는 2x - 1만큼 줄어든다. 이 값은 x가 클수록 크다.매 시간 가장 큰 일감을 1 깎는다 — 최대 힙(PriorityQueue + reverseOrder)으로 최댓값을 꺼내 1 줄이고 다시 넣는다.제곱은 (long) x * x — Math.pow는 오차 보장이 1 ulp라 캐스팅 과정에서 1이 사라질 수 있다. 목차1 문제프로그래머스 #12927야근 지수n ≤ 1,000,000 · works.length ≤ 20,000난이도: Lv.3퇴근까지 남은 시간이 n시간이고, 각 일감의 작업량이 배열 works에 담겨 있다. 1시간에 아무 일감이나 하나를 골라 작업량을 1 줄일 수 있다. 퇴근 시점에 남아 있는 각 작업량을 제곱해 모두 더..

📌 핵심 요약탐색 시작 횟수 = 정답 — BFS는 시작 노드가 속한 덩어리 전체를 방문하고 멈춘다. 따라서 BFS를 몇 번 시작했는지가 곧 네트워크 개수다.방문 배열은 1차원 — 관리해야 할 상태는 "이 컴퓨터를 이미 세었는가"이므로 주어는 컴퓨터다. 간선이 아니다.인접 행렬을 그대로 사용 — computers가 이미 인접 행렬이므로 별도 자료구조로 옮기지 않았다. n ≤ 200이라 O(n²)로 충분하다. 목차프로그래머스 #43162네트워크n ≤ 200 · 깊이/너비 우선 탐색난이도: [Level 3]컴퓨터 n대가 있고, 어떤 두 컴퓨터가 직접 또는 간접적으로 연결되어 있으면 같은 네트워크로 본다. 연결 정보는 n×n 인접 행렬 computers로 주어진다. computers[i][j]가 1이면 i번과..

📌 핵심 요약상하 이동 — 아래 방향 비용은 'Z' - c가 아니라 'Z' - c + 1이다. 커서는 A에서 출발하므로 A → Z는 1회다.좌우 이동 — length - 1은 최선이 아니다. A는 방문할 필요가 없으므로 되돌아가서 반대편으로 도는 편이 쌀 수 있다.핵심 식 — 왕복하는 구간에만 2가 곱해진다. 종착지가 되는 구간은 1배로 남는다. 목차1 문제 정리조이스틱으로 이름을 만드는 문제다. 처음에는 모든 자리가 A로 채워져 있고, 목표 문자열이 되도록 조작 횟수를 최소화해야 한다.프로그래머스 #42860조이스틱이름 길이 ≤ 20 · 대문자로만 구성난이도: Lv.2조작은 네 가지다. 위/아래는 현재 커서 위치의 알파벳을 바꾸고, 좌/우는 커서를 옮긴다. 커서는 맨 왼쪽에서 시작하며, 좌우 이동은 ..

📌 핵심 요약문제 재진술 — 위치 p에 남는 블록은 p의 약수 중 p 자신을 제외한 최댓값이다.제약 반영 — 블록은 1,000만까지만 존재하므로 최대 약수가 그보다 크면 다음 약수를 찾아야 한다.탐색 범위 — 약수는 i와 p/i가 짝을 이루므로 √p까지만 훑으면 충분하다.조기 반환 — i가 커질수록 p/i는 작아지므로, 상한 이하가 되는 첫 값이 곧 정답이다. 목차Programmers #12923숫자 블록도로 길이 10억 · 블록 번호 ≤ 1,000만 · 구간 ≤ 5,000난이도: Lv.3번호 n인 블록은 n×2, n×3, n×4, ... 위치에 설치된다. 블록은 1번부터 순서대로 깔리며 기존 블록을 덮어쓴다. 구간 [begin, end]에 최종적으로 깔린 블록 번호 배열을 반환한다.풀이 과정위치 p ..

📌 핵심 요약문제 재진술 — 미사일과 요격이라는 표현을 지우면 "구간들을 모두 찌르는 최소 개수의 점"을 구하는 문제다.정렬 기준 — 끝값(e) 오름차순으로 정렬하면 최소 끝값 탐색이 해결된다.경계 조건 — 개구간이므로 s == shot도 커버되지 않은 것으로 취급해야 한다. 비교 연산자는 >=다.상태 설계 — 필요한 정보는 스칼라 두 개뿐이므로 덱이나 리스트가 필요하지 않다.정렬 습관 — 뺄셈 비교 대신 Integer.compare를 쓰면 입력 범위와 무관하게 안전하다. 목차Programmers #181188요격 시스템표적 개수 ≤ 500,000 · 좌표 ≤ 100,000,000난이도: Lv.2표적은 개구간 (s, e)로 주어진다. 미사일은 한 점 x에서 발사되며 s 를 만족하는 표적을 요격한다. 모..

📌 핵심 요약2차원 배열이 필요 없다 — 행마다 퀸이 하나뿐이므로 queenCol[row] = col 형태의 1차원 배열이면 충분하다행 단위로 재귀를 내려간다 — 같은 행 충돌은 구조적으로 불가능해지고, 확인할 조건이 열과 대각선 둘로 줄어든다대각선은 차이로 판정한다 — 행 차이와 열 차이가 같으면 대각선이며, 절댓값 하나로 두 방향을 함께 처리한다되돌리기 코드가 필요 없다 — 다음 후보가 같은 자리를 덮어쓰고, 검사는 이미 확정된 행만 읽는다 목차1 문제 정리Programmers #12952N-Queen4 ≤ n ≤ 12난이도: Lv.2n × n 체스판에 퀸 n개를 서로 공격할 수 없도록 배치하는 경우의 수를 구하는 문제다. 퀸은 가로, 세로, 대각선 방향으로 제한 없이 이동하므로, 두 퀸이 같은 행..

📌 핵심 요약후보키 = 유일성 + 최소성 — 두 조건을 각각 독립된 메서드로 분리하면 코드가 정의를 그대로 옮긴 형태가 된다크기가 작은 조합부터 검사해야 한다 — 최소성 판단은 이미 확정된 키가 있어야 성립하므로 순서가 곧 전제 조건이다DFS와 비트마스크 두 가지로 풀었다 — 컬럼이 8개뿐이라 어느 쪽이든 통과하며, 서로 다른 지점에서 명쾌하다 목차1 문제 정리Programmers #428902019 카카오 개발자 겨울 인턴십 / 후보키1 ≤ 행 ≤ 20 · 1 ≤ 열 ≤ 8난이도: Lv.2릴레이션(표)이 문자열 2차원 배열로 주어진다. 이때 후보키가 될 수 있는 속성(컬럼) 조합의 개수를 구하는 문제다. 후보키는 아래 두 조건을 모두 만족해야 한다.후보키의 두 조건유일성 — 그 컬럼들의 값으로 모든 ..

📌 핵심 요약열마다 BFS를 돌리면 안 된다 — 격자를 딱 한 번만 순회하며 석유 덩어리를 식별하는 것이 핵심이다덩어리가 걸친 열을 Set으로 수집 — 같은 덩어리가 한 열에 여러 칸 걸쳐도 크기는 한 번만 더해야 한다결산을 BFS 안에서 끝낸다 — 덩어리를 찾은 자리에서 걸친 열에 크기를 누적하면 중간 자료구조가 필요 없다시간 복잡도 O(n×m) — 각 칸은 정확히 한 번만 큐에 들어간다 목차1 문제 정리Programmers #250136[PCCP 기출문제] 2번 / 석유 시추1 ≤ land 행 ≤ 500 · 1 ≤ land 열 ≤ 500난이도: Lv.2n × m 격자로 표현된 땅이 주어진다. 값이 1인 칸에는 석유가 있고, 상하좌우로 인접한 1들은 하나의 석유 덩어리를 이룬다. 시추관을 세로로 하나..

📌 핵심 요약완전탐색(DFS) — 이모티콘 하나당 10/20/30/40% 네 가지 할인율을 모두 대입한다. 최대 47 = 16,384가지판단 기준 — 구독자 수가 최우선, 같으면 판매액이 큰 쪽을 선택한다겪은 오류 — new int[]{n}과 new int[n]을 혼동해 길이 1짜리 배열을 넘겼다구조 문제 — 정답 후보를 static 필드에 두면 테스트케이스 간 상태가 남는다 목차1 문제 정리Programmers #150368이모티콘 할인행사users ≤ 100 · emoticons ≤ 7난이도: Lv.2각 이모티콘에 10, 20, 30, 40% 중 하나의 할인율을 정한다. 사용자는 자신의 기준 할인율 이상으로 할인되는 이모티콘을 전부 구매하고, 그 총액이 자신의 기준 금액 이상이 되면 구매를 취소하고..