2021.02.08 알고리즘

Lee Jeong Min·2021년 2월 8일

알고리즘

목록 보기

1/4

📌백준 문제 1181 단어정렬

문제

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

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

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

📌처음 시도 코드

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

int main(void)
{
    int n;
    
    cin >> n;
    
    string arr[n];
    string carr[n];
    
    for(int i = 0; i<n; i++)
    {
        cin >> arr[i];
    }

    for(int i = 0; i<n; i++)
    {
        for(int j = i+1; j<n; j++)
        {
            if(arr[i].length() > arr[j].length())
            {
                string temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            else if(arr[i].length() == arr[j].length())
            {
                if(arr[i] > arr[j])
                {
                    string temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            else
                continue;
        }
        
    }
    
    for(int i = 0; i<n; i++)
    {
        for(int j = i+1; j<n; j++)
        
        cout << arr[i] << endl;
    }
    
    return 0;
}

시간초과로 인해서 채점 불가

📌STL및 기타 팁에 대한 공부

STL에 set이라는 라이브러리 존재

set container

연관 컨테이너 중 하나이다.
노드 기반 컨테이너 이며 균형 이진트리로 구현되어 있다.
Key라 불리는 원소들의 집합으로 이루어진 컨테이너 이면 중복 불가!
원소가 insert 멤버 함수에 의해 삽입이 되며, 자동 정렬
default 정렬기준은 오름차순 이다.

기본 set 사용법

   set<T> 변수명;

c++ auto

auto는 초기화 값에 따라 자동적으로 데이터의 타입을 정해주는 키워드이다. 보통 iterator를 사용 시 많이 사용한다고 함.

기타 팁

입출력 속도차이 해결을 위해 다음의 코드를 작성해줌

ios::sync_with_stdio(0);
cin.tie(0);

ios::sync_with_stdio(0) 와 cin.tie(0)

ios::sync_with_stdio의 경우 기존 c 표준 stream과 c++ stream의 동기화를 끊어서 실행속도를 늘려주지만 기존 C와 C++의 입출력 방식 혼용하여 쓰는 것이 위험해진다.(출력 순서 보장 x)

cin.tie(0)은 기존 printf, scanf보다 cin, cout의 속도가 느리기 때문에 이것을 작성해주어서 속도 향상을 시킨다

endl 대신 '\n' 사용!

실행 속도가 출력의 개수가 많으면 많을수록 엄청나게 차이가 나게 된다.

📌최종 코드

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

struct compare {
    bool operator() (const string &s1, const string &s2) const
    {
        if(s1.size() == s2.size())
            return s1<s2;
        else
            return s1.size() < s2.size();
    }
};


int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    string word;
    cin >> n;
    set<string, compare> s;
    
    for(int i = 0; i<n; i++)
    {
        cin >> word;
        s.insert(word);
    }

    for(auto str: s)
        cout << str << '\n';
    
    return 0;
}