글 읽기 - C# 메모리초과

qopwer4345 3년 전 0

StringBuilder를 사용해도 메모리초과가 계속납니다..

카운팅 정렬인데 여기서 어떻게 더해야할지 감이안잡혀요 ㅠㅠ

반례가 1000만개 정도되니 일일이 찾는건 무리라고 생각되서 최대 최소값을 여러번 반복해서 넣어보고 있는데도 이유를 모르겠습니다..

using System;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        StringBuilder sb = new StringBuilder();
        short[] arr = new short[10000001]; // inputArray
        short[] brr = new short[10000001]; // outputArray
        int[] count = new int[10001]; // 숫자 개수
        int[] countSum = new int[10001]; // 누적합
        int n = int.Parse(Console.ReadLine());
        for (int i = 1; i <= n; i++)
        {
            arr[i] = short.Parse(Console.ReadLine());
            count[arr[i]]++;
        }
        countSum[0] = count[0];
        for (short i = 1; i <= 10000; i++)
            countSum[i] = countSum[i - 1] + count[i];
        for (int i = n; i >= 1; i--)
        {
            brr[countSum[arr[i]]] = arr[i];
            countSum[arr[i]]--;
        }
        for (int i = 1; i <= n; i++)
        {
            sb.Append(Convert.ToString(brr[i])+'\n');
        }
        Console.WriteLine(sb);
    }
}

bupjae 3년 전 0

카운팅 정렬을 좀 더 생각해보면 arr 및 brr 없이 작성할 수 있습니다.

이 문제는 arr 이나 brr 같은 배열을 만들게 되면 거의 반드시 메모리 초과를 받도록 되어 있습니다.

bupjae 3년 전 0

추가로, 이 문제에서는 StringBuilder 의 사용 방법도 다시 생각해 봐야 합니다.

StringBuilder 가 *모든* 출력 결과를 가지고 있다면 거의 반드시 메모리 초과를 받게 됩니다.

qopwer4345 3년 전 0

카운팅정렬에 처음접근해봐서 그런데 접근방식은 맞는건가요?

어디선가 헛돌고 있는 반례가 있어보이기도 하고 흠..

bupjae 3년 전 0

이 프로그램에서 count 배열을 사용한 것은 카운팅 정렬이 맞습니다.

힌트를 드리자면

count 배열을 활용하되, 이걸 arr 이나 brr을 거치지 않고 입출력을 하면 됩니다.

추가로, 만약 StringBuilder 를 쓰고 싶다면, 아마도 StringBuilder 가 일정 크기 이상 커지지 않도록 관리하는 코드 또한 작성하셔야 할 겁니다.

qopwer4345 3년 전 0

흠.. 보니까 1000만개의 숫자를 저장할 array 자체가 필요없었군요 10000이하의 자연수가 몇개인지만 알면 되니까 ㅋㅋ..

이제 메모리 초과는 안나는데 시간초과가 납니다 ㅠㅠ

StreamReader를 사용해봤는데 사용방식이 잘못된걸까요?

using System.IO;
using static System.Console;


class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(ReadLine());
        int i, input;
        int[] count = new int[10001];
        for(i=1; i<=n; i++)
        {
            input = int.Parse(ReadLine());
            count[input]++;
        }
        FileStream file = new FileStream("Example.txt", FileMode.OpenOrCreate, FileAccess.ReadWrite);
        StreamWriter sw = new StreamWriter(file);
        for(i=1;i<10001;i++)
        {
            if(count[i] > 0)
            {
                for(int t=0; t<count[i]; t++)
                {
                    sw.WriteLine(i);
                }
            }
        }
        sw.Close();
        file = new FileStream("Example.txt", FileMode.Open, FileAccess.Read);
        StreamReader sr = new StreamReader(file);
        for (i = 0; i < n; i++)
            WriteLine(sr.ReadLine());
        sr.Close();
    }
}

paraworld 3년 전 0

StringBuilder에 크기 조정하는 식으로 가능하기는 한데, 상당히 시간과 메모리가 빡빡했습니다. StreamReader로 받고 StreamWriter로 제출하는 걸 추천합니다.

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

paraworld 3년 전 1

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

qopwer4345 3년 전 0

하 ㅋㅋ 똑같이 코드를 복붙해도 시간초과가 나는걸로 봐서는.. 그냥 포기하고 카운팅 정렬을 이해했다는것으로 만족하는게 좋을거 같습니다.

일단 입출력 방식에 대해서 하나 알아가서 좋네요 ㅎ

bupjae 3년 전 0

stdin / stdout 설정 방법에 따라서 시간초과가 나느냐 안 나느냐가 결정되는 것 같습니다.

일단 저는 아래와 같은 설정으로 6292 ms 맞았습니다 를 받았습니다.

이 문제의 C# 제한 시간이 8초 라는 걸 생각하면, 이와 같이 설정해도 좀 많이 빡빡한 제한인 것 같습니다.

		var fin = new StreamReader(Console.OpenStandardInput(2048), Encoding.ASCII, false, 2048);
		var fout = new StreamWriter(Console.OpenStandardOutput(2048), Encoding.ASCII, 2048);

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

문제

문제

출처

ICPC

C# 메모리초과

qopwer4345 3년 전 0

bupjae 3년 전 0

bupjae 3년 전 0

qopwer4345 3년 전 0

bupjae 3년 전 0

qopwer4345 3년 전 0

paraworld 3년 전 0

paraworld 3년 전 1

qopwer4345 3년 전 0

bupjae 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말