글 읽기 - 시간초과 질문...

rmatlf0708 4년 전 0

처음 짠 코드가 시간초과가 되어서 cout/cin과 string 대신 printf/scanf, char*로도 써보고, int len = length(s) 해서 for문 안의 함수 호출도 줄여보고,

대문자로 변환하는 포문을 밑의 포문으로 보내서 포문 하나를 줄여보는 등 여러 시도를 해도 계속 시간 초과가 뜨더라고요...

그래서 아예 다른 방법으로 해본 것이 밑의 코드인데 이건 정답 처리 되는데,,, 왜 첫번째 코드는 시간이 오래걸리는 것 일까요...?

중첩된 포문은 되도록이면 피해야되나요?? 저는 첫번째 코드를 더 잘짰다고 생각했거든요....

그리고 앞으로 알파벳의 개수 관련된 문제는 웬만하면 밑의 문제처럼 각각의 알파벳의 개수에 대응하는 배열로 푸는게 좋을까요??

코딩 독학 초보라 모르는 게 너무 많네요...

답변해주셔서 감사합니다~

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main()  // 처음 짠 코드 -> 시간 초과
{
	string s;
	cin >> s;
	
	// 대문자로 변환
	for (int i = 0; i < s.length(); i++) 
		s[i] = toupper(s[i]);	

	int max_count = 0;
	char max_alpha;

	for (int i = 0; i < s.length(); i++)
	{
		int count = 1;
		for (int j = i + 1; j < s.length(); j++)
		{
			if (s[i] == s[j])
				count++;
		}

		if (count > max_count)
		{
			max_alpha = s[i];
			max_count = count;
		}
		else if (count == max_count)
			max_alpha = '?';
	}

	cout << max_alpha << endl;

}



int main() // 맞은 코드
{
	string s;
	cin >> s;
	int count[26] = { 0, };
	int len = s.length();

	for (int i = 0; i < len; i++)
	{
		int index = toupper(s[i]) - 'A';
		count[index]++;
	}
	
	int max = 0, max_index;
	bool ismul = false;

	for (int i = 0; i < 26; i++)
	{
		if (count[i] > max)
		{
			max = count[i];
			max_index = i;
			ismul = false;
		}

		else if (count[i] == max)
			ismul = true;
	}

	if (ismul == true)
		cout << "?" << endl;
	else
		cout << (char)(max_index + 'A') << endl;

}

djm03178 4년 전 1

시간 복잡도에 대해 공부해 보세요.

shg9411 4년 전 1

저도 초보지만 댓글 남겨봅니다.

알파벳과 관련된 문제들은 26칸 배열로 푸는것이 좋은 편입니다.

중첩 for문의 경우 시간 복잡도가 O(n^2)이라고 보시면 글자 수가 최대 1,000,000이므로 10^12가 되겠죠.

그리고 위의 코드는 글자의 카운트를 비교하시는 부분에 있어서도 같은 알파벳에 대하여 여러번 비교할 것 같네요

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

문제

문제

출처

ICPC

시간초과 질문...

rmatlf0708 4년 전 0

djm03178 4년 전 1

shg9411 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말