문제 : 사전순으로 단어를 생성하여 N 번째 올 단어를 찾아라  

 


● 특정 문자열이 주어지고 이 문자열 안에 포함된 단어들을 사전순으로 정렬하라. 그리고 주어진 N 번째 오는 단어가 무엇인지 구하라.

단, 문자열의 최대 길이는 1,000 이고, 모두 소문자 알파벳으로만 되어 있다.

중복되는 단어는 한 단어로 생각한다. 

시간제한이 있다. (빠를 수록 점수가 높다, 1초가 넘으면 실패)


● 사전순이란 것은 알파벳 a ~ z 까지 단어를 정렬하는 것을 의미한다. 


● 예를 들어, melon 이란 문자열이 주어졌을 때, 7번째 오는 단어를 구하라. 

melon 안에 포함된 단어를 사전순으로 정렬하면 다음과 같다. 

1 : e

2 : el

3 : elo

4 : elon

5 : l

6 : lo

7 : lon

8 : m

9 : me

10 : mel

11 : melo

12 : melon

13 : n

14 : o

15 : on


즉, 답은 lon 이 된다. 



 

 일반적인 풀이  

 

● 풀이방법 1 : 위 문제와 같이 알파벳 a부터 문자열 안에 단어를 찾고, 그 뒤로 한글자씩 붙여서 단어를 만들어 나간다.

    

○ 문제점 :  주어진 문자열이 최대 1,000으로 길기 때문에 a가 몇번이고 반복될 수 있다. 예를 들어, a 부터 시작할 경우, 문자열 내의 모든 a 의 위치들을 기록하고, 그 뒤에 오는 단어들을 비교해서 순서를 만들어 나가야 한다. a가 세 번 반복된 경우, 각각의 단어의 뒷글자를 확인해서 순서를 정해야 한다. 위 문제의 예제와 같은 경우는 e가 한 번만 나오지만, e가 계속 반복되는 경우, 또 비슷한 알파벳이 많아지는 경우 문제가 복잡해진다. 


● 풀이방법 2 : 문자열의 첫글자부터 문자열을 만들어 나가면서 이 문자열을 이진 트리 형태로 저장하여 빠르게 정렬한다. 이를 통해 n 번째 아이템을 빨리 찾을 수 있다. 풀이방법 1의 반복적인 검색을 생략할 수 있다.

○ 문제점 : 모든 문자열을 다 만들어보아야 해서 메모리 문제가 있을 수 있다. C++이나 Java로 문제를 푸는 경우는 메모리 이슈를 피할 수 있지만 <STDIO.H> 만 허용된 C언어에서는 어려움이 있다. 트릭을 통해 malloc과 유사하게 푼다 하여도 속도 이슈가 발생할 수 있다. 실제로 C++로 이 문제를 푼 경우 제한 시간에 걸렸다. 



   답이 되는 풀이  
 

● 생각의 전환이 필요하다. 문자열로부터 시작하는 것이 아니라 사전 으로 부터 시작한다. 즉, a가 있는지 검색하고 있으면 다시 aa가 있는지 검색한다. 이 때, 문자열 전체를 보는 것이 아니라 a를 찾은 위치에서 그 바로 뒤에 문자와만 비교하면 된다. a를 찾은 위치의 인덱스를 활용한다. 


● 예를 들어, 주어진 문자열이 kdaabdgga 일 때, 

1) 우선 a 를 찾는다. 인덱스가 2에 a가 있음을 발견한다. 

2) 인덱스 2부터 aa가 있는지 확인한다. 인덱스 2에 aa가 있다.

3) 인덱스 2부터 aaa가 있는지 확인한다. 인덱스 2에는  aaa는 없다

3-1) 문자열 전체에서 aaa가 있는지 확인한다. aaa는 없다. 

4) 인덱스 2부터 aab가 있는지 확인한다. aab는 있다. 

5) 인덱스 2부터 aaba가 있는지 확인한다. 인덱스 2에는 aaba가 없다. 

5-1) 문자열 전체에서 aaba가 있는지 확인한다. aaba가 없다. 

6) aabc, aabd 등을 동일하게 확인한다. 


● 이 방식은 풀이방법 1과 비교할 때, 검색 횟수가 현저하게 줄어든다. 문자열이 랜덤하게 만들어진다는 가정하에 a는 여러번 나오겠지만, aa는 그 숫자가 적어질 것이고, aaa는 훨씬 적을 것이기 때문이다. 



   최상의 풀이  
 

● 답이 되는 풀이도 속도 문제는 있다. aaa가 있는지 확인을 첫번째 a의 인덱스 뒤로는 다 해야 하기 때문이다. 즉, 예를 들어, 주어진 문자열이 aac로 시가된다면, aab 가 있는지 aad가 있는지 문자열 전체를 검사하는 작업을 계속 반복하게 된다. 


● 이 검색 시간을 줄이기 위해서 각 알파벳에 대한 해시를 만들어 놓으면 검색 시간을 대폭 단축시킬 수 있다. 헤시 인덱스를 한단어로 만들어도 되고 두 단어로 만들어도 된다. 두 단어 이상으로 만들면 오히려 효율이 떨어질 것으로 예상된다. 주어진 문자열이 일정길이 이상일 때만 헤시 테이블을 만드는 작업을 수행하는 식으로 프로그램을 완성하면 효율적인 검색이 가능하다. 


● 헤시테이블은 간단한 이중배열로 만들 수 있다. int hash[26][10] 정도로 만들어서, 각각의 알파벳의 10번째 나오는데까지 위치만 미리 기억해놔도 문제가 쉬워진다. 워스트케이시를 대응하기 위해서는 int hash[26][1000] 이 되어야 하는데 이는 메모리 낭비가 심하다.  또는 int hash2[26*26][10] 으로 만들수도 있는데 - (aa ~ zz) 이 경우 해시를 만드는데는 시간이 더 걸리겠지만, 검색 속도는 월등히 빨라질 수 있다. 



   예제 코드  
 

● 추후 업데이트할 예정이다.








'Exercise & Quizz > C' 카테고리의 다른 글

사전 순으로 단어 정렬하기  (0) 2014.07.19
빙고 게임 - 연속되는 숫자 찾기  (0) 2012.06.11
Posted by 지그프리드 지그프리드

댓글을 달아주세요:: 네티켓은 기본, 스팸은 사절

문제 : 0~9까지의 정수가 10x10 으로 랜덤하게 배열되어 있다. 가로, 세로, 대각선으로 연속되는 숫자의 갯수를 찾아서, 가장 많이 연속되는 숫자를 출력하라.

 

  흔히 "빙고" 게임으로 불리는, 랜덤하게 배열된 숫자에서 연속된 숫자를 체크하는 문제이다. 가로, 세로 외에 대각선이 두 방향이 있다는 점을 주의할 것. 


  c의 이중배열은 배열은 실제로 손으로 숫자를 나열한 경우와 x, y 좌표가 반대이다. 이 부분은 직접 손으로 해보고 신중하게 검토해 볼 것. 아주 잘 헛갈리는 문제이다. 


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUMBER 10
#define SIZE 10
int test[SIZE][SIZE];
int answerList[MAX_NUMBER];

int getAnswer(int game[SIZE][SIZE], int maxNumber);
int checkTopDown(int game[SIZE][SIZE], int px, int py, int maxNumber);
int checkLeftRight(int game[SIZE][SIZE], int px, int py, int maxNumber);
int checkLeftTopRightDown(int game[SIZE][SIZE], int px, int py, int maxNumber);
int checkRightTopLeftDown(int game[SIZE][SIZE], int px, int py, int maxNumber);

int main(void) 
{
	int i,j;

	/* Init game */
	srand ( time(NULL) );

	for (i = 0; i < SIZE; i++)
	{
		for (j = 0; j < SIZE; j++)
		{
			test[i][j] = rand() % MAX_NUMBER;
		}
	}

	/* print test */
	for (i = 0; i < SIZE; i++)
	{
		for (j = 0; j < SIZE; j++)
		{
			printf("%d", test[i][j]);
		}
		printf("\n");
	}
	printf("\n");
				
	/* init answerList */
	for (i = 0; i< MAX_NUMBER; i++)
	{
		answerList[i] = 0;
	}

	printf ("Longest Number is %d.", getAnswer(test,MAX_NUMBER));

	return 0;	
}

int getAnswer(int game[SIZE][SIZE], int maxNumber)
{
	int i, j;
	int biggestNumber = -1;
	int longestArray = -1;

	for (i = 0; i < SIZE; i++)
	{
		for (j = 0; j < SIZE; j++)
		{
			checkTopDown(game, i, j, maxNumber);
			checkLeftRight(game, i, j, maxNumber);
			checkLeftTopRightDown(game, i, j, maxNumber);
			checkRightTopLeftDown(game, i, j, maxNumber);
		}
	}

	/* Return biggest number */
	for (i = 0; i < MAX_NUMBER; i++)
	{
		if (longestArray <= answerList[i])
		{
			biggestNumber = i;
			longestArray = answerList[i];
		}
	}

	return biggestNumber;
}

int checkTopDown(int game[SIZE][SIZE], int px, int py, int maxNumber)
{
	int i;
	int result = 1;

	if ((py -1 >= 0) &&  (game[py][px] == game[py-1][px]))
		return 0;

	for (i = py; i < SIZE - 1; i++) 
	{
		if (game[i][px] == game[i+1][px])
		{
			result++;
		}
		else
		{
			break;
		}
	}

	if (answerList[game[py][px]] < result)
	{
		answerList[game[py][px]] = result;
	}

	return result;
}

int checkLeftRight(int game[SIZE][SIZE], int px, int py, int maxNumber)
{
	int i;
	int result = 1;

	if ((px -1 >= 0) && (game[py][px] == game[py][px-1]))
		return 0;

	for (i = px; i < SIZE - 1; i++) 
	{
		if (game[py][i] == game[py][i+1])
		{
			result++;
		}
		else
		{
			break;
		}
	}

	if (answerList[game[py][px]] < result)
	{
		answerList[game[py][px]] = result;
	}

	return result;
}

int checkLeftTopRightDown(int game[SIZE][SIZE], int px, int py, int maxNumber)
{
	int i;
	int j = 0;
	int result = 1;

	if ((px -1 >= 0) && (py -1 >= 0) && (game[py][px] == game[py-1][px-1]))
		return 0;

	for (i = px; i < SIZE - 1; i++) 
	{
		if (game[py+j][px+j] == game[py+j+1][px+j+1])
		{
			result++;
			j++;
		}
		else
		{
			break;
		}
	}

	if (answerList[game[py][px]] < result)
	{
		answerList[game[py][px]] = result;
	}

	return result;
}

int checkRightTopLeftDown(int game[SIZE][SIZE], int px, int py, int maxNumber)
{
	int i;
	int j = 0;
	int result = 1;

	if ((px + 1 < SIZE-1) && (py -1 >= 0) && (game[py][px] == game[py-1][px+1]))
		return 0;

	for (i = px; i < SIZE ; i++) 
	{
		if (px - i < 0)
		{
			break;
		}
		else if ((px-j-1 > 0) && (py+j+1 < SIZE) && (game[py+j][px-j] == game[py+j+1][px-j-1]))
		{
			result++;
			j++;
		}
		else
		{
			break;
		}
	}

	if (answerList[game[py][px]] < result)
	{
		answerList[game[py][px]] = result;
	}

	return result;
}

#define을 이용하여 사이즈와 숫자 범위를 조정할 수 있도록 했고, 랜덤하게 만들어진 문제를 출력해서 쉽게 비교해볼 수 있도록 했다. 다시 말하지만, x, y 좌표과 실제로 출력되는 x, y는 x,y 순서쌍이 바뀌어 있음을 유의할 것.


'Exercise & Quizz > C' 카테고리의 다른 글

사전 순으로 단어 정렬하기  (0) 2014.07.19
빙고 게임 - 연속되는 숫자 찾기  (0) 2012.06.11
Posted by 지그프리드 지그프리드

댓글을 달아주세요:: 네티켓은 기본, 스팸은 사절


BLOG main image
일상, 프로그래밍, IT 그리고 직장생활, Dive, 여행 by 지그프리드

카테고리

Class List (402)
Studies (30)
Exercise & Quizz (10)
Term Project (0)
ECIM list (Help!) (10)
Issues & News (0)
Gossip about IT & Job (22)
Tools (2)
Think about the Justice (23)
Book Review (170)
조엘 온 소프트웨어(번역) (28)
Diary (87)
Vacations (9)
Clash of clans 클래시 오브.. (11)

글 보관함

달력

«   2020/02   »
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
Total : 316,428
Today : 11 Yesterday : 13