[Baekjoon] 15649번 N과 M (1).cpp

[백준] 15649번 N과 M (1) 문제 링크

예전에 작성했던 dfs로 순열 구하기과 같은 로직으로 이루어져 있다. 대신 이번 문제를 굳이 리뷰하는 이유는 입출력으로 인한 효율성 차이를 알아냈음에 의의를 두기 때문이다.

· 원인

cpp에서 제공하는 iostream 헤더와 c에서 사용하는 stdio.h 헤더는 각각 다른 입출력 형식을 가진다. iostream은 cin으로 입력을 받고 cout으로 출력하며, stdio.h는 scanf로 입력을 받고 printf로 출력한다.

물론 iostream에서도 scanf, printf를 지원하지만, 두 계열의 함수 중 어떤 것이 실행시간 측면에서 효율적인지 차이가 분명 존재하고, 필자는 scanf/printf가 cin/cout보다 적은 시간에 실행되는 것으로 알고 있었다. 하지만 코드를 제출하고 표시된 실행 시간은 무려 36ms였다.

해당 문제의 상위권은 겨우 4ms의 실행 시간을 가지는 것에 비해 터무니없이 느린 코드였다. 하지만 로직 자체의 차이는 없어 보였고, 유일한 차이라면 자료형의 차이와 입출력의 차이였다.

· cin / scanf

cpp의 입출력과 c의 입출력은 2배 이상의 속도 차이가 난다. 물론 cpp의 입출력이 느리다. 그 이유는 기본적으로 cpp의 입출력과 c의 입출력이 같은 버퍼를 공유하기 때문인데, cpp가 c와 같은 입출력 버퍼에 접근하기 위해 여러 버퍼를 거치기 때문에 시간이 느려지는 것이다.

cpp의 입출력 cin/cout이 독립된 버퍼를 가지게 하면 입출력 속도가 c의 입출력에 비등하게, 어쩌면 더 빨라지게 된다. 이를 위해선 다음 코드를 main 함수 상단에 추가해줄 필요가 있다.

ios::sync_with_stdio(false); 
cin.tie(NULL); 
cout.tie(NULL);

실제로 이 방법을 입력 처리가 많은 1707번 이분 그래프 문제에 적용해보니 다음과 같은 처리 시간 차이를 확인할 수 있었다. 위에서부터

1. cin
2. sync_with_stdio과 tie(null)을 추가한 cin
3. scanf

로 입력을 받은 코드이다.

확실히 차이가 있음을 확인할 수 있다.

· 정답 출력 방식

해당 문제에선 만들어진 순열을 공백으로 구분하여 출력하게 하였다.

3 2
1 2
1 3
2 1
2 3
3 1
3 2

와 같이 출력되는데, 이를 위해 배열에 반복문을 이용해 인덱스별로 출력을 해주었다.

for(int idx = 1; idx <= m; idx++){
	printf("%d ", nums[idx]);
}
printf("\n");

하지만 한 문자를 출력할 때마다 printf를 호출해야 하므로 실행 시간이 급격하게 늘어나는 것이다. 이를 위해 순열을 저장하는 배열을 int 형이 아닌 char로 바꾸고 숫자 사이사이에 공백 문자를 추가해 '문자열'로 만들었다.

문자열 출력을 위해선 출력 함수를 한 번만 호출하면 되므로 전체 실행 시간이 대폭 감소하였고, 다른 사람들과 같은 4ms의 문제 풀이 시간에 도달하였다.

아래는 코드 전문이다.

#include <iostream>
#include <vector>

int n, m;
char nums[18];
bool visit[9];

void permutation(int count){
    if(count == m){
        std::cout << nums <<'\n';
        return;
    }
    for(int index = 1; index <= n; index++){
        if(visit[index] != 1){
            nums[count * 2] = index + '0';
            visit[index] = 1;
            permutation(count + 1);
            visit[index] = 0;
        }
    }
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n >> m;
    for(int index = 0; index < m * 2; index++){
        nums[index] = ' ';
    }

    permutation(0);
}