[백준/C++] 6603 로또

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

 

문제 분석

확률과 통계에서 배웠던 조합 nCr을 구현하는 문제입니다.  로또 번호니까 여기서는 nC6으로 고정되어있는 상황입니다. 재귀를 통해 Brute force를 하면 단순하게 구할 수 있을 것 같다고 생각을 했습니다.

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

void pick_number(vector<int> &v, vector<int> &picked, int start, int rest_pick){
    if(rest_pick == 0){
        for(int i = 0; i < picked.size(); ++i){
            cout << picked[i] << " ";
        }
        cout << endl;
        return;
    }

    for (int i = start; i < v.size(); ++i){
        picked.push_back(v[i]);
        pick_number(v, picked, i + 1, rest_pick - 1);
        picked.pop_back();
    }
}

int main(){
    int n;

    while(true){
        cin >> n;

        if(n == 0) break;

        vector<int> v(n);
        for(int i = 0; i < n; ++i){
            cin >> v[i];
        }

        vector<int> picked;
        pick_number(v, picked, 0, 6);

        cout << endl;
    }
    return 0;
}

 

처음에 start가 0부터 시작하니까 첫 번째 자리에 v[0]이 들어간 채로 그 다음 두 번째 자리를 고르는 pick_number(v, picked, i + 1, rest_pick -1);을 시작합니다. 재귀적으로 이를 반복하면 첫 번째 자리에 v[0] 들어가는 경우 중 6자리가 채워질 수 있는 모든 경우의 수는 화면에 출력이 되고 그 다음에 picked.pop_back() 부분으로 돌아와서 첫 번째 자리에서 v[0]을 제거합니다. 그렇게 하여 다음 반복에서 v[1]이 첫 번째 자리에 오면서 6자리를 채울 수 있는 경우를 모두 조사하고 출력합니다. 이런 식으로 반복하면 모든 경우의 수를 출력할 수 있습니다. 조합은 순서가 상관이 없기때문에 ({1, 2}와 {2, 1}는 같은 거라고 판단) v의 앞부터 차례대로 채우면서 순서를 일정하게 유지시킵니다.

 

#include <iostream>
#include <vector>

using namespace std;

void pick_number(vector<int> &v, vector<int> &picked, int start, int rest_pick){
    if(rest_pick == 0){
        for(int i = 0; i < picked.size(); ++i){
            cout << picked[i] << " ";
        }
        cout << endl;
        return;
    }

    if(v.size() - start < rest_pick) return;
    
    for (int i = start; i < v.size(); ++i){
        picked.push_back(v[i]);
        pick_number(v, picked, i + 1, rest_pick - 1);
        picked.pop_back();
    }
}
int main(){
    int n;

    while(true){
        cin >> n;

        if(n == 0) break;

        vector<int> v(n);
        for(int i = 0; i < n; ++i){
            cin >> v[i];
        }

        vector<int> picked;
        pick_number(v, picked, 0, 6);

        cout << endl;
    }
    return 0;
}

 

전체를 다 계산하지 않아도 아직 선택하지 않은 숫자의 수가 선택할 수 있는 수들보다 많다면 불가능한 조합이기 때문에 이를 고려하여 불필요한 반복을 줄이도록 하였습니다. 하지만 샘플 데이터에서 제공하는 배열의 길이가 많지 않고, 선택하는 개수의 길이도 6개로 짧기 때문에 현재 이 코드로 제출한 결과 48ms로 기존의 44ms 보다 증가하였습니다. 간단한 상황에서는 매 함수 호출마다 if문을 계산하는 것이 더 비효율적인 것 같습니다.

 

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

void pick_number(vector<int> &v, vector<int> &picked, int start, int rest_pick, ostringstream &output) {
    if (rest_pick == 0) {
        for (int i = 0; i < picked.size(); ++i) {
            output << picked[i] << " ";
        }
        output << "\n";
        return;
    }

    if (v.size() - start < rest_pick) return;

    for (int i = start; i < v.size(); ++i) {
        picked.push_back(v[i]);
        pick_number(v, picked, i + 1, rest_pick - 1, output);
        picked.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;

    while (true) {
        cin >> n;

        if (n == 0) break;

        vector<int> v(n);
        for (int i = 0; i < n; ++i) {
            cin >> v[i];
        }

        vector<int> picked;
        ostringstream output;
        pick_number(v, picked, 0, 6, output);
        
        cout << output.str();
        cout << endl;
    }

    return 0;
}

 

입출력 최적화를 하였더니 0ms로 줄어들었습니다. 

맨 아래부터 게시글의 첫 번째 코드

 

ostringstream의 주요 기능

1. 버퍼에 문자열 쓰기:
   • ostringstream 객체는 내부적으로 문자열을 저장할 수 있는 버퍼를 유지
   • << 연산자를 사용하여 데이터를 스트림에 쓰면 이를 메모리 버퍼에 저장
2. 버퍼 내용 읽기:
   • str() 멤버 함수를 호출하여 버퍼에 저장된 문자열을 한 번에 읽어옴
3. 많은 양의 데이터를 출력할 때 ostringstream를 사용하면 여러 번의 출력보다 한 번에 출력하는 것이 효율적(특히 I/O가 느린 경우)