12891번

수도 코드

checkArr (필요한 A, C, G, T의 개수 배열)
myArr (현재 비밀번호 문자열에 포함된 A, C, G, T의 개수 배열)
S_length (문자열 크기), P_length (부분 문자열 크기)
DNA_str (문자열 데이터)

myArr 배열 0으로 초기화 하기
S_length 입력 받기
P_length 입력 받기
DNA_str 입력 받기
checkArr 배열 입력 받기

start_index = 0 // 슬라이딩 윈도우의 왼쪽 포인터
end_index = P_length - 1 // 슬라이딩 윈도우의 오른쪽 포인터

for(P_length 만큼 반복): // 현재 비밀번호 문자열에 대해 myArr 업데이트
	myArr 업데이트

answer = 0 // 정답 초기화

// 비밀번호 문자열이 DNA문자열 끝에 도착할때까지 반복
while(end_index != S_length): 
	
    // checkArr 와 myArr 비교 후 정답 업데이트
    if(C[0] >= A[0] && C[1] >= A[1] && C[2] >= A[2] && C[3] >= A[3]):
        answer++;
        
	비밀번호 문자열의 왼쪽 문자열을 myArr에서 뺀다
    
    start_index++
    
    end_index++
    
    비밀번호 문자열의 오른쪽 문자열을 myArr에서 추가한다
    
answer 출력

답안

#include <iostream>
#include <vector>

using namespace std;

int S_length;
int P_length;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  string DNA_string;
  int A[4] = {0,}; // A, C, G, T가 포함되어야 하는 수
  int C[4] = {0,}; // 비밀번호 문자열에 포함된 A, C, G, T의 수
  cin >> S_length >> P_length;
  cin >> DNA_string;
  cin >> A[0] >> A[1] >> A[2] >> A[3];

  int start_index = 0 ;
  int end_index = P_length - 1;
  for(int i = 0; i < P_length; i++){
    switch(DNA_string[i]){
      case 'A':
        C[0]++;
        break;
      case 'C':
        C[1]++;
        break;
      case 'G':
        C[2]++;
        break;
      case 'T':
        C[3]++;
        break;
    }
  }
  int answer = 0;
  while(end_index != S_length){
    if(C[0] >= A[0] && C[1] >= A[1] && C[2] >= A[2] && C[3] >= A[3]) answer++;
    switch(DNA_string[start_index]){
      case 'A':
        C[0]--;
        break;
      case 'C':
        C[1]--;
        break;
      case 'G':
        C[2]--;
        break;
      case 'T':
        C[3]--;
        break;
    }
    start_index++;
    end_index++;
    switch(DNA_string[end_index]){
      case 'A':
        C[0]++;
        break;
      case 'C':
        C[1]++;
        break;
      case 'G':
        C[2]++;
        break;
      case 'T':
        C[3]++;
        break;
    }
  }
  cout << answer << "\n";
}

11003번⭐

아이디어

• 정렬 알고리즘을 사용하지 않고도 슬라이딩 윈도우와 덱(deque)을 이용해서 정렬 효과를 낸다.

수도 코드

N (데이터 개수), L (최소값을 구하는 범위)

Node 타입 선언(인덱스, 값)
deque<Node> mydeque (데이터를 담을 덱 자료구조)

N 입력
L 입력

end_index = 0 // 슬라이딩 윈도우의 우측 끝 인덱스

while(end_index != N):
	
    now(현재 데이터) 입력
    
    덱의 마지막 위치에서부터 now보다 큰 값들은 덱에서 제거
    
    덱의 마지막 위치에 now값 저장
    
    덱의 첫 번째 위치에서부터 L의 범위를 벗어난 값을 덱에서 제거
    (덱 값의 index <= end_index - L)
    
    덱의 첫 번째 데이터 출력
    
    end_index++

답안

#include <iostream>
#include <deque>

using namespace std;
typedef pair<int, int> Node;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N, L;
  cin >> N >> L;
  deque<Node> mydeque;

  for(int i = 0; i < N; i++){
    int now;
    cin >> now;
    while(mydeque.size() && mydeque.back().second > now){
      mydeque.pop_back();
    }
    mydeque.push_back(Node(i, now));
    if(mydeque.front().first <= i - L){
      mydeque.pop_front();
    }
    cout << mydeque.front().second << " ";
  }
}