[파트1] 코딩테스트 기초 (슬라이딩 윈도우)

📢 슬라이딩 윈도우

2개의 포인터로 범위를 지정한 다음, 범위를 유지한 채로 이동하며 문제 해결

• 투 포인터와 원리 유사

---

문제 1. 백준 12891번 DNA 비밀번호

🔎 접근법 (가정) 전체 길이 S 부분 길이 P

1. 길이가 P인 윈도우를 지정하여 배열 S 시작점에 놓기
2. 오른쪽으로 밀면서 조건 탐색
3. P 문자열이 배열 S 끝에 도달할 때까지 이동

<중요>

• 비밀번호 체크 배열, 현재 상태 배열, 조건 충족 판단 변수 필요
• 메서드를 따로 만들어 슬라이딩 윈도우 실행할 것

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	// 모든 메서드에서 사용할 수 있도록 static으로 선언
	static int checkArr[]; // 조건 배열
	static int myArr[]; // 현재 상태 배열
	static int total; // 몇 개의 문자와 관련된 개수를 충족했는지 판단

	public static void main(String[] args) throws IOException {

		/* 백준 12891번 DNA 비밀번호 */
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer line1 = new StringTokenizer(br.readLine());
		
		// 1. 변수 초기화
		int length = Integer.parseInt(line1.nextToken()); // DNA 문자열 길이
		int sLength = Integer.parseInt(line1.nextToken()); // 부분 문자열 길이
		int result = 0; // 몇 개가 총 조건이 충족됐는지
		
		char [] arr = br.readLine().toCharArray(); // 입력받은 문자열 배열
		checkArr = new int[4]; // 4인 이유는 조건 A, C, G, T 4개이기 때문
		myArr = new int[4];
		total = 0;
		
		
		StringTokenizer line2 = new StringTokenizer(br.readLine());
		
		// 조건 저장
		for(int i = 0; i < 4; i++) {
			checkArr[i] = Integer.parseInt(line2.nextToken());
			if(checkArr[i] == 0) total++; // 있든 없든 조건 무조건 충족하는 것이기 때문에 증가
		}
		
		// 2. 초기 윈도우 처리
		for (int i = 0; i < sLength; i++) {
		    Add(arr[i]);
		}
		
		if(total == 4) result++;
		
		// 3. 슬라이딩 윈도우 시작
		for(int i = sLength; i < length; i++) {
			int n = i - sLength; // 예. sLength = 4, i = 4이면 n = 0 length가 6이면 n=2까지
			
			Add(arr[i]); // arr[4] 
			remove(arr[n]); // arr[0]
			if(total == 4) result++; 
			
		}
		
		System.out.println(result);
		
		
	}
	
	// [조건에 맞는 문자 처리 1]
	// 새로 들어온 문자에 대한 조건 처리
	// 조건 배열인 check와 현재 my가 같을 경우 충족변수 +
	private static void Add(char c) {
		switch (c) {
		case 'A':
			myArr[0]++;
			if(checkArr[0] == myArr[0]) total++;
			break;
		case 'C' :
			myArr[1]++;
			if(checkArr[1] == myArr[1]) total++;
			break;
		case 'G' :
			myArr[2]++;
			if(checkArr[2] == myArr[2]) total++;
			break;
		case 'T' :
			myArr[3]++;
			if(checkArr[3] == myArr[3]) total++;
			break;
		}
	}
	
	// [조건에 맞는 문자 처리 2]
	// 이전 문자 제거하기
	
	private static void remove(char c) {
		switch(c) {
		case 'A' :
			if(checkArr[0] == myArr[0]) total--;
			myArr[0]--;
			break;
		case 'C' :
			if(checkArr[1] == myArr[1]) total--;
			myArr[1]--;
			break;
		case 'G' :
			if(checkArr[2] == myArr[2]) total--;
			myArr[2]--;
			break;
		case 'T' :
			if(checkArr[3] == myArr[3]) total--;
			myArr[3]--;
			break;
		}
	}
	
}

remove()함수에서

case 'A' :
	if(checkArr[0] == myArr[0]) total--;
	myArr[0]--;
	break;

이 부분을 원래

case 'A' :
	 myArr[0]--;
     if(checkArr[0] == myArr[0]) total--;
	 break;

이렇게 써버림.. 현재 상태를 제거하고 비교하면 당연히 안 맞겠죠..?

문제2. 백준 11003번 최솟값 찾기

🔎 접근법
1. 덱의 구조 이해 : 양끝에서 데이터 삽입 / 삭제 가능

• 형태 : (인덱스, 숫자)
• 앞 인덱스와 뒤 인덱스의 값을 비교하여 뒤의 인덱스가 클 경우 추가 뒤에 인덱스가 작을 경우엔 앞 인덱스 제거 과정을 거치며 정렬됨

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;


public class Main {
	
	// public static final Scanner scan = new Scanner(System.in);
	
	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 line1 = new StringTokenizer(br.readLine());
		
		int s = Integer.parseInt(line1.nextToken()); // 전체 크기
		int p = Integer.parseInt(line1.nextToken()); // 슬라이딩 윈도우 크기
		
		StringTokenizer line2 = new StringTokenizer(br.readLine());
		
		Deque<Node> nums = new LinkedList<>(); // 숫자 배열 데크 형식
		
		for(int i = 0; i < s; i++) {
			int now = Integer.parseInt(line2.nextToken());
			
			while(!nums.isEmpty() && nums.getLast().value > now) { // 새로운 값보다 이전 값이 크다면 제거
				nums.removeLast();
			}
			
			nums.addLast(new Node(now, i));
			
			// 범위에서 벗어난 인덱스 제거
			if(nums.getFirst().index <= i - p) {
				nums.removeFirst();
			}
			
			bw.write(nums.getFirst().value + " ");
		}
		
		bw.flush(); // 출력
		bw.close();
	}

	// Node 형식 정하기
	static class Node {
		public int value;
		public int index;
		
		Node(int value, int index) {
			this.value = value;
			this.index = index;
		}
	}
}

BufferdWriter은 처음 써보는데 bw.write()했는데 왜 콘솔에 안 나오지 싶었다. 근데 bw.flush() 해줘야 출력됨