글 읽기 - 1157번 C# 시간초과 나옵니다 ㅠ

qordlstn123 5년 전 0

일일이 비교해보는게 비효율적이라서 시간초과가 나는걸까요...

어떤 방식으로 풀어야 할지 모르겠습니다 ㅠ

using System;

namespace Prob1157
{
    class Program
    {
        static void Main(string[] args)
        {
            string input = Console.ReadLine();

            input = input.ToUpper();

            char[] alpha = new char[input.Length];
            int max = 0, maxarray = 0;
            int[] overlap = new int[input.Length];

            for (int i = 0; i < input.Length; i++)
                alpha[i] = input[i];

            for (int i = 0; i < input.Length; i++)
            {
                for (int j = i; j < input.Length; j++)
                {
                    if (alpha[i] == alpha[j])
                    {
                        overlap[i]++;
                        if (max < overlap[i])
                        {
                            max = overlap[i];
                            maxarray = i;
                        }
                    }
                }
            }

            for (int i = 0; i < input.Length; i++)
            {
                if (i != maxarray && max == overlap[i])
                {
                    Console.WriteLine("?");
                    return;
                }
            }

            Console.WriteLine(alpha[maxarray]);
        }
    }
}

exponential_e 5년 전 1

우선 문제에서 입력이 최대 100만이기 때문에 반복문을 입력 길이에 따라 돌렸을때 중첩시키시면(20~34번째 줄까지) 이미 1초가 넘어가버립니다. (최악의 경우 1,000,000 ^ 2)

문제 조건으로 알파벳만 들어온다고 했으니 이를 고려해서 푸신다고 생각하면 금방 해결책을 찾으실 수 있을 것 같아요.

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

문제

문제

출처

ICPC

1157번 C# 시간초과 나옵니다 ㅠ

qordlstn123 5년 전 0

exponential_e 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말