글 읽기 - [c#] 도저히 모르겠습니다 오늘 밤에 잠 못자요 ㅠㅜㅠㅜㅠㅜ

simplex3510 2년 전 0

카운팅 정렬을 해서 풀라는데 StringBuilder로 하니 메모리 초과가 뜹니다...

이외의 방법은 전혀 생각이 나질 않구요 ㅠㅜㅜㅠ 제발 도와주세요 ㅠㅜㅜㅠㅠㅜ

using System;
using System.Text;

namespace baekjoon12_3
{
    class MainApp
    {
        static int[] counting = new int[10_001];

        static int[] CountingSort(int[] arr, int max)
        {
            int[] result = new int[arr.Length];

            for (int i = 0; i < arr.Length; i++)    // 카운팅
                counting[arr[i]]++;

            for (int i = 1; i <= max; i++)          // 누적합 연산
                counting[i] += counting[i-1];

            for (int i = 0; i < result.Length; i++) // 정렬
                result[--counting[arr[i]]] = arr[i];

            return result;
        }

        static void Main()
        {
            StringBuilder sb = new StringBuilder();
            int testCase = int.Parse(Console.ReadLine());
            int[] arr = new int[testCase];
            int max = int.MinValue;

            for (int i = 0; i < testCase; i++)
            {
                arr[i] = int.Parse(Console.ReadLine());
                if(max < arr[i])
                    max = arr[i];
            }

            arr = CountingSort(arr, max);

            for (int i = 0; i < testCase; i++)
                sb.Append(arr[i] + "\n");

            Console.WriteLine(sb);
        }
    }
}

adfsfsf 2년 전 1

이 문제는 정렬을 하는 것이 아니라, 정렬한 결과를 출력하는 것입니다. 즉, 정렬된 결과는 필요하지 않습니다.

달리 말하자면, 정렬 함수는 없어도 되며, 그 안에서 선언된 변수들은 전부 없어도 됩니다.

또한, arr 배열도 필요하지 않습니다. 단일 변수를 이용해서 counting배열에 직접 값을 넣으면 됩니다.

이후에, 작은 수부터 counting에서 값이 있는 수들만 들어간 개수만큼 출력해주면 됩니다.

이 다음은 시간을 줄일 방법을 찾아보시면 될 것입니다.

adfsfsf 2년 전 1

해 보니까 메모리를 더 줄일 방법이 필요하군요. 만약 더 찾으면 적겠습니다.

simplex3510 2년 전 0

진짜 풀고싶은 문제 입니다 도와주시는 것 만으로도 너무나도 감사드려요 ㅜㅠㅜㅠㅠㅜㅠㅜㅠㅜㅠㅠㅜㅜ

adfsfsf 2년 전 1

누가 c# 코드 하나 공개로 올려두신 거 있네요.

https://www.acmicpc.net/source...

StreamReader랑 StreamWriter를 쓰셨더라고요. 이 2개가 기존 입출력보다 용량이나 시간을 더 적게 쓰는 것 같아요.

simplex3510 2년 전 0

소스가 404 에러 떠서 그런데 어디서 볼 수 있나요??!!!

adfsfsf 2년 전 1

채점 현황 들어가셔서 언어를 C#으로 해보세요. 2~3 페이지 즈음에 클릭 가능한 게 있을 거에요.

simplex3510 2년 전 0

아마 아직 못 맞춰서 제가 볼 수 있는 권한이 없어서 못 보는 거 같네요.... ㅜㅠㅜ

adfsfsf 2년 전 1

그럼 일단 C언어나 python 같은 좀 쉽게 풀 수 있는 언어로 풀어보시는 게 나을 것 같네요...

adfsfsf 2년 전 1

그럼 입출력 핵심 코드만 적어드릴게요.

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


sw.Flush();
sr.close();
sw.close();

simplex3510 2년 전 0

도와주셔서 정말 감사드립니다 ㅠㅜㅜ 하지만 c#으로 풀어야지 찜찜한게 풀릴 거 같아서요! 좀 더 노력해보겠습니다!

simplex3510 2년 전 0

선생님! 드디어 메모리 초과 이슈를 해결했습니다!

다만 문제가 조금 생겼습니다... 기존의두 배열을 삭제하고 counting으로만 출력하는데

틀렸습니다가 나옵니다... 자꾸 귀찮게 해서 죄송합니다만 염치 불구하고 부디 꼭 도와주셨으면 합니다 ㅠㅠ

using System;
using System.Text;
using System.IO;

namespace baekjoon12_3
{
    class MainApp
    {
        static void Main()
        {
            short[] counting = new short[10_001];

            //var sr = new StreamReader(Console.OpenStandardInput());
            var sw = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();
            int testCase = int.Parse(Console.ReadLine());
            int max = int.MinValue;
            int num = 0;

            for (int i = 0; i < testCase; i++)    // 카운팅
            {
                num = int.Parse(Console.ReadLine());
                counting[num]++;
                if (max < num)
                    max = num;
            }


            for (int i = 0; i <= max;)             // 정렬해서 출력
            {
                if (counting[i] == 0)
                {
                    i++;
                    continue;
                }

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

simplex3510 2년 전 0

꼭 64%에서 틀렸습니다가 나옵니다... 잘 가다가 이게 어느 부분에서 걸리는 거 같아요!

adfsfsf 2년 전 0

각 수의 최대 등장 횟수는 N의 최댓값과 같으며, 이는 short 범위를 넘습니다.

simplex3510 2년 전 0

ㅠㅜㅠㅜㅠㅜㅠㅜㅠㅜㅠㅜㅠㅜㅠㅜㅠㅠㅜㅠㅜㅠㅜㅠㅜㅠㅜㅠㅜㅠㅜㅠㅜ

선생님 덕분에 오늘 꿀잠 예약했습니다ㅠㅜㅜㅠㅜㅠㅜㅠㅠㅜㅜㅠㅜ 정말 감사합니다!!!

using System;
using System.Text;
using System.IO;

namespace baekjoon12_3
{
    class MainApp
    {
        static void Main()
        {
            int[] counting = new int[10_001];

            //var sr = new StreamReader(Console.OpenStandardInput());
            var sw = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();
            int testCase = int.Parse(Console.ReadLine());
            int max = int.MinValue;
            int num = 0;

            for (int i = 0; i < testCase; i++)    // 카운팅
            {
                num = int.Parse(Console.ReadLine());
                counting[num]++;
                if (max < num)
                    max = num;
            }


            for (int i = 0; i <= max;)             // 정렬해서 출력
            {
                if (counting[i] == 0)
                {
                    i++;
                    continue;
                }

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

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

문제

문제

출처

ICPC

[c#] 도저히 모르겠습니다 오늘 밤에 잠 못자요 ㅠㅜㅠㅜㅠㅜ

simplex3510 2년 전 0

adfsfsf 2년 전 1

adfsfsf 2년 전 1

simplex3510 2년 전 0

adfsfsf 2년 전 1

simplex3510 2년 전 0

adfsfsf 2년 전 1

simplex3510 2년 전 0

adfsfsf 2년 전 1

adfsfsf 2년 전 1

simplex3510 2년 전 0

simplex3510 2년 전 0

simplex3510 2년 전 0

adfsfsf 2년 전 0

simplex3510 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말