📙 Algorithm Solving/Java
📙[Algo] 24.01.30 알고리즘
혜덕hyeduck
2024. 1. 31. 10:20
알고리즘 문제) BOJ 24956. 나는 정말 휘파람을 못 불어
24956번: 나는 정말 휘파람을 못 불어
'유사 휘파람 문자열'인 부분 수열의 개수를 $1\,000\,000\,007(= 10^9+7)$로 나눈 나머지를 출력한다.
www.acmicpc.net
문제 요약
- 대문자로 구성된 문자열 S에서 휘파람과 비슷한 소리(유사 휘파람 문자열) 개수를 구해야 함
- WHEE : 유사 휘파람 문자열
- WHEE + E붙인것도 유사 휘파람 문자열
- S에서 유사 휘파람 문자열인 부분수열 개수 구하기
- 꼭 문자들이 연속하지 않아도 됨
시간 제한
- 1초
입력
- 문자열 S의 길이 N
- 1≤N≤20만
- 문자열 S
출력
- 유사 휘파람 문자열인 부분 수열 개수를 1000000007로 나눈 나머지 출력
접근법
유사 휘파람 문자열은 최소 WHEE로 구성 될 것
- 완전 탐색으로 접근하기
WAHEWHEE WHEWHEE W → H → E → E → E….
먼저 문자열 앞에서부터 W가 나올 때까지 탐색 진행
W를 찾으면 그 다음 H, E, E순서대로 찾을 때까지 탐색 진행
WHEE하나 완성 되면 카운트 증가, 그다음 끝까지 E만 등장할 때까지 탐색하면 카운트 하나씩 계속 증가
최소 2중 for문 필요 (스타트 지점 찾을 for 문 * 이후 유사 휘파람 문자열 완성할 for문 ) ⇒ 그러나 문자열 길이가 20만이기 때문에 20만*20만 이면 시간 초과 발생 ⇒ 2중 for문 안 됨! - 최적화하기
유사 휘파람 문자열은 W 1개, H 1개, E 2개이상으로 구성되어야 한다.
E W H E H E H E W W W H E H E
W: 0 1 1 1 1 1 1 1 2 3 4 4 4 4 4
H : 0 0 1 1 2 2 3 3 3 3 3 4 4 5 5
E : 1 1 1 2 2 3 3 4 4 4 4 4 5 5 6
- W → H를 먼저 찾아야 한다.
- H는 앞의 W의 개수에 영향을 받는다.
- 즉, 우선 W, E의 등장 개수 누적합 배열을 만든다.
- for문을 이용해 H 등장여부를 체크한다.
- H가 등장하면 해당 지점까지 W등장 횟수 * 해당 지점 이후 E의 부분 집합 개수 중 2개 이상의 원소로 이루어진 부분 집합 개수만큼 더해준다.
- ⇒ 1차원 배열로만 처리하기
- ⇒ 부분집합 개수 구해버리면 최악의경우 2의 20만승을 계산하니까 무한대로 커질 수 있움,,,
- W → H를 먼저 찾아야 한다.
코드
import java.io.*;
import java.util.Arrays;
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));
int N = Integer.parseInt(br.readLine());
final int MOD = 1000000007;
String S = br.readLine();
int[] accW = new int[N + 1];
int[] accE = new int[N + 1];
long[] subset = new long[N + 1];
for (int i = 1; i <= N; i++) {
accW[i] += accW[i - 1];
accE[i] += accE[i - 1];
if(S.charAt(i-1) == 'W') accW[i] = (accW[i - 1] + 1) % MOD;
else if(S.charAt(i-1) == 'E'){
accE[i] = (accE[i - 1] + 1) % MOD;
subset[accE[i]] = subset[accE[i - 1]] * 2 % MOD + accE[i - 1] % MOD;
}
}
long answer = 0;
for (int i = 1; i <= N; i++) {
if (S.charAt(i - 1) == 'H') {
answer += accW[i] * (subset[(int)accE[N] - (int)accE[i]]);
}
}
bw.write(String.valueOf(answer % MOD));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 17074. 정렬
17074번: 정렬
정렬이란, 배열의 모든 원소가 비내림차순이 되도록 순서를 바꾸는 것을 말한다. 예를 들어 배열 [2, 1, 2, 3, 1]을 정렬하면 [1, 1, 2, 2, 3]이 된다. 남규는 정수 N개로 이루어진 배열 하나를 갖고 있다
www.acmicpc.net
문제 요약
- 배열의 모든 원소가 오름차 되도록 정렬
- 수를 하나 버린 뒤 배열이 정렬되게 하려고 함
- 이때 가능한 경우의 수?
시간 제한
- 1초
입력
- N
- 2≤N≤10만
- 배열 원소 N개
- -10억 ~ 10억
출력
- 하나를 버려 정렬된 배열 만들 수 있는 경우의 수
접근법
- 완전 탐색으로 접근하기
수 하나씩 버리면서 오름차순인지 체크한다.
하지만 이렇게 되면 버릴 수 선택하는 for문 10만 * 버렸을 때 정렬 됐는 지 체크하는 for문 10만 ⇒ 100억 연산으로 시간초과 - 최적화하기
1234334- 4 양 옆 3 == 3 이므로 4제거 가능
- 3 양 옆 4 > 3 이므로 3 제거 X
- 6 양 옆 3<4이므로 6 제거 가능
- 4 양 옆 6 > 5 이므로 4 제거 X
- 6 양 옆 3<4이므로 6 제거 가능
- 4 양 옆 6 == 6 이므로 4 제거 가능
- 6 양 옆 3<4이므로 6 제거 가능
- 4 양 옆 6<7 이므로 4 제거 가능
- 7 양 옆 3>2 이므로 7 제거 X
- 2 양 옆 7>3 이므로 2 제거 X
- 2 양 옆 2>1 이므로 2 제거 X
- 1 양 옆 2<3 이므로 1 제거 가능
- 3 양 옆 2==2 이므로 3 제거 가능
- 2 양 옆 3==3 이므로 2 제거 가능
- 3 양 옆 2==2 이므로 3 제거 가능
- 2 양 옆 3<4 이므로 2 제거 가능
- 5 양 옆 3>2 이므로 3 제거 X
- 2 양 옆 5>3 이므로 2 제거 X
- diff값 양수가 두 개 존재하므로 불가능
- 3 양 옆 2>1 이므로 3 제거 X
- 1 양 옆 3==3 이므로 1 제거 가능
- 3 양 옆 2 == 2이므로 3 제거 가능
- 2는 마지막 값이므로 제거 가능
- 3 양 옆 2 > 1 이므로 3 제거 X
- 1은 마지막 값이므로 제거 가능
- diff가 양수인 게 없으므로 N만큼 가능
- 3은 가장 첫 번째 값이므로 제거 가능
- 1은 양 옆 3>1이므로 제거 X
- 2는 가장 첫 번째 값이므로 제거 가능
- 1은 양 옆 2==2 이므로 제거 가능
- diff가 양수인 게 없으므로 N만큼 가능
코드
import java.io.*;
import java.util.StringTokenizer;
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));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[N];
int[] diff = new int[N - 1];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
if (i != 0) diff[i - 1] = arr[i - 1] - arr[i];
}
// 1 2 2 3 2
int idx = 0, cnt = 0;
for (int i = 0; i < N - 1; i++) {
if (diff[i] > 0) {
cnt++;
idx = i;
}
}
int answer = 0;
if (cnt == 1) {
if (idx == 0 || idx == N - 2) answer++; // 양 끝 값은 무조건 제거할 수 있으니까
if (0 <= idx - 1 && idx + 1 < N && arr[idx - 1] <= arr[idx + 1]) answer++;
if (idx + 2 < N && arr[idx] <= arr[idx + 2]) answer++;
if (N == 2) answer++;
} else if (cnt == 0) {
answer = N;
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 14846. 직사각형과 쿼리
14846번: 직사각형과 쿼리
첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며
www.acmicpc.net
문제 요약
- N*N행렬이 주어지고 각 쿼리를 수행
- 쿼리마다 x1 y1 x2 y2 좌표가 주어지
- 왼쪽 윗칸 (x1,y1) 오른쪽 아래칸(x2,y2)인 부분 행렬에 포함된 서로 다른 정수 개수 출력
시간 제한
- 2초
입력
- N (1≤N≤300)
- N개의 줄에 행렬 정보
- 1~10 자연수
- Q (1≤Q≤10만)
- Q개의 줄에 쿼리 정보 x1 y1 x2 y2
- x1≤x2, y1≤y2
- Q개의 줄에 쿼리 정보 x1 y1 x2 y2
출력
- 각 쿼리마다 정답 출력
접근법
- 숫자들 개수들을 기록할 3차원 배열 선언 cnt[300][300][10]
- 숫자개수들을 누적해서 기록한다
- 3차원 누적합
1 2 3 3 2 1 5 6 3
- (1,1)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 |
- (1,1) ~ (1,2)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 |
- (1,1) ~ (1,3)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 | 1 |
- (1,1) ~ (2,1)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 |
- (1,1) ~ (2,2)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 1 |
- (1,1) ~ (2,3)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 2 | 2 | 2 |
=> 2차원 누적합처럼 등장한 숫자 개수를 누적해서 기록한다.(for문 1~10)
cnt[i][j][num] = cnt[i-1][j][num] + cnt[i][j-1][num] - cnt[i-1][j-1][num];
cnt[i][j][arr[i][j]]++;
출력할 때도 마찬가지로 구간합 배열에서 부분배열 합계 출력하는 공식 적용,,
(1,2) ~ (2,3)
for num 1~10까지
cnt[2][3][num] - cnt[2][1][num] - cnt[0][3][num] + cnt[0][0][num]
코드
import java.io.*;
import java.util.StringTokenizer;
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 + 1][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
// 개수 구간합 구하기
int[][][] cnt = new int[N + 1][N + 1][11];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
for (int k = 1; k <= 10; k++) {
cnt[i][j][k] = cnt[i-1][j][k] + cnt[i][j-1][k] - cnt[i-1][j-1][k];
}
cnt[i][j][arr[i][j]]++;
}
}
int Q = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
int x1, y1, x2, y2, ans;
while (Q-- > 0) {
st = new StringTokenizer(br.readLine());
x1 = Integer.parseInt(st.nextToken());
y1 = Integer.parseInt(st.nextToken());
x2 = Integer.parseInt(st.nextToken());
y2 = Integer.parseInt(st.nextToken());
ans = 0;
for (int i = 1; i <= 10; i++) {
if (cnt[x2][y2][i] > 0) {
if (cnt[x2][y2][i] - cnt[x1 - 1][y2][i] - cnt[x2][y1 - 1][i] + cnt[x1 - 1][y1 - 1][i] > 0) {
ans++;
}
}
}
sb.append(ans+"\n");
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}