프로그래머스 숫자 짝꿍 C++

프로그래머스 : 숫자 짝꿍

프로그래머스

 

---

- 문제

 

 

    쉽게 말해 X와 Y에 공통으로 들어간 수를 모두 모아서 가장 큰 수 result를 만드는 문제다. X가 "1234"이고 Y가 "3456"이면 3이랑 4가 겹치고 3과 4를 이용해서 만들 수 있는 가장 큰 수는 43이므로

 

정답은 "43"이다.

---

- 풀이

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

using namespace std;

string solution(string X, string Y) {
    string answer = "";
    sort(X.rbegin(),X.rend());
    sort(Y.rbegin(),Y.rend());
    int xsize = X.size(), ysize = Y.size(), xidx = 0, yidx = 0;
    while(1){
        if(xidx == xsize || yidx == ysize)  break;
        if(X[xidx] == Y[yidx]){
            answer += X[xidx];
            xidx++;
            yidx++;
            
        }
        else if(X[xidx] < Y[yidx]){
            yidx++;
        }
        else{
            xidx++;
        }
    }
    if (answer.empty()) answer += "-1";
    if(answer[0] == '0'){
        answer.clear();
        answer += '0';
    }
    return answer;
}

 

1. X와 Y를 내림차순으로 정렬한다.

2. xidx와 yidx를 두어 X와 Y 문자열을 따로 관리한다.

 

---------------3 조건이 성립할때 까지 반복-----------------

3. xidx 혹은 yidx 둘 중 하나라도 X나 Y의 size보다 커지면 반복을 끝낸다.

4. X와 Y의 현재 값이 같으면 둘다 idx를 하나씩 증가시키고 정답에 그 값을 추가한다.

5. Y의 현재값이 X의 현재값보다 크면 Y만 증가

6. X의 현재값이 Y의 현재값보다 크면 X만 증가

----------------------------------------------------------------------

 

7. answer가 비어있으면 -1을 넣는다.

8. answer가 "0000"이런 수일수도 있으니 "0"으로 바꿔준다.

 

 

 

    

 

--- 정리 --- 

   X에 "5355" Y에 "35151"이 들어간다고 생각하자

1. 처럼 정렬하면 X = "5553", Y = "55311"

2. 이후에 반복문 돌리면

 

 

xidx = 0, yidx = 0      X[0] = "5", Y[0] = "5"이므로 4.

xidx = 1, yidx = 1      X[1] = "5", Y[1] = "5"이므로 4.

xidx = 2, yidx = 2      X[2] = "5", Y[2] = "3"이므로 6.

xidx = 3, yidx = 2      X[0] = "3", Y[0] = "3"이므로 4.

xidx = 4, yidx = 3      xidx == xsize 이므로 3.으로 끝!!!!

 

answer = "553"으로 끝난다.

---

- 기억할 것!

- X와 Y의 길이(자릿수)가 3,000,000까지 가능하므로 "000"을 "0"으로 바꾸기 위해

 

to_string(stoll(answer))

 

를 하면 오류가 난다.