BOJ 31911 - ChatGPT 만들기 (C++)

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

문제를 푼 날짜: 24. 06. 01.

#implementation #graphs #data_structures #string #hash_set

코드

#include <iostream>
#include <string>
using namespace std;

/*
A문자 다음에 B문자가 나오는 횟수
'-': 45, '[': 91, ']': 93, 'a': 97
*/
long long stats[29][29];

//각 문자 뒤에 언어모델이 생성하는 문자
char nextChar[29];

//생성한 문장
string message = "";

//반복부의 시작점 index
long long repeatStartIdx;

//생성된 문자열에 특정 문자가 있는지의 여부
bool isInChat[29];

//아스키코드 변환함수 ('-'는 0으로, []는 각각 1, 2, a~z는 3~28)
int charToNum(char ch);

//아스키코드 변환함수 (앞서 바꾼 숫자를 원래 문자대로)
char numToChar(int num);

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

    /*
    훈련 코퍼스 총 N개의 문장
    언어모델이 생성한 문자열의 K번째 문자부터 K+M-1번째 문자까지 출력
    */
    int N, M;
    long long K;

    string tmpword;

    cin >> N >> K >> M;


    //훈련 코퍼스를 입력받아 데이터를 내는 과정
    for(int i = 0; i < N; i++){
        cin >> tmpword;

        for(int j = 0; j < tmpword.length() - 1; j++){
            stats[charToNum(tmpword[j])][charToNum(tmpword[j+1])]++;
        }
    }

    //각 문자 뒤에 언어모델이 생성하는 문자가 무엇인지 판독
    for(int i = 0; i < 29; i++){
        int max_cnt = -1;
        char max_char;
        for(int j = 0; j < 29; j++){
            if(stats[i][j] > max_cnt){
                max_cnt = stats[i][j];
                max_char = numToChar(j);
            }
        }
        nextChar[i] = max_char;
    }

    //문장 생성
    for(int i = 0; i < 29; i++){
        isInChat[i] = false;
    }
    message += '[';
    isInChat[charToNum('[')] = true;
   
    while(1){
        //생성된 문장의 맨 끝 문자
        char end_of_message = *(message.end() - 1);
        int end_of_message_code = charToNum(end_of_message);

        if(nextChar[end_of_message_code] == ']'){
            isInChat[charToNum(']')] = true;
            message += ']';
            break;
        } else if(isInChat[charToNum(nextChar[end_of_message_code])] == true){
            repeatStartIdx = message.find(nextChar[end_of_message_code]);
            break;
        } else{
            isInChat[charToNum(nextChar[end_of_message_code])] = true;
            message += nextChar[end_of_message_code];
        }
    }

    //Case 1: 생성문장이 완결됨 (= ']'로 끝남)
    if(*(message.end() - 1) == ']'){
        for(long long i = K - 1; i < K + M - 1; i++){
            if(i >= message.length()){
                for(long long j = 0; j < K + M - 1 - i; j++){
                    cout << '.';
                }
                break;
            } else cout << message[i];
        }
    }

    //Case 2: 특정 문자열이 반복됨
    else{
        //반복파트의 길이
        long long repeatPartLength = message.length() - repeatStartIdx;

        for(long long i = K - 1; i < K + M - 1; i++){
            if(i < message.length()) cout << message[i];
            else cout << message[repeatStartIdx + ((i - message.length()) % repeatPartLength)];
        }
    }
    return 0;
}

int charToNum(char ch){
    if(ch == '-') return 0;
    else if(ch == '[') return 1;
    else if(ch == ']') return 2;
    else return int(ch - 94);
}

char numToChar(int num){
    if(num == 0) return '-';
    else if(num == 1) return '[';
    else if(num == 2) return ']';
    else return char(num + 94);
}

아이디어

1. 훈련 코퍼스를 입력받아 각 문자 뒤에 가장 많이 오는 문자가 무엇인지 구한다.
2. 모델이 생성하는 문장은 완결된 형태(Case 1; "[abcd]")이거나, 특정 부분이 무한히 반복되는 형태(Case 2; “[abcdbcd...")일 것이다.
3. Case 1의 경우 문제에서 요구하는 바와 같이 출력하고,
   Case 2의 경우 어떤 문자부터 반복되는 지 체크한 후 나머지 연산을 이용하여 문자열을 출력한다.

얻어갈 부분

1. K가 최대 10^18 이므로 아이디어 1에서 구한 결과를 이용해 문장을 naive하게 계속 생성하면 시간초과가 발생할 수밖에 없다. 따라서 생성되는 문장의 특정 부분이 계속 반복된다는 힌트를 얻었고(입출력 예제를 통해서도 힌트를 얻을 수 있었다), 나머지 연산 접근을 하였다.
   => 문제에서 주어지는 변수의 범위 및 시간 제한을 통해 힌트 얻기!

2. 처음에는 아이디어 1의 부분을 map을 이용해서 해결하려고 했으나, map을 이용한 접근이 복잡하여 이차원 배열을 이용하여 해결하였다.

3. 생성 문장 내에서 반복이 시작되는 부분을 찾기 위해서 string::find()을 활용하였다.

string::find()

• str.find("찾는 문자”)로 사용
• 찾는 문자가 첫 번째로 등장하는 인덱스를 반환
• 찾는 문자가 없을 경우 string::npos(쓰레기값) 반환