[3078번] 좋은 친구

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 라인 스위핑

2. 투 포인터

3. vector STL :: http://www.crocus.co.kr/500 // http://www.crocus.co.kr/500

4. 적절한 아이디어

이 문제를 풀며 정말 많은 시간을 보냈고, 많은 아이디어를 생각해 보았던 것 같다.

시간초과를 무려 8번이나 받아서 최적화에 최선을 다하였고, 결국에는 다른 알고리즘을 다시 생각하여 풀게 된 문제이다.

1. 이름을 입력 받으면 이름의 길이를 알아내어 그 길이에 해당하는 q 벡터에 그 이름의 index를 넣어준다.

2. 두번째 for문에서는 이제 모든 이름의 길이가 같은 사람들을 상대로, index를 조사하여 좋은 친구인지 확인 해 주면 된다.

3. left, right 두개의 변수를 이용하여 좋은 친구를 조사한다.

(자세한 내용은 주석으로 달아두었습니다.)

결국 필자가 생각한 아이디어는 이름 길이에 해당하는 큐 벡터를 만들어 

이름은 이제 무시하고 인덱스로 승부를 본다는 것을 이용하여 이 문제를 해결하였다.

확실한 것은 조금 더 최적화를 할 필요가 있는 소스 코드이다.

소스 코드 : 

#include <iostream>
#include <string.h>
#include <vector>
 
using namespace std;
 
vector<int> q[25];
char str[21];
 
int main()
{
    int n, k;
    long long int cnt = 0;
    long long int tmp = 0;
    int charlen;
    
    scanf("%d %d", &n, &k);
 
    // 이름을 입력 받았을 때 이름 길이에 해당하는 
    // q 벡터에 이름이 아닌 그 이름이 나온 순서를 넣어준다.
    for (int i = 0; i < n; i++)
    {
        scanf("%s", str);
 
        charlen = strlen(str);
        q[charlen].push_back(i);
    }
 
    for (int i = 2; i <= 20; i++)
    {
        int idxlen = q[i].size();
        int left = 0, right = 0;
 
        // 큐가 비어있는 경우 다음 큐로 간다.
        if (!idxlen)
            continue;
 
        // left가 idxlen(해당하는 큐의 크기)에 도달할 때 까지
        while(left < idxlen - 1)
        {
            // right가 끝에 도달하지 않았고, 좋은 친구에 해당 될 때
            if (right < idxlen - 1 && q[i][right] - q[i][left] <= k)
            {            
                    // right를 한칸 옮겨주고 tmp++
                    right++;
                    tmp++;
 
                    // right를 한칸 옮겼을 때 q[][right] - q[][left] == k일 때
                    if (q[i][right] - q[i][left] == k)
                    {
 
                        // 모아둔 tmp를 더해주고 left를 한칸 옮기기에 tmp는 하나 빼준다.
                        cnt += tmp;
                        tmp--;
                        left++;
                    }
            }
 
            // 그외 경우
            else
            {    
                // q[][right] - q[][left] <= k 일때만 더해준다.
                if (q[i][right] - q[i][left] <= k)
                    cnt += tmp;
                
                // 그게 아니라면 tmp -1을 한 값을 더해준다.
                else
                    cnt += tmp - 1;
 
                tmp--;
                left++;
            }
        }
 
        // 해당하는 큐가 끝나면 tmp = 0으로 초기화
        tmp = 0;
    }
 
    printf("%lld", cnt);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>