[level 1] 숫자 짝꿍 - 131128

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

프로그래머스

 

---

설계

while문을 통해 X, Y의 입력값을 0~9로 쪼개서 각자 개수를 저장하고 9부터 answer에 짝을 맞춰 저장하고 return한다.

 

구현

#include <string>
#include <vector>
#include <algorithm>

using namespace std;


string solution(string X, string Y) {
    string answer = "";

    int longNum = X.size();

    vector<int> XNum = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    vector<int> YNum = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    if (X.size() < Y.size()) longNum = Y.size();

    sort(X.begin(), X.end(), greater<int>());
    sort(Y.begin(), Y.end(), greater<int>());



    int xLength = 0;
    int yLength = 0;
    char xCounter = '9';
    char yCounter = '9';

    while (xLength < X.length())
    {        
        if (xLength < X.length() && X[xLength] == xCounter)
        {
            XNum[xCounter - '0'] += 1;
            xLength++;
        }
        else
        {
            xCounter--;
        }
    }

    while (yLength < Y.length())
    {
        if (yLength < Y.length() && Y[yLength] == yCounter)
        {
            YNum[yCounter - '0'] += 1;
            yLength++;
        }
        else
        {
            yCounter--;
        }
    }


    int shortNum = 0;
    for (int i = 9; i >= 0; --i)
    {
        if (XNum[i] > 0 && YNum[i] > 0)
        {
            shortNum = YNum[i];

            if (XNum[i] < YNum[i])
            {
                shortNum = XNum[i];
            }

            for (int j = 0; j < shortNum; j++)
            {
                answer += ('0' + i);
            }
        }
    }

    if (answer == "")
    {
        return "-1";
    }
    
    if (answer[0] == '0')
    {
        return "0";
    }
    return answer;
}

 

리펙토링 코드

#include <string>
#include <vector>
#include <algorithm> // min, append 등을 사용하기 위해 포함

using namespace std;

string solution(string X, string Y) {
    string answer = "";

    // 1. 0~9까지 숫자의 개수를 세기 위한 벡터 (0으로 10칸 초기화)
    // 기존의 길게 나열한 {0,0,...} 방식을 깔끔하게 압축했습니다.
    vector<int> XNum(10, 0);
    vector<int> YNum(10, 0);

    // 2. 무거운 sort()와 복잡한 while문을 걷어내고,
    // 단순히 문자열을 한 번씩 순회하며 빈도수(개수)만 셉니다. (속도 비약적 상승!)
    for (char c : X) {
        XNum[c - '0']++;
    }
    for (char c : Y) {
        YNum[c - '0']++;
    }

    // 3. 9부터 0까지 공통으로 등장한 횟수 탐색
    for (int i = 9; i >= 0; --i) {
        // 두 배열 모두 숫자가 존재할 때만 처리 (사실 min()을 쓰면 이 if문도 없어도 되지만,
        // 직관적인 이해를 위해 사용자님의 로직을 유지했습니다)
        if (XNum[i] > 0 && YNum[i] > 0) {
            
            // XNum[i]와 YNum[i] 중 더 작은 값을 shortNum에 바로 저장합니다.
            int shortNum = min(XNum[i], YNum[i]);

            // for문으로 문자를 하나씩 더하는 대신, append로 한 번에 갖다 붙입니다.
            // 용법: answer.append(반복할 횟수, 붙일 문자);
            answer.append(shortNum, '0' + i);
        }
    }

    // 4. 예외 처리 (사용자님이 완벽하게 고쳐내신 부분!)
    if (answer == "") {
        return "-1";
    }
    
    // 오버플로우를 막는 환상적인 아이디어입니다.
    if (answer[0] == '0') {
        return "0";
    }
    
    return answer;
}

주요 리팩토링 포인트

1. 무거운 sort() 제거 및 빈도수 배열로 통폐합 (가장 중요!)
   • 사용자님의 while문 로직은 "정렬된 배열에서 특정 숫자(9~0)가 몇 개인지 세는 역할"을 하고 있습니다.
   • 하지만 길이가 최대 300만인 문자열을 sort()로 정렬하는 것은 시간이 굉장히 오래 걸립니다($O(N \log N)$).
   • 어차피 0~9의 '개수'만 필요하다면, 정렬할 필요 없이 **문자열을 한 번 쓱 훑으면서 개수만 세는 방식(for (char c : X))**이 압도적으로 빠르고 코드도 짧아집니다.
2. std::min 활용 (로직 압축)
   • XNum과 YNum 중 더 작은 값을 찾기 위해 작성하신 if 조건문은 C++ 표준 라이브러리의 min() 함수를 쓰면 한 줄로 깔끔하게 처리됩니다.
3. append()를 이용한 문자열 이어 붙이기
   • 공통된 개수(shortNum)만큼 for문을 돌며 answer += ('0' + i)를 하셨는데, string::append(개수, 문자) 함수를 쓰면 반복문 없이 한 방에 문자를 여러 개 이어 붙일 수 있어 속도도 빠르고 가독성도 좋아집니다.
4. 사용하지 않는 변수 제거
   • longNum 변수는 선언만 하시고 뒤에서 한 번도 사용하지 않으셨으므로 메모리 절약을 위해 과감히 지웠습니다. 벡터 초기화도 vector<int> XNum(10, 0);으로 짧게 줄일 수 있습니다.

---

회고

코드를 짜면서 일단 변수같은것들도 다 생성해두고 쓰다가 다하고 지우니까 코드가 더러워 진 것 같아서 처음부터 신중이 변수 선언을 하고 덱 압축에 신경써야 할 것 같다.