백준 1181번 C++ 단어 정렬하기

특정 조건에 따라서 단어 정렬하기

https://www.acmicpc.net/problem/1181

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

코드

#include <iostream>
#include <string>
#define swap(x, y, temp) ((temp)=(x), (x)=(y), (y)=(temp))
using namespace std;
 
int main() {
    int N, least;
    cin>>N;
 
    string arr[N], temp;
    for(int i=0; i<N; i++) {
        cin>>arr[i];
    }
 
    for(int i=0; i<N-1; i++) {
        least=i;
 
        for(int j=i+1; j<N; j++) {
            if(arr[j].length()<arr[least].length()) {
                least = j;
            }
 
            if(arr[j].length()==arr[least].length()
            && arr[j].compare(arr[least])<0) {//j번째 원소가 사전순으로 least보다 앞이면
                least=j;
            }
        }
 
        if(i!=least) {
            swap(arr[i], arr[least], temp);
        }
    }
 
    for(int i=0; i<N; i++) {
        if(i>0&&arr[i].compare(arr[i-1])==0) {
            continue;
        }
        cout<<arr[i]<<"\n";
    }
 
    return 0;
}

선택 정렬 알고리즘은 그냥 검색했다 ㅎㅎ;

그냥 알고리즘 헤더를 이용해서 하는 방법이 있을런지는 잘 모르겠으나

정렬을 직접 짜야하는 것 같다는 생각을 했고

문자열 길이를 먼저 비교해서 정렬하고 문자열 길이가 같고 j가 사전식 순서가 더 앞이라면 least 인덱스가 j가 되는 식으로.

그리고 같은 문자열 거르는 것은 인덱스가 0보다 클 때에 한해서 i번째 원소와 i-1번째 원소를 비교, 같으면 출력하지 않고 그냥 넘기고

그렇지 않으면 출력하는 식이다.

잠시 웹스터디를 했었는데 거기서 else를 쓰는 것은 좋지 않다고 했던 것 같다...

물론 모든 경우에 그런 건 아니지만, else를 쓰지 않고 할 수 있도록 해보려고 한다.

실제로 else를 쓰지 않으니까 오히려 예외처리가 더 편해진 느낌이다. 내가 원하는 것만 골라낼 수 있고.

else에 의존하지 않도록 해봐야 겠다.

이 문제에서 핵심은 정렬이기도 하지만 string으로 문자열 입력을 받았을 경우 compare의 쓰임같다.

compare로 문자열 비교하기(string)

문자열 A, B가 있다고 할 때

A.compare(B)<0 는 A가 B보다 사전식으로 앞에 있다는 뜻이다.

A-B<0으로 생각하면 쉬울 것 같다. A가 더 작다는 뜻이므로.

0보다 크면 A가 더 뒤에 있다는 뜻이고, 0이면 같다는 뜻.

근데 git에 커밋할 때 저렇게 했더니 warning 뜨더라. 저렇게 하면 안 좋나 보다...

이유는 잘 모르겠다.

아무튼 오랜만에 알고리즘 푸니까 머리 쓰는 느낌이 난다 ㅋㅋㅋㅋ

교환학생 와서는 먹고 사는 걱정 하다 보니까 뒷전이었는데.

일주일에 몇 문제라도 풀어야겠다