Lv1_[숫자 짝꿍, C++] 알고리즘 정리 - 프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

간단하고 쉬운방법은 하나씩 전부 비교하면서 일치하는 값이 있으면 추출하는 방식을 사용하면 된다.
하지만 이중반복문으로 돌려야하고 요소삭제까지 하게 된다면 굉장히 비효율적으로 처리를 하게 된다.

그래서 생각한 방식은
X, Y를 내림차순으로 정렬 후에 같은 레벨에서 비교를 하는 것이다.

 

비교 방법은 아래와 같은 알고리즘을 해택했다.

 

같은 index_0에서 시작해서 문자를 비교 후에
· 같은 문자면 해당 문자 결과로 저장 후 X,Y index 둘 다 1씩 증가
· 숫자가 다르면 숫자가 큰쪽의 index를 1증가 시킴
· index가 총 사이즈를 넘어가면 작업 종료

예를들면

 

3) X_index 0 (3) < (5) Y_index 0,  Y가 더 큼  →  Y_index + 1
4) X_index 0 (3) < (4) Y_index 1,  Y가 더 큼  →  Y_index + 1
5) X_index 0 (3) == (3) Y_index 2,  X, Y 같음  →  결과값 저장, X_index +1, Y_index + 1
6) X_index 1 (2) == (2) Y_index 3,  X, Y 같음  →  결과값 저장, X_index +1, Y_index + 1
7) X_index 2 (2) < (1) Y_index 4,  X가 더 큼  →  X_index + 1
8) X_index 3 (1) == (1) Y_index 4,  X, Y 같음  →  결과값 저장, X_index +1, Y_index + 1
9) Y_index가 사이즈를 넘었기 때문에 루틴 종료

 

결과값 "321"으로 종료가 된다.

 

여기서 결과 예외조건

 1) 짝궁이 없으면 "-1"

 2) 0의 값이 여러개 있는 경우 ("00", "000")는 "0"으로 변환

까지 넣어주면 코드작성 완료

 

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
string solution(string X, string Y) {
    string answer = "";
 
    // 내림차순 정렬
    sort(X.begin(), X.end(), greater<char>());
    sort(Y.begin(), Y.end(), greater<char>());
 
    int X_index = 0;
    int Y_index = 0;
    while(true) {
        if((X.size() <= X_index) || (Y.size() <= Y_index)) {
            break;
        }
 
        char tmp_X = X[X_index];
        char tmp_Y = Y[Y_index];
        if(tmp_X == tmp_Y) {
            answer += tmp_X;
            X_index++;
            Y_index++;
        } else if(tmp_X > tmp_Y){
            X_index++;
        } else {
            Y_index++;
        }
    }
 
    if(answer.compare("") == 0) {
        answer = "-1";
    } else if(answer[0] == '0') {
        answer = "0";
    } else { }
 
    return answer;
}

 

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓