투 포인터와 슬라이딩 윈도우
위의 두 알고리즘은 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 하는 경우에 O(n^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(n)으로 줄일 수 있는 알고리즘을 말합니다.
공유하는 개념은 비슷하나, 투 포인터와 슬라이딩 윈도우의 차이는 부분 배열 길이의 변화 여부입니다. 투 포인터의 경우는 부분 배열의 길이가 가변적(연속되고)이나, 슬라이딩 윈도우는 부분 배열의 길이가 고정적이라는 차이가 있습니다.
투 포인터
이러한 투포인터는 연속되는 부분 배열에 대해서 문제를 해결하는 것이 아닌 경우에는 해당 알고리즘을 사용할 수 없습니다. 이런 경우에 사용하기 위해서는 따로 요소를 리스트 혹은 배열에 저장하고 사용해야 합니다. 이렇게 투 포인터 알고리즘의 전형적인 유형은 두가지가 있습니다.
1. 2개의 포인터 변수 시작점이 배열의 시작점인 경우
2. 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점에 위치한 경우
이렇게 투 포인터를 사용하기 위해서는 대개 left, right라는 변수를 선언하여 문제를 풀게 됩니다. 이렇게 각 변수의 인덱스가 움직이는 조건은 아래와 같습니다.
1. 부분 배열의 합이 Target 값보다 크거나 같으면 left = left+1. (부분 배열의 길이를 줄여 합을 빼줍니다.)
if(sum >= target) left++;
2. 부분 배열의 합이 Target 값도가 작으면 right = right+1. (부분 배얄의 길이를 늘려 합을 더합니다.)
if(sum < target) right++;
3. 부분 배열의 합이 Target 값과 같다면 결과 값을 +1 해줍니다.
if(sum == target) count++;
슬라이딩 윈도우
슬라이딩 윈도우 알고리즘은 연속되는 투 포인터와 유사하게 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘이지만, 길이가 고정적입니다. 이렇게 길이를 고정적으로 잡기 때문에 포인터 변수가 2개일 필요 없습니다. 즉, 배열의 끝은 쉽게 알 수 있다는 장점이 있습니다.
예제 풀이
Inputs
8 30 4 30
7
9
7
30
2
7
9
25초기 아이디어
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));
List<Integer> belt = new ArrayList<>();
String[] inputs = br.readLine().split(" ");
int sushi = Integer.parseInt(inputs[0]);
int sushiAmount = Integer.parseInt(inputs[1]);
int plates = Integer.parseInt(inputs[2]);
int cupon = Integer.parseInt(inputs[3]);
// 초밥을 일단 넣음
for(int i = 0; i < sushi; i++){
int sushiOne = Integer.parseInt(br.readLine());
belt.add(sushiOne);
}
int max = 0;
for(int i = 0; i < sushi; i++){
int j = i;
int sushiBelt = plates;
Set<Integer> sushiSet = new HashSet<>();
while(sushiBelt > 0){
if(j >= belt.size()){
j = 0;
}
sushiSet.add(belt.get(j));
j++;
sushiBelt--;
}
if(!sushiSet.contains(cupon)){
max = Math.max(max, sushiSet.size()+1);
}else{
max = Math.max(max, sushiSet.size());
}
}
bw.write(max + "");
bw.close();
br.close();
}
}해당 코드는 일단 입력에 대한 것을 받은 후, HashSet 이라는 자료구조를 통해서 입력되는 변수 중 중복되는 것이 있으면 똑같이 저장되지 않는 특징을 이용하여 각 경우 별로, HashSet의 사이즈를 확인 하고, 그 set안에 coupon에 해당하는 변수가 있다면 그냥 사이즈에 대한 값과 비교하여 출력하고 아닌 경우에는 쿠폰의 경우의 수를 더한 +1을 하여 비교를 하여 출력합니다.
개선된 코드
package baekjoon;
import java.io.*;
import java.util.*;
public class sushiMain {
public static void main(String[] args) throws IOException{
Scanner sc = new Scanner(System.in);
int sushi = sc.nextInt();
int sushiAmount = sc.nextInt();
int plates = sc.nextInt();
int cupon = sc.nextInt();
int[] belt = new int[sushi];
int[] menu = new int[sushiAmount+1];
// 초밥을 일단 넣음
for(int i = 0; i < sushi; i++){
belt[i] = sc.nextInt();
}
// 메뉴에 대한
int cnt = 1, ans = 0;
menu[cupon]++;
for(int i = 0; i < plates; i++){
if(menu[belt[i]]++ == 0) cnt ++;
}
System.out.println(Arrays.toString(menu));
for(int i = plates; i < sushi + plates; i++){
if(--menu[belt[i-plates]] == 0) cnt --;
if(menu[belt[i % sushi]]++ == 0) cnt ++;
ans = Math.max(cnt, ans);
}
System.out.println(ans);
}
}기존의 코드에는 모든 경우에서 HashSet이라는 자료구조를 생성하고 비교하여 결과를 도출하기 때문에 시간이 상당히 많이 소요가 됩니다. 그래서 이러한 부분을 수정하기 위해서 모든 종류에 대한 배열을 menu라고 하여 생성 한 후, 첫번째 경우(belt 라는 배열에 저장한 변수 중 앞의 4개)에 대해서 +1을 하여 줍니다.
[0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]
그러면 위와 같은 형태로 답이 도출되게 됩니다.
int cnt = 1, ans = 0;
menu[cupon]++;
for(int i = 0; i < plates; i++){
if(menu[belt[i]]++ == 0) cnt ++;
}
for(int i = plates; i < sushi + plates; i++){
if(--menu[belt[i-plates]] == 0) cnt --;
if(menu[belt[i % sushi]]++ == 0) cnt ++;
ans = Math.max(cnt, ans);
}일단 cnt는 첫번째 반복문에 의해서 중복되는 경우, 이미 +1이 되어 있는 경우,에는 cnt를 증가 시키지 않음으로써 3이되고 다음 다음 반복문으로 갑니다. 다음 반복문을 plates로 시작하여 돌리는 이유는 belt라는 배열안에 요소가 inputs에 따라 4개가 들어 있을 것입니다. 그렇기 때문에 반복문이 돌아감에 따라, 계속 다음 변수의 값을 비교하면서 확인해야 하기 때문에 위 같이 작성합니다.
- i-plate : 0, 1, 2, 3, 4, 5, 6, 7
- i % sushi : 4, 5, 6, 7, 0, 1, 2, 3
이렇게 바뀌기 때문에 처음에 이미 넣어 둔 배열에 대해서는 i-plate를 통해서 처리를 하여, 0이 아닐 경우에는 cnt를 줄이지 않고 그냥 넘어 갑니다. 그 와중에 --를 앞에 넣었기 때문에 해당 값에 대해서는 처리가 됩니다. 그 다음 조건문은 초반 4개 이후부터(2부터) 확인을 하기 때문에 만약 0인 경우, cnt를 증가 시켜줍니다. 이렇게 반복문을 지속을 하게 되면 아래와 같은 과정을 거치게 됩니다.
[0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]
[0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]
[0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]
[0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]
[0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]
[0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]
[0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]시작을 0과 4에서 시작을 따로 하여 반복문의 반복 횟수를 기본적으로 줄입니다. 그리고, 이렇게 함으로써 효율성을 챙기고 연속적인 변수에 대해서 중복이 있는 경우 cnt를 빼면서 기존에 입력한 값을 수정합니다. 이렇게 하면, 순차대로 7 9 7 30, 9 7 30 2 이런식으로 먹었던것을 빼고 새것을 더하는 식으로 진행할 수 있게 됩니다.
