글 읽기 - 9019 C# 메모리 초과 이유를 잘 모르겠습니다

darkpppet 2년 전 0

10000회 랜덤값으로 시뮬레이션 돌려봐도 많아야 메모리 8메가를 먹던데 틀린부분 있는지 궁금합니다.

using System;
using System.Text;
using System.Collections.Generic;

int t = int.Parse(Console.ReadLine());

for (int i = 0; i < t; i++)
{
	string[] input = Console.ReadLine().Split(' ');
	
	int a = int.Parse(input[0]);
	int b = int.Parse(input[1]);
	
	Dictionary<int, (int BeforeNum, char BeforeCalc)> history = new()
	{
		[a] = (a, '\0')
	};

	HashSet<int> beforeSet = new() { a };
	
	while (!history.ContainsKey(b))
	{
		HashSet<int> tempSet = new();
		
		foreach (int num in beforeSet)
		{
			int d = (2 * num) % 10000;
			int s = (num + 9999) % 10000;
			int l = (num / 1000 + 10 * num) % 10000;
			int r = 1000 * (num % 10) + num / 10;
			
			if (!history.ContainsKey(d))
			{
				history[d] = (num, 'D');
				tempSet.Add(d);
			}
			
			if (!history.ContainsKey(s))
			{
				history[s] = (num, 'S');
				tempSet.Add(s);
			}
			
			if (!history.ContainsKey(l))
			{
				history[l] = (num, 'L');
				tempSet.Add(l);
			}
			
			if (!history.ContainsKey(r))
			{
				history[r] = (num, 'R');
				tempSet.Add(r);
			}
		}
		
		beforeSet = new(tempSet);
	}
	
	StringBuilder outputBuilder = new();
	for (int before = b; before != a; before = history[before].BeforeNum)
		outputBuilder.Insert(0, history[before].BeforeCalc);
	Console.WriteLine(outputBuilder.ToString());
}

darkpppet 2년 전 1

외부에서 도움을 받아 해결했습니다.

for-loop마다 object 생성 시, GC가 이것을 제때 처리 해 주지 않는 것 같습니다. (https://stackoverflow.com/ques...)

즉, loop안에서 메모리 사용량이 큰 편인 history(Dictionary) 객체를 loop 바깥에 생성 해 두고, loop마다 Clear해주는 식으로 구현하여 통과했습니다.

(통과한 답 채점번호 30435853입니다!!)

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

문제

문제

출처

ICPC

9019 C# 메모리 초과 이유를 잘 모르겠습니다

darkpppet 2년 전 0

darkpppet 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말