[C] 백준 - 1339번: 단어 수학

9월 6일(수) - 그리디 알고리즘 (1339번)

1339번: 단어 수학

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 입력으로는 단어의 개수인 N, 그리고 N개의 단어가 주어진다

- for문을 N개만큼 돌려주면서 word[9]에 입력받고, word[ ] - 'A' 값을 인덱스로 받은뒤

  qsort를 통해서 alphabet[ ] 배열을 정렬해주고

  for문을 돌려주면서 max 값을 갱신해준다

- 출력은 최댓값을 갱신해놓은 변수 max를 출력한다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

// 수정 전

int compare(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	if (num1 > num2)
	{
		return 1;
	}
	else if (num1 < num2)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

// 수정 후

int compare(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	return num2 - num1;
}

1. qsort를 위한 compare 함수를 원래 사용하던 함수로 그대로 사용

-> 출력값이 0으로만 나옴

-> 다른 풀이들의 compare 함수 구조를 참고해서 수정

 

-> 230913 수정

-> 그냥 내림차순 정렬인 내용이다...복습하다보니까 왜 저번주에 내림차순 정렬인지를 못봤던건지;;

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

/*
int compare(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	return num2 - num1;
}
*/

int compare(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	if (num1 < num2)
	{
		return 1;
	}
	else if (num1 > num2)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int main(void)
{
	int N;
	char word[9];
	scanf("%d", &N);

	int alphabet[26] = { 0, };
	for (int i = 0; i < N; i++)
	{
		scanf("%s", word);

		int len = strlen(word);
		for (int j = len - 1; j >= 0; j--)
		{
			int ch = word[j] - 'A';
			alphabet[ch] = alphabet[ch] + (int)pow(10, (double)len - 1 - j);
		}
	}

	qsort(alphabet, 26, sizeof(int), compare);

	int max = 0;
	for (int i = 0; i < 10; i++)
	{
		max = max + alphabet[i] * (9 - i);
	}

	printf("%d", max);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ