[프로그래머스] 2018 카카오 코딩테스트 [3차]압축 (Lv. 2) C++ 풀이

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/17684

분류

구현, 해시, 문자열

시도한 방법

초기에 모든 알파벳을 인덱스에 순차대로 담아 사전을 초기화한다.

이후 버퍼에 대상 문자열의 한 글자씩 담고, 사전에 없을 경우 색인에 추가하며 버퍼를 flush하며 대상 문자열의 인덱스를 한 칸씩 밀어준다.

위 과정을 마치고 나면 answer에 방금 검색된 색인을 담아 전달한다.

 

방향성 자체는 맞았지만, GPT 리팩토링 결과 몇 군데 지적받았다. 

1. 색인에 등록할 때는 탐색의 용이함을 확보하기 위해 한 글자씩 등록된 부분에 vector로 색인을 추가했지만, map 컨테이너에 내장된 find 함수를 사용하므로 굳이 리스트로 구현할 필요가 없었다.
   map<string, vector<int>> -> map<string, int>로 수정.
2. 전부 대문자로 변환한 후에 연산을 수행하고자 toupper 함수를 사용했다. 하지만 입력 형식 전제조건에서도 대문자로만 주어진다고 명시되어 있으며, for문을 수행할 때 it는 복사본이기 때문에 실제 msg에 내용이 반영되지 않는다.
   for(auto it : msg) -> for(auto& it : msg) 로 수정했지만, 실제론 필요 없음.

결과 코드

직접 작성해서 사용한 코드는 이와 같다.

#include <string>
#include <vector>
#include <map>
#include <cctype>

using namespace std;

vector<int> solution(string msg) {
	vector<int> answer;
	map<string, vector<int>> dictionary;
	int i;
	for (i = 1; i <= 26; i++)
	{
		string buffer(1, 'A' + i - 1);
		dictionary[buffer].push_back(i);
	}
	
	for (auto it : msg)
		it = toupper(static_cast<unsigned char>(it));
	
	string::iterator index = msg.begin();
	while (index != msg.end())
	{
		string temp = "";
		temp += *index;
		int addedIndex = 0;

		bool isFind = (dictionary.find(temp) != dictionary.end());
		bool isEnd = false;
		while (isFind)
		{
			if (index == msg.end() - 1)
			{
				isEnd = true;
				break;
			}

			temp += *(++index);
			isFind = (dictionary.find(temp) != dictionary.end());
		}

		if (!isEnd)
		{
			string findTarget = temp;
			dictionary[temp].push_back(i++);
			findTarget.pop_back();
			map<string, vector<int>>::iterator indexLocation = dictionary.find(findTarget);
			answer.push_back(indexLocation->second[static_cast<int>(indexLocation->second.size() - 1)]);
		}
		else
		{
			map<string, vector<int>>::iterator indexLocation = dictionary.find(temp);
			answer.push_back(indexLocation->second[static_cast<int>(indexLocation->second.size() - 1)]);
			index = msg.end();
		}
	}

	return answer;
}

 

GPT의 리팩토링을 거친 코드는 아래와 같다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> solution(string msg) {
    vector<int> answer;
    unordered_map<string, int> dictionary;

    // 1. 사전 초기화 (A~Z: 1~26)
    for (int i = 0; i < 26; ++i) {
        string ch(1, 'A' + i);
        dictionary[ch] = i + 1;
    }

    int nextIndex = 27; // 다음 등록할 사전 번호
    int i = 0;

    while (i < msg.size()) {
        string w = "";

        // 2. 가장 긴 w 찾기
        int j = i;
        while (j < msg.size()) {
            w += msg[j];
            if (dictionary.find(w) == dictionary.end()) {
                break;
            }
            ++j;
        }

        // 3. 결과에 w의 인덱스 추가
        string known = w;
        if (dictionary.find(w) == dictionary.end()) {
            known.pop_back();  // w = w + c 였으므로, c 제거
        }

        answer.push_back(dictionary[known]);

        // 4. 사전에 w+c 추가
        if (j < msg.size()) {
            dictionary[w] = nextIndex++;
        }

        i += known.size();  // 다음 탐색 위치로 이동
    }

    return answer;
}

 

앞서 작성한 변경내용 외에도, 출력 인덱스를 처리하는 과정의 편의성이나 반복문 제어 방식에서 차이가 발생한다.

기존 방식의 경우 이중 루프를 탐색하고 캐스팅을 하는 등 비효율적인 과정이 있다는 지적이 있었다.

실제로 아래 사진처럼 일부 결과에 한해 유의미한 차이가 발생했다.

좌측은 기존 코드, 우측은 GPT로 리팩토링한 코드의 실행 결과