모빌 이진수( BOJ 2471 )

2471. 모빌 이진수 : https://www.acmicpc.net/problem/2471

2471번: 모빌 이진수

 

문제 파악하기

• 0과 1로 이루어진 이진수가 주어집니다.
• 괄호 안의 값은 회전할 수 있으며, 회전 시 괄호 안의 숫자들은 뒤집히게 됩니다.
• 주어진 이진수로 만들 숫자 중 K번째 숫자를 찾아야 합니다.
• 입력되는 숫자와 괄호의 길이는 최대 200개이기 때문에 문자열로 입력을 받아야 합니다.
• 메모리의 제한 때문에 만들 수 있는 모든 문자열을 저장할 수는 없습니다.
• 그럼 메모리를 절약할 수 있는 방법은 어떤 것이 있을까요?

 

문제 해결하기

• 우선순위 큐(priority_queue)를 사용하면 메모리를 절약할 수 있습니다.
• 우선순위 큐를 사용하면 가장 높은 우선순위를 가진 문자열 혹은 이진수가 나오게 됩니다.
  [ 우선순위 : 길이 >> 괄호 >> 0 >> 1 ]
• 문자열이 나온 경우 괄호를 왼쪽에서부터 하나씩 제거하고 나올 수 있는 이진수를 모두 우선순위 큐에 저장합니다.
  >> 기존 순서를 유지한 이진수 / 제거한 괄호 안의 값을 회전시킨 이진수
• 큐에 저장할 때에는 해싱(map)을 사용해 중복된 문자열이 나온 경우 입력을 제거해야 합니다.
• 이진수가 나온 경우, K의 값을 감소시킵니다. 만약 K의 값이 0이 된다면 탐색을 종료합니다.

 

소스코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
 
string inp;
int k, len;
 
string top;
map< string, int > check;
priority_queue< string, vector< string >, greater< string > > pq;
 
 
char convert(char c) {
    if(c == '(') return ')';
    else if(c == ')') return '(';
    else return c;
}
 
void makeNum(string s) {
    int cnt=0;
    string str;
    int st, ed, f=0;
 
    // 가장 먼저 시작하는 괄호만 제거해서 넣기
    str.clear();
    for(char c:s) {
        // 제거할 괄호를 찾은 후에는 그대로 복사
        if(f) str.push_back(c);
        else {
            if (c == '(') {
                if (cnt > 0) str.push_back(c);
                cnt++;
 
                // 가장 왼쪽 괄호의 시작부분
                if (cnt == 1) st = str.length();
            }
 
            else if (c == ')') {
                // 가장 왼쪽 괄호의 종료부분
                if (cnt == 1) {
                    ed = str.length() - 1;
                    f = 1;
                }
 
                cnt--;
                if (cnt > 0) str.push_back(c);
            }
 
            else {
                str.push_back(c);
            }
        }
    }
 
    // 기존 문자열 중복 확인하기
    if(!check[str]) {
        pq.push(str);
        check[str] = 1;
    }
 
    // 가장 왼쪽에 위치한 괄호 회전시킨 후 저장하기
    while(st <= ed) {
        // 괄호인 경우, 방향을 바꿔주어야 함 >> convert함수
        char tmp = convert(str[st]);
        str[st] = convert(str[ed]);
        str[ed] = tmp;
 
        st++; ed--;
    }
 
    // 회전한 문자열 중복 확인하기
    if (!check[str]) {
        pq.push(str);
        check[str] = 1;
    }
}
 
int main() {
    // 입력
    cin >> inp;
    cin >> k;
 
    // 숫자 개수 세기
    for(char c:inp) {
        if(c=='0' or c=='1') len++;
    }
 
    // 우선순위 큐를 사용한 탐색
    pq.push(inp);
    while(!pq.empty() and k>0) {
        top = pq.top();
        pq.pop();
 
        // 숫자인 경우에만 K값 감소
        if(top.length() == len) k--;
        else makeNum(top);
 
    }
 
    // 출력
    if(k == 0) cout << top;
    else cout << "NO";
}