백준 알고리즘 10989번

여태 알고리즘을 풀때 하루이상 걸린 문제가 없었지만 이건 무려 3일이나 걸려서 풀었다. 다 풀고나서 백준 문제 시스템에 엄청난 허점을 발견하게 되었다. 그건 바로 나의 코드가 틀렸을때의 테스트 케이스를 알지 못하는 것이다. 그렇기 때문에 예제 입력만 가지고 VS에서 풀때는 오류가 나지 않았지만 제출을 하게되면 틀렸다고만 뜬다... 그래서 50번 정도 시도했다.. 그만큼 배운게 많고 자세히 설명되어 있는 글이 없어서 내가 작성을 해본다.

아래링크에 있는 다른사람이 푼 코드를 참고기반으로 풀었다.

https://www.acmicpc.net/board/view/50936

글 읽기 - [C#] 시간초과, 메모리초과, 런타임에러 질문입니다.

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

백준 10989번 문제

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

문제풀이

사실이 문제의 문제와 입력 출력의 조건을 맞추는 것은 아주 쉽다. 기본 제공함수중에 Sort를 사용하면된다.

그래서 밑에 코드 처럼 작성을 하였고 결과로는 메모리 초과가 나왔다.

첫번째 코드(메모리 초과)

int input = Int32.Parse(Console.ReadLine());

int[] nums = new int[input];
for (int i = 0; i < nums.Length; i++)
{
    nums[i] = Int32.Parse(Console.ReadLine());
}
Array.Sort(nums);

foreach(int i in nums)
{
    Console.WriteLine(i);
}

여태까지 내가 과제를 내던 웹,앱프로젝트를 만들때 작성한 코드는 메모리에 대한 제한이 없었기 때문에 메모리를 신경쓰지 않고 작성을 했다. 그래서 이러한 오류가 났을때 입출력의 오류인줄알고 엄청 헤메었다. 10번정도 시도 끝에 메모리 제한과 시간제한에 대해 알게 되었고 8MB라는 엄청나게 쪼잔한 메모리 제한을 인지했다. 8MB는 8,000,000B이다.

위 코드에서 잘못된건 반복문의 종료 조건으로 첫번째 입력값의 맥스값인10,000,000이 주어진다면 nums는 총 10,000,000의 인덱스를가지고 int배열이므로 한 인덱스당 4바이트 총 40,000,000바이트를 차지한다는것이다. 이말고도 추가적인 메모리사용도 있지만 이미 8MB를 넘어버렸다.

과거 백준알고리즘을 작성할때 문자열을 다룰때 오류가 나면 StringBuilder가 해결했던 기억이 있기 때문에 사용해 보았다. 사실 이때까지만해도 StringBuilder에 대한 이해가 없어서 그냥 사용하면 메모리를 잡아먹지 않겠지 라는 생각을 했었다.

두번째 코드(메모리 초과)

using System.Text;
int input = Int32.Parse(Console.ReadLine());

StringBuilder sb = new StringBuilder("");


for (int i = 1; i <= input; i++)
{
    sb.Append(Console.ReadLine());
}

string a = sb.ToString();
char[] b = a.ToCharArray();

Array.Sort(b);

StringBuilder sb2 = new StringBuilder("");

for (int i = 0; i < input; i++)
{
    sb2.AppendLine(b[i].ToString());
}

Console.WriteLine(sb2.ToString());

위 코드도 메모리 초과가 나왔고 이유를 찾아보았다. StringBuilder를 사용하는 것도 메모리를 사용을 하는 것 이였고 그저 문자열 변경에 유용한 도구였다. 위 코드또한 StringBuilder에 포함되는 문자열 하나당 4바이트를 차지해서 8MB를 넘는다.

그래서 질문게시판에가서 내가 참고했다는 코드를 거의 배꼈다.

세번째 코드(성공)

using System.Text;

int[] counting = new int[10001];
var sw = new StreamWriter(Console.OpenStandardOutput());
StringBuilder sb = new StringBuilder();
int input = int.Parse(Console.ReadLine());
int max = 0;
//int num = 0;

for (int i = 0; i < input; i++)   
{
    int num = int.Parse(Console.ReadLine());
    counting[num]++;
}


for (int i = 0; i <= 10000;)
{
    if (counting[i] == 0)
    {
        i++;
        continue;
    }

    sb.Append(i + "\n");
    counting[i]--;
    if (3_000_000 <= sb.Length)
    {
        sw.Write(sb);
        sb.Clear();
    }


}
sw.Write(sb);
sw.Close();

배낀 코드다 보니 코드에 대한 해석이 먼저 필요했다. 메모리 값을 줄이기 위해 크기를 첫번째 입력값에 초점을 두지않고 두번째 입력값의 최대값인 10,000까지 넣을 수있게 counting배열을 10,001으로 초기화했다. 첫번째 반복문은 첫번째 입력값의 크기만큼 반복하고 그 후 입력하는 수를들 counting배열의 인덱스에 넣어서 1씩추가했다. 두번째 반복문은 counting배열의 크기만큼 반목하며 0번째 인덱스부터 0이아닐때 sb객체에 해당 숫자를 추가하였다. 두번째 if부분에서 3_000_000 <= sb.Length는 sb의 메모리크기가 8MB가 넘지 않기 위해서 임의로 정했다.( 3_500_000 <= sb.Length를쓰거나 if문을안쓰면 메모리 초과가나온다) 두번째 if문 조건에 걸릴때마다 출력을 해주고 초기화 시켜 메모리의 초과를 막았다.

사실 이 코드는 다른사람이쓴 코드를 보고 수정을했지만 처음에 다른 사람이 쓴 코드를 이해하기는 어려웠다. 코드가 어떻게 작동되는지 모르다보니 굳이 안 써도 되는 코드를 보고 의미부여를 하려고 했던것이 컸다. 사실 내가 통과하고도 이해가 안 되는 부분이 너무 많다. 다른 코드를 찾아보니 더 간결한 코드를 찾게 되었다.

네번째 코드

	    StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(sr.ReadLine()); // 수의 개수

            int[] numbers = new int[10001]; // 인덱스 번호에 있는 수가 나온 수

            // 주어지는 수들을 받음
            for (int i = 0; i < n; i++)
            {
                numbers[int.Parse(sr.ReadLine())]++;
            }

            sr.Close();

            // 결과 출력
            for (int i = 0; i < numbers.Length; i++)
            {
                for (int j = 0; j < numbers[i]; j++)
                {
                    sw.WriteLine(i.ToString());
                }
            }

            sw.Close();

출처 https://www.acmicpc.net/source/20623160

로그인

www.acmicpc.net

위 코드는 내가 여태썼던 Console.Read와 Console.Write대신에 StreamReader와 StreamWriter를 사용하였다. 만약 위코드에서 Console.Read와 Console.Write를 사용한다면 시간 초과가 나오게 된다. 즉 StreamReader와 StreamWriter가 더 실행시간이 빠르다는것을 알게 되었다. StreamReader와 StreamWriter에 대해 궁금해서 챗지피티한테 물어보았다.

챗 지피티의 대답

StreamReader 및 StreamWriter 대신 Console.Read 및 Console.Write를 사용하면 프로그램의 성능 및 효율성에 영향을 줄 수 있습니다. 이는 Console.Read 및 Console.Write 함수가 단일 문자로 작동하는 반면 StreamReader 및 StreamWriter는 더 큰 데이터 덩어리로 작동하기 때문입니다.

Console.Read 및 Console.Write 함수는 문자별로 데이터를 읽고 쓰기 위한 추가 처리가 필요하므로 실행 시간이 느려지고 메모리 사용량이 늘어날 수 있습니다. 반대로 StreamReader 및 StreamWriter 함수는 더 큰 청크로 데이터를 읽고 쓸 수 있으므로 성능을 개선하고 메모리 사용량을 줄일 수 있습니다.

또한 StreamReader 및 StreamWriter는 데이터 인코딩 지정 및 스트림 및 파일 작업과 같은 데이터 작업을 위한 추가 기능과 옵션을 제공합니다. Console.Read 및 Console.Write를 사용하면 코드의 유연성과 기능이 제한될 수 있습니다.

전반적으로 StreamReader 및 StreamWriter 대신 Console.Read 및 Console.Write를 사용할 수 있지만 특히 대량의 데이터 또는 더 복잡한 작업의 경우 가장 효율적이거나 효과적인 접근 방식이 아닐 수 있습니다.

즉 StreamReader는 일일히 읽는것이아니라 버퍼를 사용하기때문에 읽기 및 쓰기 작업의 수를 줄여 데이터를 보다 효율적으로 처리가 되어 빠른 속도를 낼 수있다는 것이다.

저작자표시 비영리 동일조건

메인블로그