Sho1007

MMORPG 클라이언트 개발자 지망생

1 minute read

556. Next Greater Element III / c++ / Medium / 18분

문제 및 코드

#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;

int target, answer;
vector<int> numberVector;
unordered_set<int> resultSet;
unsigned long long result;
unsigned long long intLimit = 2'147'483'647;

void BackTracking()
{
    if (numberVector.size() == 0)
    {
        if (result <= intLimit && result > target)
        {
            resultSet.insert(result);
        }

        return;
    }

    for (int i = 0; i < numberVector.size(); ++i)
    {
        result = result * 10 + numberVector[i];
        numberVector.erase(numberVector.begin() + i);
        BackTracking();
        numberVector.insert(numberVector.begin() + i, result % 10);
        result /= 10;
    }
}

class Solution {
public:
    int nextGreaterElement(int n) {
        target = n;
        answer = -1;
        result = 0;
        numberVector.clear();
        resultSet.clear();

        string nString = to_string(n);
        for (int i = 0; i < nString.length(); ++i)
        {
            numberVector.push_back(nString[i] - '0');
        }

        BackTracking();

        if (resultSet.size() == 0) return -1;

        vector<int> resultVector(resultSet.begin(), resultSet.end());
        sort(resultVector.begin(), resultVector.end());

        return resultVector[0];
    }
};

접근 방식

문자열 / 백트래킹

  1. n과 같은 숫자로 만들어진 수 중, n보다 크고, 그 중에서 가장 작은 수를 반환하는 문제
  2. 1번 조건이 약간 이상하게 쓰여져있지만, 해석해보면 n과 같은 숫자의 조합으로 만들어진 수 중에서, n 바로 다음으로 큰 수를 구하는 문제였다.
  3. 숫자를 각 자리마다 접근하기 위해서 to_string으로 문자열로 바꿔서 접근해줬다.
  4. 모든 자리를 numberVector에 담아준다.
  5. 그 후 백트래킹을 하면서 numberVector에 있는 수로 만들 수 있는 모든 수를 구해준다.
  6. 숫자가 다 만들어지면, 해당 숫자가 n보다 크고, intLimit(32bit int의 최대 범위) 보다 작거나 같은지 체크한 뒤 resultSet에 담아준다. (중복을 피하기 위해서 unordered_set을 이용)
  7. 위의 과정이 끝나면, resultSet을 다시 resultVector에 담는다. (만약 resultSet이 비었다면, 이 시점에서 -1을 반환)
  8. resultVector를 정렬 후 0번째 숫자 (즉, intLimit보다 작거나 같고, n보다 큰 수 중 가장 작은 수)를 반환한다.

생각해 볼 점

  1. 백트래킹과 set 그리고 정렬을 이용해서 풆 수 있는 문제였다.
  2. 32-bit int 라고 해서 unsigned int 는 아니겠지 하고 int의 최대 범위를 사용했는데 맞았다.
  3. 조합할 수 있는 수는, 앞에 9가 오게 되고 10자리 인 경우 int의 최대 범위르 넘어갈 수 있으므로, 통 크게 unsigned long long 으로 잡아줬다. (n이 양의 정수이므로 음수는 가정하지 않았다)
  4. leetcode의 경우 전역변수를 공유해서 테스트케이스들을 처리하다보니, 전역변수를 선언하고 함수 안에서 초기화해주는 방식으로 사용했다. (이번엔 백트래킹에 사용되는 전역변수가 좀 많았다.)

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL

You may also enjoy