서론
매번 후순위로 밀리던 슬라이딩 윈도우 문제를 풀어보려고 한다.
2559 수열 - 실버3
https://www.acmicpc.net/problem/2559
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] arr = new int[n];
int maxSum = -10_000_001;
int sum= 0;
int tmp = k - 1;
for (int i =0; i<n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
sum += arr[i];
if (i < tmp) {
continue;
}
if (i >= k) {
sum -= arr[i - k];
}
if (sum > maxSum) {
maxSum = sum;
}
}
System.out.println(maxSum);
}
그냥 앞뒤 숫자를 큐스택처럼 빼는 문제였다. 어렵지 않다
21921 블로그 - 실버3
https://www.acmicpc.net/problem/21921
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] visitorCnt = new int[n];
int tmp = x - 1;
int cnt = 0;
int maxSum = 0;
int currentSum =0;
for (int i =0; i<n; i++) {
visitorCnt[i] = Integer.parseInt(st.nextToken());
currentSum += visitorCnt[i];
if (i < tmp)
continue;
if (i > tmp) {
currentSum -= visitorCnt[i-x];
}
//갱신작업
if (currentSum == maxSum) {
cnt ++;
}
if (currentSum > maxSum) {
maxSum = currentSum;
cnt = 1;
}
}
//출력
if (maxSum == 0) {
System.out.println("SAD");
} else {
System.out.println(maxSum + "\n" + cnt);
}
}
윗 문제와 굉장히 유사하다. 어렵지 않다
12891 DNA 비밀번호 - 실버2
https://www.acmicpc.net/problem/12891
class Main {
static int[] currentAlpha;
static int[] requiredAlpha;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
requiredAlpha = new int[4];
currentAlpha = new int[4];
int s = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
String input = br.readLine();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < 4; i++) {
requiredAlpha[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < p; i++) {
increaseCurrentAlpha(input.charAt(i));
}
int result = 0;
if (check()) {
result++;
}
for (int i = 1; i < input.length() + 1 - p; i++) {
decreaseCurrentAlpha(input.charAt(i - 1));
increaseCurrentAlpha(input.charAt(i + p - 1));
if (check()) {
result++;
}
}
System.out.println(result);
}
private static void decreaseCurrentAlpha(char c) {
if (c == 'A') {
currentAlpha[0]--;
} else if (c == 'C') {
currentAlpha[1]--;
} else if (c == 'G') {
currentAlpha[2]--;
} else if (c == 'T') {
currentAlpha[3]--;
}
}
private static boolean check() {
boolean pass;
pass = true;
for (int j = 0; j < 4; j++) {
if (requiredAlpha[j] > currentAlpha[j]) {
pass = false;
break;
}
}
return pass;
}
private static void increaseCurrentAlpha(char c) {
if (c == 'A') {
currentAlpha[0]++;
} else if (c == 'C') {
currentAlpha[1]++;
} else if (c == 'G') {
currentAlpha[2]++;
} else if (c == 'T') {
currentAlpha[3]++;
}
}
}
" 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다."라는 조건때문에 쉬워진 문제인 것 같다. 알파벳이 26개밖에 안되기 때문에 배열로 최적화한 풀이들이 많아서 재미있었다.
2531 회전 초밥 - 실버1
https://www.acmicpc.net/problem/2531
class Main {
static int max;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int plateCnt = Integer.parseInt(st.nextToken());
int typeCnt = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int coupon = Integer.parseInt(st.nextToken());
int[] plate = new int[plateCnt+k-1]; //k-1개만큼 배열 늘리기
int[] current = new int[typeCnt+1]; //접시타입별 개수 저장용
int currentTypeCnt = 0;
max = 0;
for (int p =0; p<plate.length; p++) {
//입력받기
if (p < plateCnt) {
plate[p] = Integer.parseInt(br.readLine());
}
int type = plate[p];
//현재값 갱신
current[type] ++;
if (current[type] == 1) {
currentTypeCnt++;
}
//사이클 갱신용
if (p < k-1) {
plate[plateCnt + p] = type;
continue;
}
//앞에꺼 빼주기
if (p >= k) {
int prevType = plate[p - k];
current[prevType] --;
if (current[prevType] == 0) {
currentTypeCnt--;
}
}
//max값 갱신
updateMax(currentTypeCnt, current, coupon);
}
System.out.println(max);
}
private static void updateMax(int currentTypeCnt, int[] current, int coupon) {
int tmpCurrentTypeCnt = currentTypeCnt;
//쿠폰고려해서 typecnt 갱신
if (current[coupon] ==0) {
tmpCurrentTypeCnt++;
}
if (tmpCurrentTypeCnt > max) {
max = tmpCurrentTypeCnt;
}
}
}
사이클만 고려하면 어렵지 않은 문제다.
슬라이딩윈도우 초기값을 채우는 과정과 사이클을 위한 배열 추가값을 더하는 과정을 한 번에 진행하느라 코드가 깔끔하지 못한 것 같다. 나중에 나도 못알아볼 것 같아서 주석이라도 열심히 달았다
15565 귀여운 라이언 - 실버1
https://www.acmicpc.net/problem/15565
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
//라이언 인형 위치 저장용
int[] lion = new int[n]; //최대 라이언인형 개수는 n개 -> n개로 넉넉하게 잡음
int lionIdx= 0; //저장된 라이언 인형 개수
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
int doll = Integer.parseInt(st.nextToken());
if (doll == 1) {
lion[lionIdx++] = i;
}
}
//전체 라이언인형 개수가 k보다 작으면 -1 출력 후 종료
if (lionIdx < k) {
System.out.println(-1);
return;
}
//lion인형 k개를 유지하면서 범위크기 비교
int min= Integer.MAX_VALUE;
int end = lionIdx - k + 1;
for (int i = 0; i< end; i++) {
int nextIdx = i + k - 1;
int tmp = lion[nextIdx] - lion[i] + 1;
if (tmp < min) {
min = tmp;
}
}
System.out.println(min);
}
원래는 전체 배열에 대해서 start와 end를 조절하면서 라이언 인형 개수를 맞추고자 했는데, 조금만 생각을 틀면 훨씬 빨리 구할 수 있는 방법이 있었다. 내가 생각한 풀이는 아니고 인터넷 풀이를 참고해서 풀었다. (참고한 블로그: https://chan-it-note.tistory.com/100)
- 라이언 인형 위치만 배열에 저장한다
- 라이언 인형 배열에서 투포인터를 사용하여 라이언인형 K개일 때 최소 범위사이즈를 구한다
1593 문자 해독 - 골드5
https://www.acmicpc.net/problem/1593
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int wordLength = Integer.parseInt(st.nextToken());
int totalLength = Integer.parseInt(st.nextToken());
String word = br.readLine();
String totalWord = br.readLine();
int[] wordCnt = new int[58];
for (int i = 0; i < wordLength; i++) {
wordCnt[word.charAt(i) - 'A']++;
}
//초기값 넣기
int[] currentCnt = new int[58];
for (int i = 0; i < wordLength; i++) {
currentCnt[totalWord.charAt(i) - 'A']++;
}
int result = 0;
if (Arrays.equals(currentCnt, wordCnt)) {
result++;
}
//슬라이딩 윈도우 수행
int endWindow = totalLength - wordLength + 1;
for (int i = 1; i < endWindow; i++) {
currentCnt[totalWord.charAt(i-1) - 'A']--;
currentCnt[totalWord.charAt(i+wordLength - 1) - 'A']++;
if (Arrays.equals(currentCnt, wordCnt)) {
result++;
}
}
System.out.println(result);
}
슬라이딩 윈도우 방법으로 하나씩 비교하면 되는 문제다.
항상 배열 값 하나하나 비교하는 방식을 사용했는데, 다른 풀이를 보다가 Arrays.equals로 비교가능하다는 걸 알게되었다.
2096 내려가기 - 골드5
https://www.acmicpc.net/problem/2096
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] minScore = new int[3];
int[] maxScore = new int[3];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int[] tmpMinScore = new int[3];
tmpMinScore[0] = getMin(minScore[0], minScore[1]) + a;
tmpMinScore[1] = getMin(minScore[0], minScore[1], minScore[2]) + b;
tmpMinScore[2] = getMin(minScore[1], minScore[2]) + c;
minScore = tmpMinScore;
int[] tmpMaxScore = new int[3];
tmpMaxScore[0] = getMax(maxScore[0], maxScore[1]) + a;
tmpMaxScore[1] = getMax(maxScore[0], maxScore[1], maxScore[2]) + b;
tmpMaxScore[2] = getMax(maxScore[1], maxScore[2]) + c;
maxScore = tmpMaxScore;
}
int realMax = 0;
int realMin = Integer.MAX_VALUE;
for (int i = 0; i < 3; i++) {
realMax = Math.max(realMax, maxScore[i]);
realMin = Math.min(realMin, minScore[i]);
}
System.out.println(realMax + " " + realMin);
}
슬라이딩 윈도우보단 dp로 보는게 맞는 문제인 것 같다.
3078 좋은 친구 - 골드4
https://www.acmicpc.net/problem/3078
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
//좋은 친구 쌍 = 결과값
long goodFriendPairCnt = 0L;
int n = Integer.parseInt(st.nextToken());
int windowSize = Integer.parseInt(st.nextToken()) + 1; //넘으면 친구가 아니다 = 같으면 친구다
//이름 입력 받기
int[] nameLen = new int[n];
for (int i = 0; i < n; i++) {
nameLen[i] = br.readLine().length();
}
//현재까지 이름 길이 개수 저장 - 시간줄이기 용
int[] currentCnt = new int[21];
for (int i=0; i<windowSize; i++) {
currentCnt[nameLen[i]] ++;
}
//초기 비교, 좋은 친구 쌍 갱신
for (int i =0; i<21; i++) {
if (currentCnt[i] > 1) {
goodFriendPairCnt += ((long)(currentCnt[i]) * (currentCnt[i] - 1) / 2);
}
}
//슬라이딩 윈도우 -> 추가된 애랑 앞에 친구들 비교만 하면 됨
for (int i = windowSize; i< n; i++) {
currentCnt[nameLen[i - windowSize]]--;
currentCnt[nameLen[i]]++;
goodFriendPairCnt += (currentCnt[nameLen[i]] - 1);
}
System.out.println(goodFriendPairCnt);
}
이름 길이 개수를 저장하지 않아서 시간초과가 발생했고, 친구 쌍 개수가 300,000 * 300,000 = 90,000,000,000 정도로 int 최대값을 넘어가는 경우를 고려하지 않아서 한 번 틀렸다.
슬라이딩 윈도우 과정에서 빠르게 비교할 수 있도록 개수값을 캐싱해두는 것과, 숫자범위만 잘 처리해주면 어렵지는 않은 문제다.
15961 회전 초밥 - 골드4
https://www.acmicpc.net/problem/15961
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int typeCnt = Integer.parseInt(st.nextToken());
int winSize = Integer.parseInt(st.nextToken());
int couponNum = Integer.parseInt(st.nextToken());
int[] tmpArr = new int[winSize]; //i % winSize 값을 임시로 채울 배열
int[] frontArr = new int[winSize]; //0 ~ winSize 값을 채우는 배열
int[] currentCnt = new int[typeCnt + 1]; //초밥 타입별 개수 저장할 배열
int currentTypeCnt = 0; //현재까지 타입개수
int maxTypeCnt = 0; //결과
//windowSize까지 채워주기
for (int i = 0; i < winSize; i++) {
int num = Integer.parseInt(br.readLine());
frontArr[i] = num;
tmpArr[i] = num;
currentCnt[num]++;
if (currentCnt[num] == 1) {
currentTypeCnt++;
}
}
int plusFood = (currentCnt[couponNum] == 0) ? 1 : 0; //쿠폰 초밥 추가 가능여부
if (currentTypeCnt + plusFood > maxTypeCnt) {
maxTypeCnt = currentTypeCnt + plusFood;
}
//슬라이딩 윈도우
for (int i = winSize; i < n; i++) {
int num = Integer.parseInt(br.readLine());
//현재 값 추가
currentCnt[num]++;
if (currentCnt[num] == 1) {
currentTypeCnt++;
}
//이전값 계산 -> tmpArr 에 저장해둔 값 사용
int prevNum = tmpArr[(i - winSize) % winSize];
currentCnt[prevNum]--;
if (currentCnt[prevNum] == 0) {
currentTypeCnt--;
}
plusFood = (currentCnt[couponNum] == 0) ? 1 : 0; //쿠폰 초밥 추가 가능여부
if (currentTypeCnt + plusFood > maxTypeCnt) {
maxTypeCnt = currentTypeCnt + plusFood;
}
tmpArr[i % winSize] = num;
}
//마지막 값들 처리
for (int i = 0; i < winSize - 1; i++) {
int prevNum = tmpArr[(n - winSize + i) % winSize];
currentCnt[prevNum]--;
if (currentCnt[prevNum] == 0) {
currentTypeCnt--;
}
//미리 저장해둔 값 사용
currentCnt[frontArr[i]]++;
if (currentCnt[frontArr[i]] == 1) {
currentTypeCnt++;
}
plusFood = (currentCnt[couponNum] == 0) ? 1 : 0; //쿠폰 초밥 추가 가능여부
if (currentTypeCnt + plusFood > maxTypeCnt) {
maxTypeCnt = currentTypeCnt + plusFood;
}
}
System.out.println(maxTypeCnt);
}
실버문제와 거의 동일한 문제다. 아마 입력값 범위만 달라진 것 같다.(시간초과가 날까봐 조마조마했다)
입력으로 들어오는 300만개 데이터를 다 저장할 수 없지만, 슬라이딩 윈도우를 위한 이전 값은 저장이 필요했다. 그래서 k크기만큼만 저장하고, 나머지 연산자를 열심히 사용해줬다.
나는 총 세 부분으로 나눠서 문제를 풀었다.
- 0 ~ k-1까지 처리 (초기값 저장 위함)
- k ~ n 까지 처리 (슬라이딩 윈도우로 갱신)
- 0 ~ k-1까지 처리 (순환 처리)
저장소는 이전 값을 저장할 tmpArr 과 0~k-1까지 값을 저장할 frontArr을 사용하였다.
슬라이딩 윈도우 과정에서 윈도우 사이즈를 벗어나 빼줘야하는 값은 tmpArr에서 빼왔고,
순환 처리 과정에서는 frontArr 값을 사용했다.
23295 스터디 시간 정하기 1 - 골드3
https://www.acmicpc.net/problem/23295
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int manCnt = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(st.nextToken());
int[] arr = new int[100_001]; //들어오고 나가는 사람 기록용(들어오면 1, 나가면 -1)
int[] sum = new int[100_001]; //만족도 캐싱용
//입력받기
for (int i = 0; i < manCnt; i++) {
int cnt = Integer.parseInt(br.readLine());
for (int j = 0; j < cnt; j++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
arr[start]++;
arr[end]--;
}
}
int startTime = 0;
int endTime = time;
long maxScore = 0;
long currentScore = 0;
//초기값 계산
int tmpScore = 0; //현재 나가거나 들어온 사람 값
for (int i = 0; i < time; i++) {
tmpScore += arr[i];
sum[i] = tmpScore; //캐싱
currentScore += tmpScore;
}
if (currentScore > maxScore) {
maxScore = currentScore;
}
//슬라이딩 윈도우
for (int i = time; i < arr.length; i++) {
currentScore -= sum[i - time]; //캐싱한 값 빼주기
tmpScore += arr[i];
sum[i] = tmpScore;
currentScore += tmpScore;
if (currentScore > maxScore) {
maxScore = currentScore;
startTime = i - time + 1;
endTime = i + 1; //시간범위는 1 더해줘야함
}
}
System.out.println(startTime + " " + endTime);
}
감도 안잡혀서 풀이를 찾아봤다. 들어오고 나가는 사람의 수를 체크하고, 슬라이딩 윈도우 방식으로 최댓값을 구해주면 어렵지 않게 구할 수 있었다. 아이디어를 찾는 게 가장 중요했다. (+ 범위값을 잘 봐야한다. long으로 안하면 틀린다)
5444 시리얼 넘버 - 골드1
https://www.acmicpc.net/problem/5444
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tcCnt = Integer.parseInt(br.readLine());
for (int t = 0; t < tcCnt; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] dp = new int[2][m];
Arrays.fill(dp[0], -1);
Arrays.fill(dp[1], -1);
dp[1][0] = 0;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
int serialNum = Integer.parseInt(st.nextToken());
int current = i % 2;
int prev = (i + 1) % 2;
for (int j = 0; j < m; j++) {
if (dp[prev][j] == -1) {
continue;
}
dp[current][j] = Math.max(dp[current][j], dp[prev][j]);
// 선택하는 경우
int next = (j + serialNum) % m;
if (dp[current][next] == -1 || dp[current][next] < dp[prev][j] + 1) {
dp[current][next] = dp[prev][j] + 1;
}
}
}
System.out.println(dp[(n - 1) % 2][0]);
}
}
문제유형은 슬라이딩 윈도우라고 되어있는데, 그냥 순환하는 dp문제였다. 아이디어는 떠올렸는데 관련 문제를 푼 경험이 없어서 애를 먹었다.
dp배열 크기를 줄이기 위해 %m을 사용하였고, 이전 데이터를 누적하기 위해 2개의 행도 사용해줬다. 2개의 행도 %2로 굉장히 아껴썼다. 신박한 유형이라 굉장히 재미있었다!
마치며..
슬라이딩 윈도우의 느낌은 알았는데, 아직 범위를 고려해서 깔끔하게 코드를 짜는 숙련도는 부족한 것 같다. 한 10개는 더 풀어봐야할 듯 하다.
'알고리즘 > 백준' 카테고리의 다른 글
| [JAVA] 백준 dp 부수기 (3) | 2025.05.17 |
|---|---|
| [JAVA] 백준 7579 앱 - 골드3 (1) | 2025.02.09 |
| [JAVA] 백준 union find 부수기(1) (1) | 2025.01.18 |
| [JAVA] 백준 스택 부수기 1 (0) | 2024.09.29 |
| [JAVA] 백준 문자열 부수기 1 (1) | 2024.09.28 |