문제
문제 해석
1. 주어진 문자열에서 Pair(쌍)을 이루는 숫자를 찾는다.
2. 찾아낸 숫자들을 조합하여 가장 큰 숫자를 문자열로 바꿔 반환한다.
코드
성공한 코드
더보기
#include <string>
#include <algorithm>
#include <map>
using namespace std;
string solution(string X, string Y) {
// X, Y의 각 숫자에 해당하는 문자 갯수를 찾아낸다
map<char, int> XMap;
map<char, int> YMap;
for(char CH : X) XMap[CH]++;
for(char CH : Y) YMap[CH]++;
string answer;
// 문자의 키 값은 '0'~'9'인데, Pair를 이루려면 해당 키에 해당하는 값이 작은 쪽에 제한이 걸린다.
// 가장 큰 수를 만들어야 하므로 '9'부터 짝궁의 갯수를 검사하여 숫자 문자열을 만들어준다.
for(char NUM = '9'; NUM >= '0'; --NUM)
{
int Count = min(XMap[NUM], YMap[NUM]);
// Count의 갯수에 따라 반복하여 숫자를 붙여준다.
for(int ITER = 0; ITER < Count; ++ITER)
{
answer += char(NUM);
}
}
// 예외처리
if(answer.empty())
{
answer = "-1";
}
else if(answer[0] == '0')
{
answer = "0";
}
return answer;
}실패한 코드
1. 제한 조건(숫자의 자릿수가 최대 3,000,000)을 지키지 않아 케이스에서 Runtime error 발생.
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
string solution(string X, string Y) {
// 공통되는 수를 찾는 방법
// 1. X의 원소 하나하나를 맵에 넣고
// 2. Y의 원소가 넣은 어딘가에 존재하면 짝궁 배열에 넣어준다.
map<char, int> XMap;
for(char ch : X)
{
XMap[ch]++;
}
vector<char> PairVector;
for(char ch : Y)
{
// 맵에 해당 값을 키로 같는 값이 0보다 크면 존재하는 것이므로
if(XMap[ch] > 0)
{
// 다음 검사를 위해 값을 감소시키고
XMap[ch]--;
// 짝궁 배열에 넣어준다.
PairVector.push_back(ch);
}
}
// -. 짝궁 배열에 원소가 없다면 -1을 바로 반환한다.
string answer = "";
if(PairVector.size() == 0)
{
return string("-1");
}
// 가장 큰 수를 찾는 방법
// 1. 짝궁 배열을 정렬해준다.
// 2. 조합을 이용해서 가장 큰 수를 찾는다.
sort(PairVector.begin(), PairVector.end());
// 자릿수를 고려해 여유롭게 long long으로 처리
long long MaxNumber = 0;
string PermuteSTR;
do{
PermuteSTR = string();
// 조합으로 문자열 생성
for(char ch : PairVector)
{
PermuteSTR += ch;
}
// 자릿수를 고려해 long long으로 변환해서 비교
if(MaxNumber < stoll(PermuteSTR))
{
MaxNumber = stoll(PermuteSTR);
}
}while(next_permutation(PairVector.begin(), PairVector.end()));
// 최댓값을 문자열로 변환
answer = to_string(MaxNumber);
return answer;
}2. 케이스에서 시간 초과 발생.
더보기
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
string solution(string X, string Y) {
// 공통되는 수를 찾는 방법
// 1. X의 원소 하나하나를 맵에 넣고
// 2. Y의 원소가 넣은 어딘가에 존재하면 짝궁 배열에 넣어준다.
map<char, int> XMap;
for(char ch : X)
{
XMap[ch]++;
}
vector<char> PairVector;
for(char ch : Y)
{
// 맵에 해당 값을 키로 같는 값이 0보다 크면 존재하는 것이므로
if(XMap[ch] > 0)
{
// 다음 검사를 위해 값을 감소시키고
XMap[ch]--;
// 짝궁 배열에 넣어준다.
PairVector.push_back(ch);
}
}
// -. 짝궁 배열에 원소가 없다면 -1을 바로 반환한다.
string answer = "";
if(PairVector.size() == 0)
{
return string("-1");
}
// 가장 큰 수를 찾는 방법
// 1. 짝궁 배열을 정렬해준다.
// 2. 조합을 이용해서 가장 큰 수를 찾는다.
sort(PairVector.begin(), PairVector.end());
// 가장 큰 수를 찾는 방법
// 1. 조합으로 만들어낸 문자열의 길이가 이전값과 같은 경우, 앞에서부터 각 원소가 더 큰지 비교
// 2. 조합으로 만들어낸 문자열의 길이가 이전값보다 작은 경우, 이전값이 숫자변환 시 더 크다
// 3. 조합으로 만들어낸 문자열의 길이가 이전값보다 큰 경우, 만들어낸 문자열이 숫자변환 시 더 크다
string PermuteSTR;
string MaxSTR;
size_t PermuteSTRLength = 0;
size_t MaxSTRLength = 0;
do{
PermuteSTR = string();
// 조합으로 문자열 생성
for(char ch : PairVector)
{
PermuteSTR += ch;
}
PermuteSTRLength = PermuteSTR.length();
if(PermuteSTRLength == MaxSTRLength)
{
int Length = PermuteSTR.length();
if(PermuteSTR > MaxSTR)
{
MaxSTR = PermuteSTR;
MaxSTRLength = PermuteSTRLength;
}
}
else if(PermuteSTRLength > MaxSTRLength)
{
MaxSTR = PermuteSTR;
MaxSTRLength = PermuteSTRLength;
}
}while(next_permutation(PairVector.begin(), PairVector.end()));
// 최댓값을 문자열로 변환
answer = MaxSTR;
// 만약 answer가 0으로 시작한다면 예외처리
if(answer[0] == '0')
{
answer = "0";
}
return answer;
}다른 사람의 풀이
1. 풀이의 전체적인 흐름은 비슷하나, map을 사용하지 않고 정렬을 이용하여 index 기반으로 X,Y를 순회하여 품. 메모리를 아낄 수 있는 좋은 방법이라 생각된다.
2. map 대신 unordered_map을 사용했음.
회고
1. '입력으로 들어올 수 있는 숫자의 크기가 백만 단위면 O(N)에 근접할 수 있도록 풀어야 한다.'는 것을 다시 일깨워줬다. 반성해야할 포인트