백준 1339(단어 수학)

jh Seo·2022년 12월 21일
백준백트래킹한번에 푼 문제
0

백준

목록 보기
105/194
post-custom-banner

개요

백준 1339번: 단어 수학

  • 입력
    첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

  • 출력
    첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

접근 방식_map<char, int>

  1. 처음 푼 방식은 map자료구조를 이용한 방식이였다.
    자료형은 <char,int>로 각 알파벳에 숫자를 key-value로 대응하여 구현하였다.
    입력값을 받을 때, map의 중복 key값 insert가 안되는 특성을 이용하여
    모든 단어의 char형 알파벳에 value값 -1 을 넣어주고,
    백트래킹 함수의 재귀를 map의 iterator을 사용하여 구현하였다.
void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> nums[i];
		//각 알파벳값 초기화
		for(char e: nums[i])
			//map에 -1로 넣어주기
			digitNum.insert({e,-1});
	}
	
}


void Backtracking(map<char, int>::iterator iter)
  1. bool used[10] 배열을 통해 0부터 9까지 한번만 사용하게 구현하였다.
for (int i = 0; i <= 9; i++) {
		//i를 이미 다른 알파벳에 할당한 상황이라면 continue
		if (used[i]) continue;
		used[i] = true;
		//현재값 변경해줌.
		digitNum[iter->first] = i;
		Backtracking(++iter);
		//백트래킹 끝나면 iterator와 used배열 다시 초기화
		iter--;
		used[i] = false;
	}
  1. 각 백트래킹에서 모든 알파벳을 숫자로 채웠을 때는 결과값을 계산 후
    maxAns를 갱신해준다.
	//각 백트래킹의 끝단계에서
	if (iter==digitNum.end()) {
		//각 재귀의 끝단계에서의 단어의 합
		int tmpSum = 0;
		//각 단어마다 
		for (int i = 0; i < N; i++) {
			int tmp = 0;
			//i번째 단어의 각 알파벳 e에 대해  
			for (char e : nums[i]) {
				//알파벳 e에 매핑된 숫자를 통해 단어를 숫자로 변경해준 후 더해준다.
				tmp= tmp*10+digitNum[e];
			}
			//각 단어를 수로 변경한 값인 tmp를 총합 tmpSum에 더해줌
			tmpSum += tmp;
		}
		//최대치의 답 갱신해줌
		maxAns = maxAns > tmpSum ? maxAns : tmpSum;
		return;
	}
  1. 만약 알파벳이 하나라면 바로 답 처리해주기 위해
    해당 알파벳에 9를 대입해주고 계산 후 출력하였다.
if (digitNum.size() == 1) {
		digitNum[nums[0][0]] = 9;
		//각 재귀의 끝단계에서의 단어의 합
		int tmpSum = 0;
		//각 단어마다 
		for (int i = 0; i < N; i++) {
			int tmp = 0;
			//i번째 단어의 각 알파벳 e에 대해  
			for (char e : nums[i]) {
				//알파벳 e에 매핑된 숫자를 통해 단어를 숫자로 변경해준 후 더해준다.
				tmp= tmp*10+digitNum[e];
			}
			//각 단어를 수로 변경한 값인 tmp를 총합 tmpSum에 더해줌
			tmpSum += tmp;
		}
		cout << tmpSum;
		return;
	}

접근 방식_배열

  1. 위 방식으로 구현했으나 map의 자료구조 특성상 해당 값을 찾을 때,
    배열처럼 O(1)이 아니라 트리를 search해야하므로
    O(logn)의 시간복잡도라서 채점결과 시간이 좀 많이 걸렸다.

    따라서 map이 아닌 다른 방법을 생각하다가
    알파벳에 'A'를 빼면 해당 알파벳의 인덱스를 나타낼 수 있다는 점에서
    알파벳 26가지값을 다 저장하는 배열 을 사용해서 다시 구현해봤다.

    int digitNumArr[26];

    이 경우에는 백트래킹 함수가 map의 iterator을 순회하는게 아니라
    배열 digitNumArr을 순회하며 단어에 포함된 알파벳값들을
    0부터 9까지 넣어보게 구현하였다.

  2. 단어들을 받기 전에 모든 알파벳을 -1로 초기화해주고
    포함된 알파벳이라면 0을 넣어줘서 구별해주었다.

    void Input() {
	cin >> N;
	//알파벳 배열에 미리 -1값으로 넣어주기
	fill(digitNumArr, digitNumArr + 26, -1);
	for (int i = 0; i < N; i++) {
		cin >> nums[i];
		for (char e : nums[i]) {
			//단어에 포함된 알파벳은 0을 넣어주기
			digitNumArr[e - 'A'] = 0;
		}
	}

}

  3. 백트래킹 함수는 digitNumArr의 index값을 매개변수로 받는다.

    //0부터 25까지 알파벳 전체 백트래킹
void Backtracking(int length) {

  4. 만약 현재 index에 해당하는 알파벳이 단어에 미포함 알파벳이라면
    포함된 알파벳이 나올때 까지 인덱스를 증가시켜줬다.
    하지만 이 부분에서 인덱스가 25를 넘어가버리면 엉뚱한 메모리 읽어오게 되므로 답 계산하고 return해줬다. 

    		//입력값에 포함되어있지 않은 알파벳이면
		if (digitNumArr[length] == -1) {
			//포함된값까지 증가시켜줌
			while (digitNumArr[length] == -1) {
				length++;
           	//만약 이 부분에서 26넘어가면 오류출력하므로 여기서도 26인지 체크해줘야함
				if (length == 26) {
					//각 재귀의 끝단계에서의 단어의 합
					int tmpSum = 0;
					//각 단어마다 
					for (int i = 0; i < N; i++) {
						int tmp = 0;
						for (char e : nums[i]) {
							//현재 각 문자에 해당된 숫자를 통해 단어를 숫자로 변경해준 후 더해준다.
							tmp = tmp * 10 + digitNumArr[e - 'A'];
						}
						tmpSum += tmp;
					}
					//최대치의 답 갱신해줌
					maxAns = maxAns > tmpSum ? maxAns : tmpSum;
					return;
				}
			}

  5. 만약 백트래킹 함수가 반복된 끝에 index가 26인 상황에선
    답을 계산 후 리턴해줬다.

    		if (length==26) {
			//각 재귀의 끝단계에서의 단어의 합
			int tmpSum = 0;
			//각 단어마다 
			for (int i = 0; i < N; i++) {
				int tmp = 0;
				for (char e : nums[i]) {
					//현재 각 문자에 해당된 숫자를 통해 단어를 숫자로 변경해준 후 더해준다.
					tmp= tmp*10+digitNumArr[e-'A'];
				}
				tmpSum += tmp;
			}
			//최대치의 답 갱신해줌
			maxAns = maxAns > tmpSum ? maxAns : tmpSum;
			return;
		}

  6. 나머지 부분은 이제 해당 인덱스의 알파벳값에 숫자를 0부터 9까지
    중복되지 않게 넣어주면서 백트래킹을 진행하면된다.

	for (int i = 9; i >=0; i--) {
		if (used[i]) continue;
		used[i] = true;
		//현재length번째 알파벳에 해당하는 숫자 변경해줌.
		digitNumArr[length] = i;
		//다음 인덱스 백트래킹 진행
		Backtracking(length + 1);
        //백트래킹 빠져나올시 used배열 초기화
		used[i] = false;
	}

map<char, int>사용한 코드

#include<iostream>
#include<map>

using namespace std;

string nums[11];
int N=0,maxAns=0;
//중복 허용 안하는 map으로 선언
map<char, int> digitNum;
//숫자를 사용했는지
bool used[10];

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> nums[i];
		//각 알파벳값 초기화
		for(char e: nums[i])
			//map에 -1로 넣어주기
			digitNum.insert({e,-1});
	}
	
}

void Backtracking(map<char, int>::iterator iter) {
	//각 백트래킹의 끝단계에서
	if (iter==digitNum.end()) {
		//각 재귀의 끝단계에서의 단어의 합
		int tmpSum = 0;
		//각 단어마다 
		for (int i = 0; i < N; i++) {
			int tmp = 0;
			//i번째 단어의 각 알파벳 e에 대해  
			for (char e : nums[i]) {
				//알파벳 e에 매핑된 숫자를 통해 단어를 숫자로 변경해준 후 더해준다.
				tmp= tmp*10+digitNum[e];
			}
			//각 단어를 수로 변경한 값인 tmp를 총합 tmpSum에 더해줌
			tmpSum += tmp;
		}
		//최대치의 답 갱신해줌
		maxAns = maxAns > tmpSum ? maxAns : tmpSum;
		return;
	}

	for (int i = 0; i <= 9; i++) {
		//i를 이미 다른 알파벳에 할당한 상황이라면 continue
		if (used[i]) continue;
		used[i] = true;
		//현재값 변경해줌.
		digitNum[iter->first] = i;
		Backtracking(++iter);
		//백트래킹 끝나면 iterator와 used배열 다시 초기화
		iter--;
		used[i] = false;
	}
}

void Solution() {
	if (digitNum.size() == 1) {
		digitNum[nums[0][0]] = 9;
		//각 재귀의 끝단계에서의 단어의 합
		int tmpSum = 0;
		//각 단어마다 
		for (int i = 0; i < N; i++) {
			int tmp = 0;
			for (char e : nums[i]) {
				//현재 각 문자에 해당된 숫자를 통해 단어를 숫자로 변경해준 후 더해준다.
				tmp = tmp * 10 + digitNum[e];
			}
			tmpSum += tmp;
		}
		cout << tmpSum;
		return;
	}
	Backtracking(digitNum.begin());
	cout << maxAns;
}

int main() {
	Input();
	Solution();
}

배열 사용한 코드

#include<iostream>
#include<map>

using namespace std;

string nums[11];
int N=0,alphabetAmount=0,maxAns=0;
int digitNumArr[26];
//숫자를 사용했는지
bool used[10];

void Input() {
	cin >> N;
	//알파벳 배열에 미리 -1값으로 넣어주기
	fill(digitNumArr, digitNumArr + 26, -1);
	for (int i = 0; i < N; i++) {
		cin >> nums[i];
		for (char e : nums[i]) {
			//단어에 포함된 알파벳은 0을 넣어주기
			digitNumArr[e - 'A'] = 0;
		}
	}

}

//0부터 25까지 알파벳 전체 백트래킹
void Backtracking(int length) {
	//각 백트래킹의 끝단계에서
	if (length==26) {
		//각 재귀의 끝단계에서의 단어의 합
		int tmpSum = 0;
		//각 단어마다 
		for (int i = 0; i < N; i++) {
			int tmp = 0;
			for (char e : nums[i]) {
				//현재 각 문자에 해당된 숫자를 통해 단어를 숫자로 변경해준 후 더해준다.
				tmp= tmp*10+digitNumArr[e-'A'];
			}
			tmpSum += tmp;
		}
		//최대치의 답 갱신해줌
		maxAns = maxAns > tmpSum ? maxAns : tmpSum;
		return;
	}
	//입력값에 포함되어있지 않은 알파벳이면
	if (digitNumArr[length] == -1) {
		//포함된값까지 증가시켜줌
		while (digitNumArr[length] == -1) {
			length++;
			//만약 이 부분에서 26넘어가면 오류출력하므로 여기서도 26인지 체크해줘야함
			if (length == 26) {
				//각 재귀의 끝단계에서의 단어의 합
				int tmpSum = 0;
				//각 단어마다 
				for (int i = 0; i < N; i++) {
					int tmp = 0;
					for (char e : nums[i]) {
						//현재 각 문자에 해당된 숫자를 통해 단어를 숫자로 변경해준 후 더해준다.
						tmp = tmp * 10 + digitNumArr[e - 'A'];
					}
					tmpSum += tmp;
				}
				//최대치의 답 갱신해줌
				maxAns = maxAns > tmpSum ? maxAns : tmpSum;
				return;
			}
		}
	}

	for (int i = 9; i >=0; i--) {
		if (used[i]) continue;
		used[i] = true;
		//현재length번째 알파벳에 해당하는 숫자 변경해줌.
		digitNumArr[length] = i;
		//
		Backtracking(length + 1);
		used[i] = false;
	}
}

void Solution() {
	Backtracking(0);
	cout << maxAns;
}

int main() {
	Input();
	Solution();
}

문풀후생

확실히 배열을 사용하니 시간이 감소한 걸 볼 수 있었다.

profile
jh Seo
코딩 창고!
이전 포스트

백준1405(미친 로봇)

다음 포스트

백준11659(구간 합 구하기 4)

post-custom-banner

0개의 댓글