[프로그래머스] 코딩테스트 연습 - 숫자 짝궁(C)

-링크

https://school.programmers.co.kr/learn/courses/30/lessons/131128

프로그래머스

 

 

-문제 설명

두 정수 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의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

 

 

-입출력 예

"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

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

 

 

-해설

이 문제는 숫자를 역순으로 정렬하여 처음부터 차근차근 겹치는 숫자 순서대로 출력하면 끝나는 간단한 문제입니다.

우선 들어온 두 X,Y 배열을 큰 숫자 -> 작은 숫자 순서대로 정렬한 후 for문을 돌려 일치하는 숫자를 answer에 담아줍니다.

비교 대상 배열을 두고 다른 배열을 for문으로 돌려가면서 탐색할 때 같은 문자를 발견했을 시 break를 태우고 멈춥니다.

그 다음 탐색할 수를 가지고있다가. 비교 대상 배열을 다음으로 찾을 때 마지막으로 탐색했 던 위치 다음 부터 탐색하는 것이 탐색할 때 시간을 줄일 수 있습니다. 만일 맨 첫 번째로 찾은 값이 0이라면 그 다음 탐색은 필요없습니다. 0이 한개든 00으로 두개 던 숫자로 표현하면 0과 같기 때문에 그 부분도 예외처리를 하여 탐색 시간을 줄여줍니다.

만일 찾은 값이 아무것도 없다면 -1을 넣고 정답을 도출하면 됩니다.

 

 

-풀이(C)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int sort(const void* a, const void* b){
    return (*(char*)b - *(char*)a); 
}

char* solution(const char* X, const char* Y) {
    char* answer = (char *)malloc(3000000+1);
    int x_len = strlen(X);
    int y_len = strlen(Y);
    char* x_cpy = (char *)malloc(x_len+1);
    char* y_cpy = (char *)malloc(y_len+1);
    int pos = 0;
    int ans_pos = 0;
  
    memset(x_cpy, 0x00, x_len+1);
    memset(y_cpy, 0x00, y_len+1);
    strcpy(x_cpy, X);
    strcpy(y_cpy, Y);
      
    qsort(x_cpy, x_len, sizeof(char), sort);
    qsort(y_cpy, y_len, sizeof(char), sort);
    
    for(int i = 0; i < x_len; i++){
        for(int j = pos; j < y_len; j++){
            if(x_cpy[i] == y_cpy[j]){
                answer[ans_pos++] = x_cpy[i];
                pos = j+1;
                break;
            }
        }
        if(pos == y_len || answer[0] == '0') break;
    }
    
    if(pos == 0) strcpy(answer ,"-1");

    return answer;
}