[백준/C++] N과 M(5) / 시간초과 이유

---

백트래킹 문제들을 풀다보니 N과 M 시리즈들을 많이 풀게되었다. 풀어 본 사람들은 알겠지만 이 시리즈들은 문제가 거의 비슷비슷하다. 전의 문제들은 숫자가 오름차순으로 고정되어 있어서 따로 숫자를 입력 받을 필요가 없었다. 하지만 이번에는 임의의 숫자를 입력 받아서 수열로 출력해주어야 했다.

그렇기에 전에 코드들에서 vector만 추가해주었다.

 

풀이 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 8
using namespace std;

int n, m;
int arr[MAX] = { 0, };
bool visited[MAX] = { 0, };
vector<int> v;

void dfs(int cnt)
{
    if (cnt == m) {
        for (int i = 0; i < m ; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 0; i < v.size(); i++) {
        if (!visited[i]) {
            arr[cnt] = v[i];
            visited[i] = true;
            dfs(cnt + 1);
            visited[i] = false;
        }
    }

}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    v.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    dfs(0);
}

---

여기서 잠깐!!

 

 

테스트 케이스도 모두 정상적으로 출력되고 모두 맞게 코드를 짠거 같은데 왜 시간 초과가 뜨지?... 해서 무지성으로 코드를 조금씩 계속 수정해봤고 결과는 마찬가지로 시간초과였다. 무엇이 문제일까 찾아보던 도중 바로 endl이 문제라는 것을 알았다.

endl 함수는 개행을 해주는 것 뿐만 아니라 내부 버퍼를 비워주는 역할도 함께하기 때문에 매우 느리다고 한다.

 

그렇기에 알고리즘 문제 푸는데에 있어서 C++을 사용한다면 입출력은 C스타일로 지향하는것이 맞다고 생각한다.