[Programmers Level1] 숫자 짝꿍(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

프로그래머스

 

 

[문제 설명]

 

 

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.

예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.

 

 

[제한 사항]

 

 

• 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
• X, Y는 0으로 시작하지 않습니다.
• X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

 

 

[입출력 예]

 

 

X	Y	result
"100"	"2345"	"-1"
"100"	"203045"	"0"
"100"	"123450"	"10"
"12321"	"42531"	"321"
"5525"	"1255"	"552"

 

 

[입출력 예 설명]

 

 

입출력 예 #1

• X, Y의 짝꿍은 존재하지 않습니다. 따라서 "-1"을 return합니다.

입출력 예 #2

• X, Y의 공통된 숫자는 0으로만 구성되어 있기 때문에, 두 수의 짝꿍은 정수 0입니다. 따라서 "0"을 return합니다.

입출력 예 #3

• X, Y의 짝꿍은 10이므로, "10"을 return합니다.

입출력 예 #4

• X, Y의 짝꿍은 321입니다. 따라서 "321"을 return합니다.

입출력 예 #5

• 지문에 설명된 예시와 같습니다.

 

 

[문제 풀이]

 

회사를 다니면서 블로그 글을 쓰기란 쉽지가 않다.

그래도 주말에 일이 없다면 공부한 내용을 블로그에 적어보려한다. 

 

문제를 보고 이 문제의 경우 탐색을 이용하여 풀어야겠다고 생각을 했다.

 

처음 코드를 작성했을 땐

 

1. 주어진 자료형 string에서 find함수를 사용하여 문자를 찾기
2. 찾았다면 해당 인덱스의 문자를 공백으로 변경
3. 가장 큰 정수를 만들기 위해 sort 함수를 사용하여 내림차순 정렬하여 리턴

 

하지만 테스트케이스 11번 ~ 15번에서 시간초과가 발생했다.

 

그래서 시간 초과를 줄이기 위해 탐색에 유리한 자료형인 map으로 변경했다.

그리고 내가 생각한 알고리즘을  입출력 예시5 string X = "5525", string Y = "1255"를 설명해보려한다.

 

1. string X = "5525" 를 map<char, int> m 에 셋팅한다.

➜ 여기서 char은 문자, int는 문자의 개수이다.

 

 

2. map에 string Y의 문자가 있는지 찾는다.

➜ 문자를 찾았고 문자의 개수가 0보다 크다면

     문자에 해당하는 개수를 1 감소시키고 string 변수에 찾은 문자를 추가해준다.

 

string Y = "1255"

첫번째 문자 '1'일 때 map에서 1을 찾을 수 없으므로 패스

 

두번째 문자 '2'일 때 map에서 2를 찾을 수 있고 문자의 개수가 0보다 크기 때문에

문자에 해당하는 개수를 1 감소시키고 string 변수에 찾은 문자('2')를 추가해준다.

 

세번째 문자 '5'일 때 map에서 5를 찾을 수 있고 문자의 개수가 0보다 크기 때문에

문자에 해당하는 개수를 1 감소시키고 string 변수에 찾은 문자('5')를 추가해준다.

 

네번째 문자 '5'일 때 map에서 5를 찾을 수 있고 문자의 개수가 0보다 크기 때문에

문자에 해당하는 개수를 1 감소시키고 string 변수에 찾은 문자('5')를 추가해준다.

 

더이상 짝을 지을 문자가 없기 때문에 종료한다.

 

 

3. 가장 큰 값을 리턴하기 위해 sort함수를 이용하여 내림차순 정렬한다.

➜ answer 변수는 552로 정렬이 되고 해당 string answer 변수를 리턴하면 된다.

 

 

4. 예외 처리

서로 짝이 안 맞는 값이 전달인자로 주어진다면 answer는 빈 상태로 존재할 것이다.

그래서 answer가 비어있다면 바로 "-1"로 리턴하도록 한다.

 

그리고 2개의 전달인자를 짝 지었을 때 공통된 숫자가 0뿐이고 0이 여러개 존재할 수 있다.

그래서 sort함수를 사용 후 0번째 인덱스를 확인했을 때 '0'인 경우엔 바로 "0"을 리턴하도록 한다.   

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;

map<char, int> m;

void setMap(string X) {
    int gXlength = X.length();
    for(int i = 0; i < gXlength; ++i) {
        if(m.empty()) {
           m[X[i]] = 1;
        } else {
            if(m.find(X[i]) != m.end()) {
                m[X[i]] += 1;
            } else {
                m[X[i]] = 1;
            }
        }
    }
}

string solution(string X, string Y) {
    string answer = "";
    setMap(X);
    int gYlength = Y.length();
    for(int i = 0; i < Y.length(); ++i) {
        auto result = m.find(Y[i]);
        if(result != m.end()) {
            if(result->second > 0) {
                m[Y[i]] -= 1;
                answer += Y[i];
            }
        }
    }

    sort(answer.begin(), answer.end(), greater<char>());
    if(answer.empty()) return "-1";
    else {
        if(answer[0] == '0') return "0";
    }
    
    return answer;
}