[ 백준 3078 ] 좋은 친구 (C++)

백준의 좋은친구(3078) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

주어진 친구 목록에서 성적의 등수가 K 이하이면서 글자수가 같은 친구를 좋은 친구라 정의 할 때, 주어진 목록에서 친구는 총 몇 쌍이 있는지 구해야 하는 문제이다.

풀이에 사용되는 자료구조와 어떻게 활용했는지부터 정답도출까지 순차적으로 알아보자.

 

#1. Queue를 이용한 목록 관리

본인은 자료구조 Queue를 이용해서 이 문제를 접근하였다. Queue는 "선입선출(FIFO)"의 구조를 가진 자료구조이다. 즉 ! 먼저 Queue에 들어간 데이터가 먼저 빠질 수 밖에 없다. 그렇다면 이 문제에서 이 성질이 어떻게 적용될까 ??

본인은 이 성질을 이 문제에서 "등수"에 적용시켰다.

문제에서 주어지는 리스트들은 '성적순'으로 나열이 된다. 즉 ! 입력으로 주어지는 리스트들을 순차적으로 Queue에 넣게 된다면, 자연스럽게 Queue의 가장 앞쪽에는 성적이 높은 사람이, 뒤쪽에는 성적이 낮은 사람이 배치되어 질 것이다.

즉 ! 우리는 여기서 Queue에 저장되는 값이 단순히 "등수" 라는 것을 알 수 있다. Queue에서는 등수를 위한 'int'형 변수를 자료형으로 가지고 관리해 줄 것이다.

보다 구체적인건 이 후에 Queue를 구체적으로 어떻게 설정하고 관리했는지에 대해서 이야기를 한 후에 알아보자.

 

#2. Queue배열을 이용한 목록 관리

#1에서는 Queue에 등수를 저장한다는 것에 대해서 이야기를 했다.

그런데 ! 좋은 친구가 되기 위해서는 친구와 이름의 길이 또한 같아야 한다고 되어있다.

따라서, 본인은 Queue배열을 하나 만들어 주었다.

Queue Q[25] 이런 식으로 배열을 만들어 주었는데, 이는 다음과 같은 의미를 가진다.

Q[A] 에는 "이름의 길이가 A인 사람들이 모여 있는 곳" 을 의미한다.

즉 ! #1의 내용과 위의 내용을 합쳐보면, Queue에는 "Queue배열에서 배열이 가지는 Index를 이름의 길이로 가지는 사람들을 등수 순으로 저장해 놓는다."

 

#3. 코드 분석

	long long Answer = 0;
	queue<int> Q[25];
	for (int i = 1; i <= N; i++)
	{
		int Len = Student[i].length();
		while (Q[Len].empty() == false && i - Q[Len].front() > K) Q[Len].pop();
		Answer += Q[Len].size();
		Q[Len].push(i);
	}

본인이 구현한 코드이다. 코드가 굉장히 간단하다는 것을 알 수 있다.

lin6)에 있는 while문을 보게 되면, "등수가 K등 넘게 차이나는 친구들을 리스트에서 빼기 위한 과정" 이 진행되고 있다.

무조건, Queue에 앞에 있는 친구가 등수가 더 높은 친구일 것이므로 위와 같이 앞에 있는 친구들부터 순차적으로 빼주면서 등수가 K등 이내인 친구를 찾고 있다.

그리고 line7)에서 해당 Queue에 남아있는 친구의 수만큼 정답을 +시켜주고 있다. Queue[Len]에 들어있는 친구들은 일단 자기와는 모두 이름의 길이가 같은 친구들만 모여 있는 곳이고, line6)에서 pop()되지 않았다는 것은 자기와 등수 차이가 K등이내인 친구들이라는 이야기이므로, 무조건 Queue에 남아있는 친구의 수가 현재 탐색하고 있는 '나'와 친구로써 한 쌍이 될 수 있다는 이야기이다.

 

#4. 소스코드

#include <iostream>
#include <string>
#include <queue>
 
#define endl "\n"
#define MAX 300010
using namespace std;
 
int N, K;
string Student[MAX];
 
void Input()
{
    cin >> N >> K;
    for (int i = 1; i <= N; i++) cin >> Student[i];
}
 
void Solution()
{
    long long Answer = 0;
    queue<int> Q[25];
    for (int i = 1; i <= N; i++)
    {
        int Len = Student[i].length();
        while (Q[Len].empty() == false && i - Q[Len].front() > K) Q[Len].pop();
        Answer += Q[Len].size();
        Q[Len].push(i);
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}