슬라이딩 윈도우
슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음,범위를 유지한 채로 이동하여 문제를 해결하는 방법이다. 투포인터 알고리즘과 매우 비슷하고 원리도 간단하기 때문에 문제를 통해서 알아보겠다
DNA 비밀번호
이 문제의 경우 후처리를 하는데에 있어서 조금 애를 먹었다.
from sys import stdin
s, p = map(int, stdin.readline().split())
dna = stdin.readline();
a,c,g,t = map(int,stdin.readline().split())
start = dna[:p]
dic = {"A":0,"C":0,"G":0,"T":0}
answer = 0
for i in start:
dic[i] +=1
if dic["A"]>=a and dic["C"] >= c and dic["G"] >= g and dic["T"] >= t :
answer +=1
start_idx = 0
end_idx = start_idx + p
for i in range(s-p):
#s-p 까지 루프를 돌리는 이유
#슬라이딩 윈도우의 경우 뒤에껄 계속 붙이는 연산만 남아있기 때문에 남은 뒤에 것의 개수만 구하면 됨
dic[dna[start_idx+i]] -= 1
dic[dna[end_idx+i]] +=1
if dic["A"] >= a and dic["C"] >= c and dic["G"] >= g and dic["T"] >= t:
answer += 1
print(answer)import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
//슬라이딩 윈도우
//bj 12891
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st ;
st = new StringTokenizer(br.readLine()," ");
int S = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
char[] arr = br.readLine().toCharArray();
st = new StringTokenizer(br.readLine()," ");
int a = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int g = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
int answer = 0;
Map<String,Integer> map = new HashMap<>(){
{
put("A",0);
put("C",0);
put("G",0);
put("T",0);
}
};
for(int i=0;i<P;i++){
String target = String.valueOf(arr[i]);
map.put(target,map.get(target)+1);
}
if(map.get("A")>=a && map.get("C")>=c && map.get("G")>=g && map.get("T") >= t){
++answer;
}
int start_idx = 0;
int end_idx = start_idx + P ;
for(int i=0;i<S-P;i++){
String start = String.valueOf(arr[start_idx+i]);
String end = String.valueOf(arr[end_idx+i]);
map.put(start,map.get(start)-1);
map.put(end,map.get(end)+1);
if(map.get("A")>=a && map.get("C")>=c && map.get("G")>=g && map.get("T") >= t){
++answer;
}
}
System.out.println(answer);
}
}최솟값 찾기
이 문제는 처음에 이해하는 것 조차도 힘들었다.
문서로는 작성된게 없는 것 같고 유투브 영상을 통해서 문제를 이해할 수 있었다.
내가 이해한바를 토대로 설명해보려고 한다.
i - L + 1 에서 윈도우의 크기가 L 이 되는 이유를 이해하지 못했는데.
맨 첫번째 항목이 2개의 공백을 가지면서 시작하기 위해 다음과 같은 조건을 준것같다.
이런식으로 i - L + 1 ~ i 까지를 표시하면서 보면 이해하기가 쉽다.
그림은 L = 3 인 경우로 윈도우가 3인 것을 눈으로 확인 할 수 있다.
이것만 이해하면 구현에 있어서는 큰 어려움은 없다.
알고리즘 코딩테스트 문제풀이 강의 - 10 최솟값 찾기 1 (백준 11003)
문제의 핵심은 두가지다
- 디큐를 사용할 것
- 최솟값을 찾는 것에 집중할 것
- 윈도우의 크기에 맞는지 확인할 것
-
디큐가 나오는 이유
왜 디큐를 사용하는가 라는 의문이 생길 수 있다. 우리는 항상 정렬된 상태를 유지 할 것이다. 그리고 윈도우의 크기를 초과하면 왼쪽에 있는 원소를 잘라낼 것이다.
윈도우의 크기를 초과할때마다 우리는 왼쪽의 원소를 popleft로 쫒아낼 것이다.
그리고 항상 디큐의 순서가 유지되기 때문에 (왼쪽부터 시작해서 정렬된 상태) 항상 가장 왼쪽에 있는 원소가 가장 작을 것이다. 우리가 원하는 윈도우 안에서 가장 작은 원소이기 때문에 첫번째 원소를 항상 출력해주면 된다. 이런 점을 고려해봤을 때 디큐를 사용하는 것이다.
-
최솟값을 찾는 것에 집중 할 것
여기에서 가장 오른쪽에 있는 값보다 큰 값은 들어올 필요가 없다. 항상 디큐는 가장 왼쪽이 작고 가장 오른쪽이 크게 구성할 것이기 때문에 가장 오른쪽에 위치한 값보다 큰 값이 들어온다면 해당값을 쳐낼것이다. 반대의 경우에도 그럴 것이다. 가장 오른쪽에 있는 값이 새로 들어오는 값이 작다면 가장 오른쪽에 있는 값을 자르고, 작은 값을 넣을 것이다. 이러한 연산이 가능 한 이유는 디큐가 정렬된 채로 유지되기 때문이다.
-
윈도우의 크기에 맞는지 확인 할 것
해당 범위에서 가장 끝에 있는 값의 인덱스는 i-L+1를 가진다. 만약, 이것보다 작을경우 윈도우의 크기를 초과한 것이기 때문에 항상 확인해주어야한다.
from collections import deque
from sys import stdin
N,L = map(int,stdin.readline().split())
arr = list(map(int,stdin.readline().split()))
que = deque()
answer = []
for i in range(N):
while que and que[-1][0] > arr[i]:
que.pop()
while que and que[0][1] < i-L+1:
que.popleft()
que.append((arr[i],i))
print(que[0][0],end=" ")
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
//슬라이딩 윈도우
//bj 11003
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st ;
st = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
ArrayDeque<int[]> deque = new ArrayDeque<>();
st = new StringTokenizer(br.readLine()," ");
for(int i=0;i<N;i++){
arr[i] = Integer.parseInt(st.nextToken());
}
//입력받는 부분
//로직 시작
for(int i=0;i<N;i++){
while(!deque.isEmpty() && deque.getLast()[1] > arr[i]){
deque.pop();
}
while(!deque.isEmpty() && deque.getFirst()[0] < i-L+1 ){
deque.removeFirst();
}
deque.add(new int[] {i,arr[i]});
System.out.print(deque.getFirst()[1]+" ");
}
}
}→ 시간초과 에러
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
//슬라이딩 윈도우
//bj 11003
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 L = Integer.parseInt(st.nextToken());
ArrayDeque<Point> deque = new ArrayDeque<>();
st = new StringTokenizer(br.readLine()," ");
//입력받는 부분
//로직 시작
for(int i=0;i<N;i++){
int num = Integer.parseInt(st.nextToken());
while(!deque.isEmpty() && deque.peekLast().num > num){
deque.pollLast();
}
if(!deque.isEmpty() && deque.peekFirst().idx < i-L+1 ){
deque.pollFirst();
}
deque.addLast(new Point(num,i));
bw.write(deque.peekFirst().num+" ");
}
bw.flush();
}
public static class Point{
int num, idx;
Point(int num, int idx) {
this.num = num;
this.idx = idx;
}
}
}알아보기 쉽게 Point 클래스를 추가하고 , while 로직을 없앴다 이랫는데도 시간초과 올라와서..다른 코드 찾아보면서 내 로직에 있어서 터질 이유가 없는데 하면서 보다가 유일하게 다른 점이 있었다..
바로 System.out.println() 구문.. 이것말곤 다른게 없더라.. 그래서 변경해주었더니 안터져서..앞으로는 System.out.println 대신 무조건 bw를 사용하려고 한다… 이것때문에 터지면 얼마나 속상해..
