[GDSC Week2-4] 백준 3078번:: 좋은친구 (C++)

 

 

* 생각한 아이디어 및 문제 풀이

0. 이름 길이별로 벡터를 생성한다.

1. 등수가 k만큼 차이나는 사람과 이름 길이를 비교하고 해당 길이의 벡터에 ++을 한다.
2. 만약 큐의 사이즈가 K 이상이라면 비교 숫자를 벗어난 것이므로 큐의 맨 앞에 위치한 문구를 삭제한다. 

3. 이를 반복해서 좋은 친구를 출력한다.

 

 

* 코드

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

int main(){
    ios::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);
    
    int N, K, len;
    long long Good=0;
    string input;
    vector<int> v(21);
    queue<int> q;
    
    cin >> N >> K;
    for(int i=0; i<N; i++){
        cin >> input;
        len = input.length();
        Good += v[len];
        
        if( int(q.size()) >= K){
            v[q.front()]--;
            q.pop();
        }
        v[len]++;
        q.push(len);
    }
    cout << Good;
}

 

* 회고

자료형을 잘 확인해야겠다.

1초는 시간복잡도 계산할 시 1억이라는 점,

결과 값이 21억을 넘긴다면 int 대신 long long을 써야하는 점을 기억하자.

또한 위처럼 각각 벡터 큐를 따로 구현하는 것보다 더 쉽게 푸는 방법이 있지 않을까 하는 생각이 든다.

 

 

* 문제 링크 : https://www.acmicpc.net/problem/3078

3078번: 좋은 친구

 

* 참고 링크 : https://slllju.tistory.com/77

[BOJ 3078] 좋은 친구 (풀이)