[G4] 백준 3078번 좋은 친구 C++ 큐, 슬라이딩 윈도우

리뷰

 

https://www.acmicpc.net/problem/3078

큐를 사용한 간단한 슬라이딩 윈도우 문제

 

 

전역 변수

• n, k : 친구의 수 n, 등수의 최대 차이 k
• lst : 친구의 이름 길이를 저장할 정수형 배열
• v : 슬라이딩 윈도우 내 각 이름의 길이의 개수를 저장할 정수형 배열
• ans : 정답을 저장하기 위한 변수, 최악의 경우 30만^2 / 2가 주어질 것 같아 long long타입을 사용했다.
• q : 슬라이딩 윈도우로 사용할 큐

 

함수

1. input

void input()

 

변수와 배열 초기화를 진행할 함수

1. n, k를 입력 받고 n번의 반복문을 실행한다.
2. 친구의 이름 s를 입력 받고, 해당 이름의 길이를 lst배열에 저장해 준다.

 

2. init

void init()

 

초기 슬라이딩 윈도우를 초기화 하기 위한 함수

1. 0 ~ k번의 반복문을 실행해 준다.
2. ans에 동일한 이름의 길이를 가진 친구들의 개수를 더해준다.
3. 현재 친구 이름의 길이를 증가시켜 준다.
4. 슬라이딩 윈도우 q에 현재 친구 이름의 길이를 넣어준다.

 

3. solve

void solve()

 

슬라이딩 윈도우를 움직이며 문제를 해결하기 위한 함수

1. k + 1 ~ n - 1번의 반복문을 진행해 준다.
2. 큐에서 요소를 하나 뺀 뒤 그 친구의 이름 길이의 개수를 감소시킨다.
3. 이후 내용은 init의 로직과 동일하다.

 

문제풀이

1. input 함수를 통해 변수와 배열의 값을 초기화 해준다.
2. init 함수를 통해 슬라이딩 윈도우의 초깃값과 ans를 최신화 해준다.
3. solve 함수를 통해 슬라이딩 윈도우를 움직이며 ans를 최신화 해준다.
4. ans에 저장된 값을 출력해 준다.

 

참고 사항

ans를 애초에 long long타입으로 설정하였는데 int로도 가능한지는 잘 모르겠다.

 

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;

int n, k;
int lst[300000];
int v[21];
long long ans = 0;
queue<int> q;

void input() {
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		string s; cin >> s;
		lst[i] = s.size();
	}
}

void init() {
	for (int i = 0; i <= k; ++i) {
		ans += v[lst[i]];
		v[lst[i]]++;
		q.push(lst[i]);
	}
}

void solve() {
	for (int i = k + 1; i < n; ++i) {
		v[q.front()]--;
		q.pop();
		ans += v[lst[i]];
		v[lst[i]]++;
		q.push(lst[i]);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();
	init();
	solve();
	cout << ans;
}