[백준 알고리즘 / C++] BOJ.1427 : 소트인사이드

 

문제

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

1427번: 소트인사이드

 

---

풀이

자료구조

- string 또는 char을 사용한 문자형 배열

- 입력을 최대 10억의 숫자가 아니라 10글자짜리 문자열로 봐야함

 

알고리즘

- 정렬 알고리즘 사용

- 입력 개수가 10이 최대라 버블 정렬을 사용해도 될 듯함

- 버블 정렬의 시간 복잡도 O(n²)

 

 

코드

- C++은 string이라는 문자열을 처리하기에 유리한 변수가 있기 때문에 사용

-  getline() 함수를 사용하면 문장을 개행문자(\n) 전까지 한 번에 입력받을 수 있음

---

코드 

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


int main() {
    string string1;  //문자열 변수 선언
    getline(cin,string1);  //string1에 입력 받기
    char temp; //정렬에 사용할 임시 변수

//버블정렬
    for(int i = 0; i < string1.length() - 1; i++) {
        for(int j = 0; j < string1.length()- 1 - i; j++) {
            if(string1[j] < string1[j+1]) {
                temp = string1[j];
                string1[j] = string1[j + 1];
                string1[j + 1] = temp;
            }
        }
    }
    cout << string1 << endl;
    return 0;
}

 

---

총평

입력값의 최대 개수가 10으로 작았기 때문에 버블 정렬로도 쉽게 풀 수 있었다.

만약 입력값의 개수가 크다면 실행시간을 고려하여 O(nlogn)인 힙 정렬이나 퀵 정렬도 고려하였을 것이다.