[백준 1620]-나는야 포켓몬 마스터 이다솜(C++)/이진탐색, 숫자여부

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

1620번: 나는야 포켓몬 마스터 이다솜

 

이 문제에서 배운것은 문자열-숫자 변환, 이진탐색이다. 이진탐색은 이론은 알고 있었는데 사용할 생각을 자꾸 못하는 것 같다.

 

문자열과 숫자

우선 입력받은 값이 숫자인지 숫자가 아닌지 판정을 해야 했는데 그러기 위해 함수를 하나 만들었다. isdigit()함수를 이용했다.

//isdigit( [char형 문자] ) -> 해당 문자가 숫자인지 아닌지 리턴해준다.

bool isNumber(string str) {
	for (auto k : str) {
		if (isdigit(k) == false) {
			return false;
		}
	}
	return true;
}

또 값을 문자열(string)에 입력받아 이게 숫자면 나중에 int형으로 바꿔주었는데 그건 아래와 같이 하면 된다.

atoi()함수와 c_str()함수를 이용했다.

atoi => char to int
atof => char to float
atol => char to long int

c_str => string의 첫번째 문자의 주소값 반환. char *형 반환

즉 string형의 자료형을 c_str()로 char* 형으로 바꿔준 후, 이를 atoi함수의 인자로 받아 int형으로 바꿔주는 것이다.

아래와 같이 사용한다.

string question="12";
int num=atoi(question.c_str());

//13
cout<<num;

 

이진탐색

이진탐색은 쉽게 말해서 오름차순으로 정렬된 데이터에서 찾으려는 값과 중간 값을 비교하며 값을 찾아 나가는 것이다. 일반적인 예시가 배열이니 정렬된 배열에서 값을 찾는다고 가정하자. 아래는 간단하게 구현한 예시이다.

#include<iostream>
using namespace std;

//아래 배열에서 7을 찾는 예제
int arr [10]= { 1,2,3,4,5,6,7,8,9,10 };

int main() {
	//찾을 값 범위 중 첫번째 인덱스, 마지막 인덱스의 위치이다.
	int low = 0;
	int high = 9;

	int ans = 7;
	//몇번만에 찾는지 확인하기 위함
	int count = 0;

	int mid = 0;
	while (low <= high) {
		count++;
		mid = (low + high) / 2;

		if (arr[mid] < ans) {
			low = mid + 1;
		}
		else if (arr[mid > ans]) {
			high = mid - 1;
		}
		if (arr[mid]==ans) {
			cout << count << "번 만에 찾았습니다!";
			break;
		}
		
	}


}

 

아래 블로그에 더욱 다양한 방법이 있다.

https://blockdmask.tistory.com/167

[탐색] 이진탐색 (Binary Search) 구현 방법

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define P pair<string,int>
using namespace std;

string arr[100001];
vector<P> vec;

bool isNumber(string str) {
	for (auto k : str) {
		if (isdigit(k) == false) {
			return false;
		}
	}
	return true;
}

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

	int N, M;
	cin >> N >> M;
	vec.push_back(P("", 0));
	for (int i = 1; i <= N; i++) {
		string name;
		cin >> name;
		arr[i] = name;
		vec.push_back(P(name, i));
	}

	sort(vec.begin(), vec.end());
	



	string question;
	for (int i = 0; i < M; i++) {
		cin >> question;
		//입력값이 숫자면, 해당 인덱스에 있는 값 가져옴
		if (isNumber(question)) {
			int num = atoi(question.c_str());
			cout << arr[num] << "\n";
		}
		else {
			//입력값이 문자열이면 이진탐색으로 값 찾음(그냥 찾으면 시간초과)
			int low = 1;
			int high = N;
			int mid = (low + high) / 2;
			while (low <= high) {
				mid = (low + high) / 2;
				if (vec[mid].first == question) {
					cout << vec[mid].second << "\n";
					break;
				}
				else if (question > vec[(low + high) / 2].first) {
					low = mid+1;
				}
				else {
					high = mid-1;
				}
			}
			
		}
	}

	
}