백준 c++백준 1181번 단어정렬 (부제 :c++의 말도 안되는 편리함)

실패코드

#include<iostream>
#include<cstring>
using namespace std;

int ft_strcmp(char *str1, char *str2)
{
        if(strlen(str1) !=strlen(str2))
        {
                if (strlen(str1) > strlen(str2))
                                return (1);
                else
                        return (-1);
        }
        while (*str1 == *str2 && *str1 && *str2)
        {
                str1++;
                str2++;
        }
        return (*str1 - *str2);
}

int main()
{
        int inputnum;
        cin >> inputnum;
        char **arr = new char*[inputnum + 1];
        char *tmp;
        for (int i = 0; i < inputnum; i++)
        {
                arr[i] = new char[51];
                cin >> arr[i];
        }
        arr[inputnum] =0;
        for(int i = 0; i < inputnum; i++)
        {
                for (int j = i + 1; j < inputnum; j++)
                {
                        if(ft_strcmp(arr[i],arr[j]) > 0)
                        {
                                tmp = arr[i];
                                arr[i] = arr[j];
                                arr[j] = tmp;
                        }
                }
        }
        for(int i = 0; i <inputnum;i++)
        {
                if (arr[i+1]&&ft_strcmp(arr[i],arr[i + 1]))
                        cout << arr[i]<<endl;
        }
        for(int i = 0; i <inputnum; i++)
        {
                delete arr[i];
        }
        delete arr;
        return (0);

}

처음으로 풀때는 위와같이 문제를 풀었었다. 하지만 버블 정렬을 사용했기 떄문에 시간 복잡도상에서 탈락을 하였다.

그래서 아 이런 머지소트를 또 구현해야 하다니.... 싶었는데 이게 왠걸...! 별다른 기대없이 다른 코드를 보던중 말도 안되는걸 찾아서 그렇게 풀었는데 일단 말이 안되는 많은 기능들을 정리해보자.

#include<iostream>
#include<algorithm>
using namespace std;

int ft_strcmp(string str1, string str2)
{
        if (str1.length() == str2.length())
        {
                return (str1 < str2);
        }
        else
                return (str1.length() < str2.length());
}
string str[20000];
int main()
{
        int inputnum;
        cin >> inputnum;

        for (int i = 0; i < inputnum; i++)
        {
                cin >> str[i];
        }
        sort(str, str+inputnum , ft_strcmp);//1일때 정렬을 한다는 의미로 받아드리자. 참일때 0 거짓일떄 1
        for(int i = 0; i <inputnum;i++)
        {
                if (str[i-1] != str[i])
                        cout << str[i]<<endl;
        }
        return (0);

}

우선 정답코드는 다음과 같다.

일단 놀라운점 1번

string 이라는 클래스가 std안에 정의가 되어있다.

이 문제에서 사용된 스트링 클래스의 특징만 살펴보자면

1. 클래스 내장 메소드로 length()가 존재해서 str.length() 를 하게 된다면 그 스트링의 길이를 구할 수 있었다.

2. string 클래스는 등호와 비교연산자만으로 그 문자열의 아스키 코드값으로 알아서 비교해준다. ( strcmp함수가 내장되서 알아서 작동하는 구조인 것 같다!!)

string 클래스 사용방법 일단 스트링 헤더는 #include<string> 에 존재한다.

1. std :: string str1;

str1 = "hello world";

-단 이방법일땐 굳이 string 헤더를 선언하지 않아도 된다.

2. string str("hello worild");

3. string str1;

str1 = "hello world";

​

<string 의 특징>

string 클래스는 char형과 달리 문자열의 끝에 \0이 있지 않다.

​

str1.at(index) : 그 위치에 있는 문자 반환 인덱스의 범위를 검사해 그 범위를 벗어나면 예외를 벹는다.

str1.operator[index] 비슷하나 배열처럼 접근하지만 인덱스의 범위를 검사하지 않는다.

str.front() : 맨 앞인자 반환

str.back() ;맨뒤 인자 반환

str.size() : string 의 사이즈를 반환

str.length(): string의 길이를 반환 -- size 함수와 같다고 봐도된다.

str.capacity(): string객체에 할당된 메모리크기 반환

str.resize(n) -> str크기를 n 으로 바꾼다.

str.resize(n,'a')-> n 으로 크기를 바꾸고 a로 채운다.

str1.shrink_to_fit(); -> 낭비되는 스트링의 길이를 즉 메모리를 줄인다.

str1.clear() -> 스트링 내부 문자열을 지운다. size length 는 줄어들지만 메모리 크기는 그대로 유지된다.

str.empty() -> 스트링이 비었는지 확인한다.

일단은 이정도로 정리할 거고 더 많은 기능이 있는 것 같지만 일단은 여기서 접는다.

​

2. 두번째로는 sort함수를 사용한다는 점이다.

선택정렬 버블정렬 (간단 ) 이 친구들을 사용할때는 전혀 부담이 되지는 않는다. 하지만 시간복잡도가 빅오표기법으로 n^2라서 솔직히 상당히 비효율적이다. 그래서 더 빠른 정렬 알고리즘을 공부했었다.

퀵 소트 머지소트 삽입정렬 계수정렬에 대해서 공부했었지만 공부할때는 이해했지만 한번더 암기 과정이 필요하다... 일단은 이정도로 하고, 두번째로는 그래서 문제를 풀때 망했다 싶었다. 1일1백준을 하는데 이런 간단한 문제에서 시간을 그렇게 쏟아야하다니... 그래서 찾아봤는데

sort함수가 있지 않던가!!

sort() 함수의 기본 사용법

#include<algorithm>이 헤더파일에 존재한다.

sort(arr, arr+10);이렇게 하면 10개의 원소의 배열을 오름차순으로 정렬을 실행한다.

두번째 경우 는

sort(arr, arr+10, compare); -> 일단 함수 포인터를 보내서 사용했다고 볼 수 있는데 이 함수를 만들면 좋은점은 정렬의 기준이 내가 원하는 기준이 될 수가 있다는 점이다!!

첫번째 경우는 기본적으로 함수가

bool compare (int a,int b) { return (a<b) ; }

이것을 의미한다!!!

참이 1이고 거짓이 0인 컴퓨터 언어를 볼때 이 함수는 앞에 친구가 더 작을때 참을 하기때문에 함수가 거짓일때 두개를 변경한다고 생각하면 될 것 같다.

 

이 글은 코딩 꼬꼬마 시절에 푼 문제를 보관한 글로 네이버에 저장해둔 글을 옮긴 글입니다.
혹시나 참고하시는 부분에 이상한 부분이나 질문이 생긴다면 남겨주시면 친절히 답변 드리겠습니다.