1620번-나는야 포켓몬 마스터 이다솜 | 스택 오버플로우 by 지역변수 (C++)

---

문제

---

풀이

입력값이 숫자인 경우와 문자인 경우를 분류해 구하는게 까다로운 부분이다.

 

1. 입력값이 숫자인 경우

  string 배열을 이용해 문자열을 저장해둔다.

  입력을 받을 때 for문으로 0부터 배열에 저장되었기 때문에, -1 을 해주었다.

 

string name[100001];		// 입력이 숫자인 경우에 사용

	if (isdigit(str[0]) != 0) {		// isdigit == 0: 문자 | isdigit != 0: 숫자
			cout << name[stoi(str) - 1] << "\n";		// 입력값: 숫자
	}

 

 

2. 입력값이 문자인 경우

  key값과 value값이 함께 저장되는 map을 이용한다.

  이 문제는 입력값이 많기 때문에 시간 초과를 주의해야 하므로 map을 선택했다.

  

  문자가 입력된 경우, map에서 key 값을 찾아 전달하도록 한다.

  이때, for문으로 0부터 배열에 저장되었기 때문에 +1 을 해주었다.

 

map<string, int> num;

	else {
		cout << num.find(str)->second + 1 << "\n";		// 입력값: 문자
	}

 

 

처음부터, for문을 1부터 m까지 돌도록 하면 -1, +1을 고려하지 않아도 된다.

---

 첫 번째 풀이 _ 스택 오버플로우 발생 (실패) | 지역 변수 name의 크기가 너무 큼

// 스택 오버플로우
#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	string str;
	map<string, int> num;		// 입력이 문자인 경우에 사용
	string name[100001];		// 입력이 숫자인 경우에 사용

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> str;
		num.insert({ str, i });		// num.inset(make_pair(name[i], i))
		name[i] = str;
	}

	for (int i = 0; i < m; i++) {
		cin >> str;

		if (isdigit(str[0]) != 0) {		// isdigit == 0: 문자 | isdigit != 0: 숫자
			cout << name[stoi(str) - 1] << "\n";		// 입력값: 숫자
		}
		else {
			cout << num.find(str)->second + 1 << "\n";		// 입력값: 문자
		}
	}
	
	return 0;
}

 

---

스택 오버플로우

 

위와 같이 '예외가 처리되지 않음'이라는 스택 오버플로우(Stack Overflow)가 발생했다.

 

스택 오버플로우가 발생하는 이유는 다음과 같다.

1. 재귀 호출이 너무 깊어지는 경우
2. 지역 변수나 배열이 너무 커서 스택 메모리를 초과하는 경우

 

num의 배열이 너무 커서 스택 메모리를 초과해서 발생한 스택 오버플로우였다.

이를 해결하기 위해 두 가지 방안을 생각해보았다.

 

1. array가 아닌 vector를 이용하여 동적 할당하기
2. 지역 변수를 전역 변수로 설정해주기

나는 간단히 지역 변수를 전역 변수로 설정해주어 문제를 해결하였다.

---

 

이렇게 해결되는 이유는 전역 변수와 지역 변수의 메모리 할당이 다르기 때문이다.

 

1. 전역 변수
   • 프로그램이 시작될 때 데이터 세그먼트에 할당
   • 따라서, 크기가 커도 스택 메모리 사용량에 영향을 미치지 않음.
2. 지역 변수
   • 함수가 호출될 때 스택 메모리에 할당
   • 지역 변수가 할당되는 스택 메모리는 주로 함수의 호출, 종료마다 할당되고 해제됨.
   • 스택 메모리는 제한된 크기를 가지기 때문에, 재귀 호출이나 큰 지역 변수가 있으면 스택 오버플로우가 발생함.

 

---

 

 두 번째 코드 (성공) | 전역 변수로 설정해 스택 오버플로우 해결

#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;

int n, m;
string str;
map<string, int> num;		// 입력이 문자인 경우에 사용
string name[100001];		// 입력이 숫자인 경우에 사용

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> str;
		num.insert({ str, i });		// num.insert(make_pair(name[i], i))
		name[i] = str;
	}

	for (int i = 0; i < m; i++) {
		cin >> str;

		if (isdigit(str[0]) != 0) {		// isdigit == 0: 문자 | isdigit != 0: 숫자
			cout << name[stoi(str) - 1] << "\n";		// 입력값: 숫자
		}
		else {
			cout << num.find(str)->second + 1 << "\n";		// 입력값: 문자
		}
	}
	
	return 0;
}

 

---

결과

 

https://www.acmicpc.net/problem/1620