백준 1759번 문제 바로가기

문제에 대한 첫 인상

단순히 모든 조합을 구하라고 했으면 실버 문제에 해당하겠지만, 자음/모음 갯수를 고려해주는 것이 은근 까다로워서 골드 등급을 부여해준 듯 하다. 문제를 읽고 나서 두 가지 방법이 생각났다. 1) permutation 라이브러리를 사용한다. 2) DFS로 풀어낸다. 두 경우 모두 모든 경우를 커버해야하기 때문에 결국엔 bruteforce로 풀어내야 한다. 라이브러리의 사용법을 이미 알고 있어서 간단히 이용할 수 있는 permutation 라이브러리를 이용했다.

Python 풀이

import itertools

# input
l,c=map(int, input().split())
chars=list(map(str, input().split()))

# examples
words=itertools.combinations(sorted(chars), l)

# 조건 확인
def check(word):
    vowels = ['a','e','i','o','u']
    n = 0 # 모음 갯수
    m = 0 # 자음 갯수
    for w in word:
        if w in vowels:
            n += 1
        else:
            m += 1
    return (n, m)

answer = []
for word in words:
    nm = check(word)
    if nm[0]>=1 and nm[1]>=2:
        answer.append(''.join(word))

# output
for ans in sorted(answer):
    print(ans)

C++ 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    // input
    int l, c;
    cin >> l >> c;
    vector<string> chars(c);
    for (int i=0; i<c; i++){
        cin >> chars[i];
    }
    sort(chars.begin(), chars.end());
    vector<string> answer;
    
    // permutation
    vector<bool> vec(chars.size()-l, false);
    vec.insert(vec.end(), l, true);
    string vowels = "aeiou";
    
    do {
        string temp = "";
        int n=0, m=0; // n 모음갯수, m 자음갯수
        for (int i=0; i<chars.size(); i++){
            if (vec[i]){
                temp += chars[i];    
                if (vowels.find(chars[i]) != string::npos){
                    n++;
                } else{
                    m++;
                }
            }
        }
        if (n>=1 && m>=2){
            answer.push_back(temp);    
        }
    } while (next_permutation(vec.begin(), vec.end()));
    
    // output
    sort(answer.begin(), answer.end());
    for (string ans: answer){
        cout << ans << endl;
    }

    return 0;
}

풀어내고 보니까 Python이 확실히 코드가 깔끔하긴 하다. 그렇지만 메모리 사용량과 시간을 보면 C++의 압승

References