글 읽기 - 이 예에 대해 질문 드립니다.

nlkey2022 6년 전 0

2일 동안 고민했는데

일단 알고리즘은 다음과 같습니다.

1. 각 단어의 알파벳을 중복되지 않도록 abc 배열에 삽입
2. 각 알파벳에 대해 Z로 변경한후 각 N개의 수를 모두 더했을때 함수 sum을 이용하여 문자열 값 반환
3. 반환된 값을 따로 저장한 후 vector와  pair을 이용해 사전식으로 정렬
4. k값을 입력 받아 위에서부터 k개 의 문자만 가져와 이를 Z로 바꾸기
 (이때, 각 반환된 합 문자열과 알파벳은 서로 일대일 함수 즉 hashtable와 같은 역할을 한다)
5. Z값으로 변환된 값을 출력

궁금한게 있다면

0000

A000

일때

ZZZZ

AZZZ

1AZZY로 바뀌는게 맞을까요?

EX1)

50
XWW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW

2AYW

E2)

ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ

1DZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZYM

#include <iostream>
#include <cmath>
#include<string>
#include<vector>
#include<algorithm>
#include <cstring>

using namespace std;

int f(char c) {

	if (c == NULL) return 0;

	if ('0' <= c && c <= '9')
		return c - 48;
	else
		return (int)c - 55;
}

char f2(int n) {
	if (0 <= n && n <= 9)
		return (char)(n + 48);
	else
		return (char)(n + 55);
}
int MAX;
// MAX는 최고 숫자 자리수, N은 테스트케이스 갯수
void sum(int N, char words[][60], int length[], char re[]){

	char result[100] = { NULL };


	//for (int i = 0; i < N; i++) cout << words[i] << endl;

	// befor sum
	for (int i = 0; i < N; i++) {
		if (length[i] < MAX) {
			int d = MAX - length[i];
			for (int j = length[i] - 1; j >= 0; j--) {
				words[i][j + d] = words[i][j];
			}
			//cout <<i<<" "<<length[i] << " MAX " << MAX << endl;
			for (int j = MAX - length[i] - 1; j >= 0; j--) {
				words[i][j] = '0';
			}
		}
	}

	int mod = 0;
	// SUM
	for (int i = MAX - 1; i >= 0; i--) {
		int sum = 0;
		for (int j = 0; j < N; j++) {
			sum += f(words[j][i]);
		}
		if (mod != 0) {
			sum = sum + mod;
			mod = 0;
		}
		//cout << i << " sum " << sum << endl;
		if (sum >= 36) {
			mod = sum / 36;
			result[i + 1] = f2(sum % 36);
			if (i == 0) {
				MAX++;
				if (mod >= 36) {
					result[i] = f2(mod % 36);
					mod = mod / 36;
					for (int j = MAX + 1; j >= 1; j--) {
						result[j] = result[j - 1];
					}
					MAX++;
					result[0] = f2(mod);
				}
				else
					result[i] = f2(mod);

			}
		}
		else {
			result[i + 1] = f2(sum);
			if (i == 0) {
				for (int j = 1; j <= MAX; j++) {
					result[j - 1] = result[j];
				}
				result[MAX] = NULL;
			}

		}
	}
	
	int s = 0;
	while (result[s] == '0') {
		s++;
	}

	int l = 0;
	while (result[l] != NULL) l++;

	strcpy(re, result);

}



int main() {

	vector<pair<string, char> > v;

	int N; cin >> N;

	MAX = 0;


	char words[50][60] = { NULL };
	int length[60];

	float calculate[36];
	char abc[36];
	int cal_count = 0;

	for (int t = 0; t < N; t++) {
		char input[51] = { NULL };
		cin >> input;

		int len = 0;
		while (input[len] != NULL) { len++; }

		length[t] = len;

		if (MAX < len) MAX = len;

		for (int i = 0; i < len; i++) {
			words[t][i] = input[i];
			bool find = false;
			for (int j = 0; j < 36; j++) {
				if (abc[j] == input[i]) {
					find = true;
				}
			}
			if (!find) {
				abc[cal_count] = input[i];
				cal_count++;
			}
		}
	}



	for (int i = 0; i < cal_count; i++) {
		char t_word[50][60] = { NULL };
		char output[60];
		calculate[i] = 0;

		for (int i = 0; i < N; i++)
			for (int j = 0; j < length[i]; j++)
				t_word[i][j] = words[i][j];

		for (int x = 0; x < N; x++) {
			for (int y = 0; y < length[x]; y++) {
				if (abc[i] == t_word[x][y])
					t_word[x][y] = 'Z';
			}
		}
		sum(N, t_word, length, output);
		//cout << "MAX : " << MAX << endl;

		v.push_back(pair<string, char>(output, abc[i]));

	}
	int k; cin >> k;

	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	vector<pair<string, char> >::iterator iter;

	char* kc = new char[k];
	int k_c = 0;
	
	for (iter = v.begin(); iter != v.end(); iter++) {

		if (k_c == k) break;

		cout << "[" << iter->first << "," << iter->second << "]" << endl;
		bool find = false;
		for (int i = 0; i < k_c; i++) {
			if (kc[i] == iter->second) {
				find = true;
			}
		}
		if (!find) {
			kc[k_c] = iter->second;
			k_c++;
		}
	}


	for (int i = 0; i < N; i++) {
		for (int j = 0; j < length[i]; j++) {
			for (int k = 0; k < k_c; k++) {
				if (kc[k] == words[i][j]) {
					words[i][j] = 'Z';
				}
			}
		}
	}




	
	cout << endl;
	for (int i = 0; i < N; i++) {
		cout << words[i] << endl;
	}
	

	char output[53];
	sum(N,words,length, output);

	cout << output;
	
	//delete[] alphabet;

	return 0;
}

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

문제

문제

출처

ICPC

이 예에 대해 질문 드립니다.

nlkey2022 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말