백준 알고리즘 1431번 - 시리얼 번호

algorithm에 있는 sort함수를 사용해서 구현하는 문제.

그 중에서 비교함수, cmp는 문제 조건에 맞춰서 작성해 주어야 한다.

 

그 전에 헷갈리는 return 값 부터 생각해보자.

비교 함수를 설정할때 cmp(a,b)의 return 값이 true 라면 cmp(a,b)에서 a가 먼저온다.

 

 

 

 cmp함수는 이렇게 구현하였는데, 채로 거르듯 조건마다 하나씩 걸러준다.

1. 길이 순으로 거르자.

    //길이순으로 길이가 짧은 것부터 먼저 오도록 한다
    if(alength<blength) return true;
    if(alength>blength) return false;
    //길이가 같다면
    if(alength==blength){

2. 문자열 자리수의 합으로 거르자

 

    for(int i=0;i<alength;i++){
            //a문자열의 자리수
            if((int)a[i]>='0' && (int)a[i]<='9'){
                asum=asum+(int)a[i]-'0';
            }//b문자열의 자리수
            if((int)b[i]>='0' && (int)b[i]<='9'){
                bsum=bsum+(int)b[i]-'0';
            }
        }
        //문자열의 자리수의 합을 비교 해서 작은 것부터 먼저 오도록 한다
        if(asum<bsum) return true;
        else if(asum>bsum) return false;

3. 사전순으로 비교한다.

 

 

 

    for(int i=0;i<alength;i++){
            //a문자열의 자리수
            if((int)a[i]>='0' && (int)a[i]<='9'){
                asum=asum+(int)a[i]-'0';
            }//b문자열의 자리수
            if((int)b[i]>='0' && (int)b[i]<='9'){
                bsum=bsum+(int)b[i]-'0';
            }
        }
        //문자열의 자리수의 합을 비교 해서 작은 것부터 먼저 오도록 한다
        if(asum<bsum) return true;
        else if(asum>bsum) return false;

주어진 조건대로 구현만 하면 되는 간단한 문제였다.

 

 

소스코드

 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool cmp(string &a,string &b)
{
	int asum=0,bsum=0;
	int alength=a.length();
	int blength=b.length();
	
	//길이순으로 길이가 짧은 것부터 먼저 오도록 한다
	if(alength<blength) return true;
	if(alength>blength) return false;
	//길이가 같다면
	if(alength==blength){
		for(int i=0;i<alength;i++){
			//a문자열의 자리수
			if((int)a[i]>='0' && (int)a[i]<='9'){
				asum=asum+(int)a[i]-'0';
			}//b문자열의 자리수
			if((int)b[i]>='0' && (int)b[i]<='9'){
				bsum=bsum+(int)b[i]-'0';
			}
		}
		//문자열의 자리수의 합을 비교 해서 작은 것부터 먼저 오도록 한다
		if(asum<bsum) return true;
		else if(asum>bsum) return false;
		
		//다 비교가 안됐을 경우 사전순으로 비교한다.
		for(int i=0;i<alength;i++){
			if(a[i]<b[i]) return true;
			else if(a[i]==b[i]) continue;
			else return false;
		}
	}
}

int main() 
{
	int num;
	cin>>num;
	string arr[1001];
	for(int i=1;i<=num;i++){
		cin>>arr[i];
	}
	sort(arr+1,arr+num+1,cmp);
	for(int i=1;i<=num;i++){
		cout<<arr[i]<<endl;
	}
}