SWEA 7701 - 염라대왕의 이름 정렬(C++)

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqU0zh6rssDFARG 

SW Expert Academy

 

풀이

이 문제는 입력된 문자열들을 중복 제거, 길이 짧은 순 정렬, 길이 같다면 사전순 정렬하는 문제이다.

처음에는 문제 대충 읽고 중복 제거 + 사전순 정렬로 생각해서 set으로 구현했는데 당연히 틀려서 삽질을 좀 했었다..

그리고 이 문제가 시간 제한이 있어서 cin/cout을 쓰면 pass를 못한다.

그래서 scanf/printf를 사용해야 하는데, 또 문자열을 다루기 때문에 string을 사용하지 못하고 char 배열로 입력받았다.

암튼 그래서 배운 것들,,

 

1) string 을 printf 해주려면 c.str()을 사용한다.  --->  printf("%s",s.c.str());

2) 문자열을 담은 배열을 sort 할 때, 정렬 조건을 정해주고 싶다면 인덱스를 담은 배열을 이용한다.

문자열을 담은 배열을 정렬하는 것이 아니라, 인덱스를 정렬.

 

bool cmp(int i, int j)
{
    if(strlen(name[i])==strlen(name[j]))
    {
        return (strcmp(name[i],name[j])<0);
    }
    else return (strlen(name[i])<strlen(name[j]));
}

sort(idx,idx+n,cmp);

 

이렇게 수행해주면 idx라는 인덱스들을 담은 배열에는 정렬 조건에 맞게 정렬이 된다.

이를 문자열을 담은 배열의 인덱스처럼 사용하면 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
 
bool cmp(string s1, string s2)
{
    if(s1.length()==s2.length())
    {
        return (s1.compare(s2)<0);
    }
    else return (s1.length()<s2.length());
}
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
    scanf("%d",&T);
    for(test_case = 1; test_case <= T; ++test_case)
    {
        vector<string> v;
        int n;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            char str[51];
            scanf("%s",str);
            v.push_back(str);
        }
        sort(v.begin(),v.end(),cmp);
        printf("#%d\n",test_case);
        for(int i=0; i<n; i++)
        {
            if(v[i]==v[i+1]) continue;
            printf("%s\n",v[i].c_str());
        }
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}