java34 [Java] 백준 10986 - 나머지 합 누적합을 M으로 나눈 같은 나머지끼리의 개수를 이용해, 구간합이 M의 배수인 경우의 수를 구하는 문제 1. 문제 유형수학, 누적 합 2. 내가 놓친 포인트처음 떠올린 접근 : 누적합 배열을 만든 뒤, 모든 구간 (i, j)를 이중 반복문으로 직접 확인하려고 했다. 오답 원인: 모든 구간을 직접 검사하는 방식은 O(N^2)이라 N이 최대 10^6인 이 문제에서는 시간초과가 발생한다.3. 핵심 로직 & 해결 방법핵심 조건: 구간합 (S[j] - S[i-1]) 이 M으로 나누어떨어지려면 S[j] % M == S[i-1] % M 이어야 한다. 풀이 아이디어:누적합을 구하면서 매 순간 sum % M 값을 계산한다.현재 나머지와 같은 나머지가 이전에 몇 번 나왔는지 확인하고, 그 개수만큼 count에 더한다.이후 .. 2026. 4. 7. [Java] 백준 11660 - 구간 합 구하기 5 2차원 배열에서 여러 번 주어지는 직사각형 구간의 합을 빠르게 구하는 문제. 1. 문제 유형누적 합, 2차원 누적 합, 구현 2. 내가 놓친 포인트처음 떠올린 접근 : 배열의 값을 입력받으면서 바로 누적합 배열 S를 만들려고 했다. 오답 원인: 처음에는 누적합 공식을 아래처럼 생각했는데 이건 왼쪽 위 대각선 값만 더하는 거라서 2차원 누적합이 아니다. S[i][j] = S[i-1][j-1] + arr[i][j]예를 들어 S[1][4]는 (1,1) ~ (1,4)까지 합이라 10이 나와야 하는데, 위 공식으로 하면 4만 남게 된다.또 구간 합을 구할 때도위쪽과 왼쪽 영역을 각각 뺏다가 두 번 빠진 왼쪽 위 영역을 다시 더해줘야 한다. 3. 핵심 로직 & 해결 방법핵심 조건: 질의 개수 M이 많기 때문에 매번.. 2026. 4. 6. [Java] 백준 11659 - 구간 합 구하기 4 수 N개가 주어졌을 때 i 번째 수에서 j 번째 수까지의 합을 구하는 문제. 1. 문제 유형누적합, 구현 2. 내가 놓친 포인트처음 떠올린 접근 : 누적합 배열을 만들어놓고 매 질의마다 구간합을 구한다.오답 원인: 수열 N개가 한 줄에 주어지는데 입력 처리를 잘못했다.반복문 범위를 잘못 작성해서 마지막 값을 누락했다.구간합 공식을 잘못 사용했다.3. 핵심 로직 & 해결 방법핵심 조건: 빠르게 구간합을 계산하려면 누적합 배열이 필요하다. 풀이 아이디어:누적합 배열 S를 만든다.S[i] = S[i - 1] + 현재 값 형태로 저장한다.구간합은 S[right] - S[left - 1]로 구한다.4. 구현 코드import java.io.*;import java.util.*;public class Main { .. 2026. 4. 6. [Java] 백준 2164 - 카드2 큐를 이용해 맨 앞 카드를 버리고, 그다음 카드를 맨 뒤로 보내는 과정을 반복하여 마지막에 남는 카드를 구하는 문제 1. 문제 유형큐, 덱(Deque), 구현, 시뮬레이션 2. 내가 놓친 포인트처음 떠올린 접근 : 큐를 이용해 문제 조건을 그대로 따라가면서 카드의 이동 과정을 직접 구현하려고 했다. 오답 원인: x 3. 핵심 로직 & 해결 방법핵심 조건: 큐에 맨 앞 카드를 버리고, 그 다음 카드를 맨 뒤로 보내는 과정을 한장 남을 때 까지 반복한다.풀이 아이디어:1부터 N까지의 카드를 Deque에 순서대로 넣는다.맨 앞 카드를 하나 꺼내 버린다.카드가 남아 있다면, 다시 맨 앞 카드를 꺼내 맨 뒤로 보낸다. 이 과정을 반복한다.4. 구현 코드import java.util.*;public class Ma.. 2026. 4. 4. [Java] 백준 2003 - 수들의 합 2 연속된 부분 수열의 합이 M이 되는 경우의 수를 구하는 문제. 1. 문제 유형투 포인터, 슬라이딩 윈도우, 부분합 2. 내가 놓친 포인트처음 떠올린 접근 : 배열을 정렬한 뒤 양끝 포인터를 두고 두 수의 합이 M이 되는 경우를 세려고 했다. 오답 원인: 문제는 연속된 부분 수열의 합을 구하는건데 문제 해석을 잘못했다.정렬하면 안되고, 원래 배열 순서를 유지한 채 구간 합을 관리해야 했다. 3. 핵심 로직 & 해결 방법핵심 조건: 배열의 각 원소가 자연수이기 때문에 구간에 값을 추가하면 합이 커지고, 왼쪽 값을 빼면 합이 작아진다. 풀이 아이디어:start, end 두 포인터를 사용해 현재 연속 구간을 나타낸다.end를 오른쪽으로 이동시키며 현재 구간합(sum)에 값을 더한다.sum이 M보다 커지면 sta.. 2026. 4. 3. [Java] 프로그래머스 - 폰켓몬 중복을 제거해 폰켓몬 종류 수를 구한 뒤, 고를 수 있는 마리 수(N/2)와 비교해서 더 작은 값을 반환하는 문제. 1. 문제 유형해시 2. 내가 놓친 포인트처음 떠올린 접근 : 전체 폰켓몬 수의 절반만 선택 가능하니까 nums.length / 2를 먼저 구하고 HashSet을 통해 중복을 제거해서 둘 중 더 작은 값을 반환하려고 했다. 오답 원인: 중복 제거를 위해 HashSet을 써야 하는 건 맞았는데, HashMap처럼 제네릭을 두 개 넣어버렸다. 3. 핵심 로직 & 해결 방법핵심 조건: N마리 중 정확히 N/2마리만 선택 가능하고 최대한 많은 종류를 골라야한다.풀이 아이디어:nums.length / 2로 선택 가능한 마리 수를 구한다.HashSet에 배열의 값을 전부 넣어 중복을 제거하고 종류 .. 2026. 4. 2. 이전 1 2 3 4 5 6 다음