11. 슬라이딩 윈도우 [BOJ 3078번]

1. 관련 문제 🎯

문제 : 백준 3078 좋은 친구 👭
난이도 : 골드 4

2. 문제 소개 🧩

1️⃣ 상근이네 반의 N명 학생들의 이름이 성적순으로 주어진다.
2️⃣ 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.

• 따라서, 좋은 친구는 총 2가지의 조건을 만족해야 한다.
• 1) 등수의 차이가 K보다 작거나 같다.
• 2) 이름의 길이가 같다.

3️⃣ 좋은 친구가 몇 쌍이나 있는지 구한다.

• 위의 예시를 살펴보면, 좋은 친구쌍은 총 5쌍이 있다는 것을 알 수 있다!

3. 문제 풀이 🖌️

이때, 좋은 친구는 등수의 차이가 K보다 작거나 같은 조건을 만족해야 한다.
즉, K=2라면 1등~3등까지의 사람들 사이에서 이름의 길이가 같은 친구가 있는지 살펴보면 된다. 이처럼 배열의 길이가 3으로 고정된 채 비교해보는 슬라이딩 윈도우를 사용하여 이번 문제를 해결해보아야 한다!!

3-1. 슬라이딩 윈도우를 사용한 문제 풀이

• 먼저, 친구들의 이름을 하나의 배열에 입력을 받는다.
  그리고 시작점(X등)을 1등부터 차례대로 지정해주면 자동으로 K를 통해서 끝점(X+2등)을 지정할 수 있다.
• 1등~3등 사이에 좋은 친구쌍이 있는지 살펴보고, 다 살펴보았다면 시작점을 1등을 증가시켜서 2등~4등 사이에 좋은 친구쌍이 있는지를 살펴본다.
  
• 이때, 2등과 3등은 겹치게 된다!
  
• 따라서 처음 구하는 1등~3등까지의 부분은 그대로 구하고, 그 다음부터는 추가되는 등수인 4등을 기준으로 2등과 4등을 살펴보고 4등과 3등을 살펴본다.
  

4. 시간 초과 풀이 🔥

#include <iostream>
using namespace std;

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

    int N = 0, K = 0;    //학생의 수, 좋은 친구가 되는 조건(K)
    int friends[300001];
    string friend1 = "";
    long long ans = 0;    //좋은 친구쌍의 수

    cin>>N>>K;
    //1등부터 차례대로 이름을 입력받는다.
    for(int i=1; i<=N; i++){	
        cin>>friend1;
        friends[i] = friend1.size();
    }

	//처음에는 겹치는 부분을 고려하지 않고, 1등부터 K+1등까지 길이가 같은지 살펴본다.
    for(int i=1; i<=K; i++){ 
        for(int j=i+1; j<=K+1; j++){
            if(friends[i] == friends[j]){
                ans++;
            }
        }   
    }
	
    //겹치는 부분을 고려하여 끝에 추가되는 부분을 기준으로 길이가 같은 친구가 있는지 살펴본다.
    for(int i=K+2; i<=N; i++){
        for(int j=1; j<=K; j++){
            if(friends[i] == friends[i-j]){
                ans++;
            }
        }
    }
    cout<<ans<<"\n";
}

5. 성공한 코드 🫧

다른 블로그들을 참고하여 문제를 해결했다 🥲
하나씩 비교하는 것이 아니라 계수 정렬처럼 이름의 길이 배열을 선언하여 이름의 길이가 같은지를 확인하는 방법을 사용한다!

• 슬라이딩 윈도우에서 사용하는 배열(x등~x+k등)에 속한 등수에 해당하는 이름들의 길이를 [이름의 길이 배열]에 더해준다.
  
  

#include <iostream>
using namespace std;

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

    int N = 0, K = 0;    //학생의 수, 좋은 친구가 되는 조건(K)
    int friends[1000000];
    int cnt[23]={0,};	//이름의 길이 배열
    string friend1 = "";
    long long ans = 0;    //좋은 친구쌍의 수

    cin>>N>>K;
    for(int i=1; i<=N; i++){
        cin>>friend1;
        friends[i] = friend1.size();
    }

	//처음에는 겹치는 부분을 고려하지 않고, 1등부터 K+1등까지 길이를 cnt배열에 개수를 넣는다.
    for(int i=1; i<=K+1; i++){
        cnt[friends[i]]++;
    }
    
    //겹치는 부분을 고려하여, 윈도우의 끝에 추가될 friends[i+k+1]만 추가해준다.
    for(int i=1; i<=N; i++){
        cnt[friends[i]]--;	//자기 자신의 길이는 제외한다.
        ans += cnt[friends[i]];	//좋은 친구쌍의 수을 더해준다.
        cnt[friends[i+K+1]]++;	//슬라이딩 윈도우를 오른쪽으로 이동시킨다.
    }
    cout<<ans<<"\n";
}

참고한 블로그 : https://wantchicken.tistory.com/75

6. 결과 🏆