글 읽기 - 백준 1157번

kkh3972460 2년 전 0

1157번 시간 초과 오류 피드백 부탁드려요!

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>


int bubble_sort(char arr[], int count)
{
	int temp;

	for (int i = 0; i < count; i++)
	{
		for (int j = 0; j < count - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	return 0;
}
int main()
{
	
	char str[1000001] = { 0, };
	int count;
	char result;

	int temp = 0;
	scanf("%[^\n]s", str);
	count = strlen(str);
	


	for (int i = 0; i < strlen(str); i++)
	{
		if (str[i] >= 'a' && str[i] <= 'z')
		{
			str[i] = str[i] - 32;
		}
	}

	bubble_sort(str, count);
	count = 1;

	for (int i = 0; i < strlen(str)-1; i++)
	{
		if (str[i] == str[i + 1])
		{
			count++;
			if (count == temp)
			{
				result = '?';
			}
			else if (count > temp)
			{
				temp = count;
				result = str[i];
			}	
		}

		else
		{
			count = 1;
		}
	}
	printf("%c", result);
	
}

djm03178 2년 전 1

우선 시간 복잡도의 개념을 먼저 공부하시는 것을 추천드립니다. 버블 정렬은 O(N^2)의 시간 복잡도를 가지고 있기 때문에 너무 느립니다. 병합 정렬, 힙 정렬 등의 O(NlogN)의 정렬을 사용해야 합니다.

반복문의 조건문에 strlen을 넣는 것도 O(N^2)입니다. 길이를 미리 얻어놓고 그 값을 계속 사용해야 합니다.

kkh3972460 2년 전 0

아 참고해서 해결해보겠습니다!!

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

문제

문제

출처

ICPC

백준 1157번

kkh3972460 2년 전 0

djm03178 2년 전 1

kkh3972460 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말