[백준] 3078 좋은 친구

백준: 문제

3078번: 좋은 친구

처음에 보면 매우 간단한 문제로 보이나, 생각보다 메모리와 제한 시간이 빡빡해서 알고리즘을 여러 번 바꾸어가며 코드를 작성해야 했다. 

 

1. 반복문

첫 번째로 시도한 방법은 정말 단순한 방식으로 시간복잡도가 최악의 경우 O(N^2)가 되는 반복문을 사용하였다. 쉬운 만큼 디버깅도 필요없이 단번에 작성해냈으나, 바로 시간 초과를 당했다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> students;
int len[20];
int main(void){
    int n, k;
    string student;
    int answer = 0;
    cin >> n >> k;
    for(int i = 0;i < n;i++){
        cin >> student;
        students.push_back(student.length());
    }
    for(int i = 1;i < n;i++){
        int out = i - k - 1;
        if(out >= 0) len[students[out]]--;
        int in = i - 1;
        len[students[in]]++;
        answer += len[students[i]];
    }
    cout << answer;
}

 

2. 슬라이딩 윈도우

어떻게 하면 효율을 올릴 수 있을지 고민하던 찰나 하나의 Stream을 떠올렸다. 주어진 k의 크기만한 스트림에 데이터를 저장하고 있다가, 범위를 벗어나는 숫자는 스트림에서 빼고, 새로 들어오는 숫자를 스트림에 넣는 방식으로 불필요한 탐색 횟수를 극적으로 줄이고자 하였다. 하지만 바로 새로운 고민이 생겼다. 각 등수에 있는 학생 이름의 길이는 다른데, 매 학생마다 스트림 안의 학생 이름 길이를 비교하면 어차피 시간 복잡도가 1번과 동일해진다는 것이 문제였다.

 

이러한 문제를 단 하나의 배열로 개선해낼 수 있었다. 바로 학생 길이별로 현재 스트림 안에 있는 학생의 수를 카운트하면 된다. 단 하나의 배열로 극강의 효율을 낼 수 있다. 이를 len배열로 선언하고 활용하였다. 이는 앞서서 풀었던 문제와 상당히 유사하니 비교해보면 좋을 것 같다.

2021.10.08 - [TIL💡/Algorithms] - [백준] 2531 회전초밥

[백준] 2531 회전초밥

그런데 이렇게 풀어도 이번에는 메모리 초과가 발생했다..

 

3. Queue

여기서 어떻게 메모리를 더 줄이나 고민을 했는데, 이미 구간이 끝난 학생들의 값을 벡터에서 지우지 않고 가지고 있어서 발생했던 문제였다. 그래서 구간을 이미 지난 값은 배열에서 제외하고 새로운 값을 추가하기 쉽게 vector을 queue로 바꾸어주고 코드를 작성했더니 드디어 성공할 수 있었다. 그리고 혹시 몰라서 입력받는 값도 따로 배열에 저장해두지 않고 입력받자마자 Queue에 저장하는 등 자료구조로 Queue만을 활용하였다.

#include <iostream>
#include <queue>
using namespace std;
queue<int> students;
int len[20];
int main(void){
    int n, k;
    int out;
    string student;
    long long answer = 0;
    cin >> n >> k;
    for(int i = 0;i < n;i++){
        cin >> student;
        if(students.size() > k) {
            out = students.front();
            len[out]--;
            students.pop();
        }
        answer += len[student.length()];
        len[student.length()]++;
        students.push(student.length());
    }
    cout << answer;
}