h32j00

처음에는 그냥 이중 포문 써서 했는데 시간 초과가 되는 바람에 다시 한번 생각을 해봤습니다.

고려해야할 조건은

1. 정수의 범위 - int 대신 double 사용

2. time limit - 이중포문 대신 qsort(), 이진 탐색 사용

다음은 C언어로 작성한 코드입니다.

#pragma warning(disable : 4996)
#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b)
{
	double ra = *(double*)a;
	double rb = *(double*)b;
	return ra - rb > 0 ? 1 : -1;
}

int main()
{
	double * a, * b;
	int n, m;
	int i, flag = 0;
	int l, r, mi;
	scanf("%d", &n);
	a = (double*)malloc(sizeof(double) * n);
	for (i = 0;i < n;i++) scanf("%lf", &a[i]);
	scanf("%d", &m);
	b = (double*)malloc(sizeof(double) * m);
	for (i = 0;i < m;i++) scanf("%lf", &b[i]);
	qsort(a, n, sizeof(double), compare);
	for (i = 0;i < m;i++) {
		l = 0;
		r = n - 1;
		while (1)
		{
			if (l <= r) {
				mi = (l + r) / 2;
				if (b[i] == a[mi]) { flag = 1;break; }
				else if (b[i] < a[mi]) { r = mi - 1; }
				else if (b[i] > a[mi]) { l = mi + 1; }
			}
			else break;
		}
		if (flag == 1) printf("1\n");
		else printf("0\n");
		flag = 0;
	}
    free(a);
    free(b);
}

배운 점

1. 문제의 조건을 잘보자.

2. qsort() 잘 사용하자.

3. 이진탐색

C언어를 이용하여 코드를 작성하였다.

처음 코드에는 정렬을 할 때, O(n^2)인 정렬을 써서 시간 초과가 나서 검색해보니 

stdlib.h 파일에서 제공하는 qsort()라는 함수를 발견하여 qsort()함수를 이용하여 코드를 작성하였다.

#pragma warning(disable : 4996)
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int len;
	char str[51];
}words;

int compare(const void *a, const void *b) {
	words real_a = *(words*)a;
	words real_b = *(words*)b;
	int len_a = strlen(real_a.str);
	int len_b = strlen(real_b.str);
	if (len_a != len_b)
		return (len_a - len_b);
	return strcmp(real_a.str, real_b.str);
}

int main()
{
	words* word;
	words tmp;
	int flag = 0, real_n = 0;
	char strtmp[51] = {0};
	int n, i, j;
	scanf("%d", &n);
	word = (words*)malloc(sizeof(words) * n);
	for (i = 0;i < n;i++)
	{
		scanf("%s", strtmp);
		for (j = 0;j < i;j++) {
			if (strcmp(word[j].str, strtmp) == 0) {
				flag = 1;
				break;
			}
		}
		if (flag == 0) {
			strcpy(word[real_n].str, strtmp);
			word[real_n].len = strlen(strtmp);
			real_n++;
		}
		flag = 0;
	}
	qsort(word, real_n, sizeof(words), compare);
	for (i = 0;i < real_n;i++) printf("%s\n", word[i].str);
	free(word);
	return 0;
}

입력을 받으면서 이전에 입력 받았던 문자열이면 배열에 추가하지 않게 설정하였다.

qsort()를 사용하기 위해서는 어떤 방식으로 sort를 할 것인지에 대한 함수가 추가적으로 필요한데 여기서는 compare()를 추가적으로 사용하였다.

Compare()

int compare(const void *a, const void *b) {
	words real_a = *(words*)a;
	words real_b = *(words*)b;
	int len_a = strlen(real_a.str);
	int len_b = strlen(real_b.str);
	if (len_a != len_b)
		return (len_a - len_b);
	return strcmp(real_a.str, real_b.str);
}

compare 함수만 따로 살펴보자.

문제에서 요구한 것을 다시 생각해보면 a,b를 비교할 때, 길이가 다르면 (예를 들어 i, no) i가 우선순위가 더 높다. (길이가 짧으니까!!)

우선순위가 높은것이 더 작은 수라고 생각하면 된다.

(음.. 1과 2가 있을때, 우선순위가 1이 먼저지만 수는 1이 더 작은 느낌이랄까)

그래서 len_a - len_b가 음수가 나올것이고 그건 a가 우선순위가 더 높다는 것을 뜻한다. (반대의 경우, 즉 길이가 긴 것이 우선순위가 높을 때에는 len_a - len_b가 양수이기 때문에 우선순위가 낮으니까 (-1)을 곱해준 뒤 return 하면 된다.)

길이가 같을 때에는 사전 순으로 배열이기 때문에 strcmp()함수를 써서 return을 하게 해주었다.

strcmp()은 a,b를 비교해서 a가 작으면 음수를 리턴하기에 딱 알맞게 사용했다고 볼 수 있다.

배운점

1. qsort() 함수를 처음 봤다. 종종 사용해야겠다.

2. 퀵정렬과 힙정렬도 생각해봐야겠다....... 먼 미래에..

문자열에 관련된 문제입니다. 

맨 처음 문자열(예시로 하면 config.sys)을 기준으로 다음 문자열과 비교하여 다르면 '?'로 문자를 바꾸는 식으로 코드를 작성하였습니다.

C를 이용하여 코드를 작성하였습니다.

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

int main(void)
{
    int n, i, j, len;
    
    char a[50][51] = {0};
    char answer[51] = {0};

    scanf("%d", &n);

    for (i = 0; i < n; i++)
        scanf("%s", a[i]);

    len = strlen(a[0]);

    memcpy(answer, a[0], len);

    for (i = 0; i < len; i++)
    {
        for (j = 0; j < n - 1; j++)
        {
            if (a[j][i] != a[j + 1][i])
            {
                answer[i] = '?';
                break;
            }
        }
    }

    printf("%s", answer);

    return 0;
}

배운점

1. 학교에서 항상 void main()으로 했었는데 이것 때문에 컴파일에러가 났다. 컴파일러에 따라 컴파일에러가 난다고 하니 이제는 int main()으로 써야겠다.