정렬 단계 2751

백준 온라인 코딩 문제풀이

https://www.acmicpc.net/

Baekjoon Online Judge

 

코드 참고

https://replit.com/@wny0320

wny0320 (박 상운)

 

2751번에 대해 다룸

 

---

2751

수 정렬하기 2

 

똑같이 List를 사용하여 Sort를 사용하면 되는 문제이나 똑같이 작성하게 된다면 필자와 같은 오류에 마주하게 됨

 

리스트에 항목을 넣는 것은 insert가 아니라 Add로 넣기 때문에 시간 복잡도는 상수항임 O(1)

 

그리고 보통의 정렬 메소드는 퀵정렬로 이루어져 있어 정렬에도 시간의 문제가 없음

 

따라서 해결해야하는 문제는 입력과 출력이라고 유추할 수 있음

 

따라서 WriteLine()보다 성능이 좋은 Write("/n")을 이용해보았지만 마찬가지로 시간 초과가 뜸

 

그래서 필자는 StringBuilder를 사용하였음

 

string 같은 경우에는 문자가 하나 추가되거나 삭제되었을 때 나타나는 새로운 문자가 새롭게 메모리를 사용하기 때문에 성능이 매우 좋지 않음

 

StringBuilder와 같은 경우는 문자를 추가하거나 삭제해도 성능이 크게 바뀌지 않아 사용됨

 

using System;
using System.Collections.Generic;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
        int input = int.Parse(Console.ReadLine());
        List<int> num = new List<int>();
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < input; i++)
        {
            num.Add(int.Parse(Console.ReadLine()));
        }
        num.Sort();
        for (int i = 0; i < input; i++)
        {
            result.Append(num[i] + "\n");
        }
        Console.Write(result);
    }
}

위와 같이 코드를 작성하게 된다면 마지막 Write로 해당 StringBuilder의 내용이 전부 하나의 문자열로 출력됨

 

따라서 Write나 WriteLine을 여러번하는 것보다 성능이 향상됨