📙 Algorithm Solving/Java
📙[Algo] 24.03.04 ~ 24.03.05 알고리즘
혜덕hyeduck
2024. 3. 6. 11:18
알고리즘 문제) BOJ 2230. 수 고르기
문제 요약
- N개의 정수로 이루어진 수열 A[1], … A[N]이 존재
- 여기서 두 수를 골랐을 때, 그 차이가 M이상이면서 제일 작은 경우를 구해라
- 같은 수를 고를 수도 있다.
시간 제한
- 2초
입력
- 두 정수 N, M
- N개의 줄에 차례로 A[1], … A[N]이 주어진다.
- 1≤N≤10만
- 0≤M≤20억
- 0≤abs(A[i])≤10억
출력
- 첫째 줄에 M이상이면서 가장 작은 차이 출력
접근법
1 2 3 4 5 6 (M=2)
s
e
- s→ 1, e→1
- abs(s,e) = 0 < M
- e+=1
- s→ 1, e→ 2
- abs(s,e) = 1 < M
- e+=1
- s→ 1, e→ 3
- abs(s,e) = 2 == M
- 찾았으므로 break
⇒ 차이값 < M
- 더 큰 차이값을 찾아야 한다
- s기준 가장 작은 e와의 차이값을 구한 것이므로 e+=1
⇒ 차이값 > M
- 조건을 충족했으몰 정답 갱신
- 더 작은 차이를 찾아야 한다.
- e기준 가장 큰 s와의 차이값을 구한 것이므로 s+=1
⇒ 차이값 == M
- 가장 최소가 될 차이값이므로 갱싱하고 break
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int s = 0, e = 0;
int answer = Integer.MAX_VALUE;
int diff;
while (s <= e && e < N) {
diff = Math.abs(arr[s] - arr[e]);
if (diff >= M) {
answer = Math.min(answer, diff);
if (diff == M) break;
s += 1;
} else {
e += 1;
}
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 1253. 좋다
문제 요약
- N개의 수 중 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다”라고 한다.
- N개의 수 중 좋은 수의 개수는 몇 개?
- 수의 위치가 다르면 값이 같아도 다른 수
시간 제한
- 2초
입력
- 수 N개
- 1≤N≤2000
- i번째 수를 나타내나 Ai N개
- Ai의 절대값은 10억이하
출력
- 좋은 수의 개수는?
접근법
- 완전탐색으로 생각하기
- 3중 for문을 돌면서 수 하나를 선택하고 남은 for문 2개로 다른 수들을 선택해서 합했을 때 해당 수가 되는 경우를 찾는다.
- ⇒ 시간초과(for문은 최대 2개만 사용할 것)
- 최적화 하기
- for문 하나로 목표 수를 설정한다.
- 그리고 투포인터 s, e를 사용해서 다른 두 수를 가리킨다.
- 먼저 수열을 오름차순 정렬
- 1 2 3 4 5 6 7 8 9 10
s e - s→ 1, e→10
- arr[s]+arr[e] = 11 > 6
- e-=1
- s→1, e→9
- arr[s]+arr[e] = 10 > 6
- e-=1
- s→1, e→8
- arr[s]+arr[e] = 9 > 6
- e-=1
- s→1, e→7
- arr[s]+arr[e] = 8 > 6
- e-=1
- s→1, e→6
- arr[s]+arr[e] = 7 > 6
- e-=1
- s→1, e→5
- arr[s]+arr[e] = 6 == 6
- 찾음 ⇒ 카운트 증가하고 break;
- target > arr[s]+arr[e] : s+=1
- target < arr[s]+arr[e] : e-=1
- target == arr[s]+arr[e] : answer++
반례
5
0 0 0 0 1
- 현재 target 수는 s,e가 가리키면 안 된다 ⇒ 이게 제일 애먹었다
- 처음에 카운팅 배열 사용해서 푸니까 범위를 20억해서 메모리 초과 뜸
- 그냥 카운트 변수를 개별적으로 만들고 같은 값을 가리키는 경우가 있다면 한 번 더 돌아서 카운트 변수가 2이상인 경우만 answer를 갱신하게 했다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int target, s, e, sum;
int answer = 0, cnt = 0;
for (int i = 0; i < N; i++) {
target = arr[i];
s = 0;
e = N - 1;
cnt = 0;
while (s < e) {
sum = arr[s] + arr[e];
if (sum > target) {
e--;
} else if (sum < target) {
s++;
} else {
if (target == arr[s] || target == arr[e]) {
cnt++;
if(cnt >= 2){
answer++;
break;
}
if(target == arr[s]) s++;
else if(target == arr[e]) e--;
} else {
answer++;
break;
}
}
}
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 2613. 숫자 구슬
문제 요약
- N개의 숫자 구슬을 M개의 그룹으로 나누었을 때. 각 그룹의 합 중 최댓값이 최소가 되도록 하기
- 그 최댓값과 각 그룹을 구성하는 구슬의 개수 출력
시간 제한
- 1초
입력
- 구슬 개수 N, 그룹의 수 M
- N은 300이하 자연수
- M≤N(자연수)
- 구슬 숫자가 주어짐
- 100이하 자연수
출력
- 각 그룹의 합 중 최댓값
- 각 그룹을 구성하는 구슬의 개수를 왼쪽부터 출력
- 둘 이상이면 하나만
접근법
- 완전 탐색으로 접근하기
- N개의 구슬을 M개의 그룹으로 나누려면 M-1개의 구분선이 필요하다.
- 구분선의 번호를 내 좌측에 있는 구슬의 인덱스로 생각
- 즉 1~N-1중 M-1개를 고르는 경우를 생각한다.
- N은 300까지 가능하므로 N이 최대일 때 나올 수 있는 경우들은 300C0, 300C1, … , 300C299가 된다. ⇒ 경우의 수가 너무 많아지므로 다 보면 안 됨,,
- 백트랙킹 가지치기
- 만약, 그룹합이 현재까지 갱신한 최댓값의 최솟값보다 큰게 나온다면 가지치기 return
코드
- 시간 고려 안하고 완탐(백트) 돌린 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M; // N: 구슬 개수, M : 그룹 개수
static int[] marbles;
static int[] selected;
static int[] prefix;
static int answer = Integer.MAX_VALUE;
static int[] ansIdx;
static void recur(int cur, int start) {
if (cur > 1 && prefix[selected[cur - 1]] - prefix[selected[cur - 2]] >= answer) {
return;
}
if (cur == M) {
int max = 0;
for (int i = 1; i <= M; i++) {
max = Math.max(max, prefix[selected[i]] - prefix[selected[i - 1]]);
}
if (answer > max) {
answer = max;
for (int i = 1; i <= M; i++) {
ansIdx[i - 1] = selected[i] - selected[i - 1];
}
}
return;
}
for (int i = start; i <= N - 1; i++) {
selected[cur] = i;
recur(cur + 1, i + 1);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
marbles = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
marbles[i] = Integer.parseInt(st.nextToken());
}
prefix = new int[N + 1];
for (int i = 1; i <= N; i++) {
prefix[i] = prefix[i - 1] + marbles[i];
}
selected = new int[M + 1];
selected[M] = N;
ansIdx = new int[M];
recur(1, 1);
StringBuilder sb = new StringBuilder();
sb.append(answer + "\\n");
for (int idx : ansIdx) {
sb.append(idx + " ");
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}