글 읽기 - 이분탐색 시간초과 질문

compa513 4년 전 0

M의 입력이 숫자로 들어오는 경우와 문자열로 들어오는 경우 나눠서 생각했습니다

숫자로 들어오는 경우: string배열에서 인덱스 바로 탐색후 출력

문자로 들어오는 경우: 포켓몬 이름과 도감 순서를 같이 저장한 구조체 배열을 알파벳 오름차순으로 정렬하여 이분탐색후 출력

이분탐색을 적용하여 시간을 단축시켰다고 생각했는데 시간초과가 뜹니다

어디서 더 개선해야할까요?

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;


bool chk_num(string temp) {
	switch (temp[0]){
	case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':
            return true;
	}
	return false;
}

typedef struct pkm {
	string name;
	int num;
}pkm;
pkm pkm_arr[100001];

bool compare(pkm a, pkm b) {
	return a.name < b.name;
}

string str_tmp[100001];
int N, M;

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> str_tmp[i];
		pkm_arr[i].name = str_tmp[i];
		pkm_arr[i].num=i;
	}
	sort(pkm_arr + 1, pkm_arr + N + 1,compare);

	//cout << "\n";for (int i = 1; i <= N; i++) {cout << pkm_arr[i].name << '\n';}

	while (M--) {
		string temp;
		cin >> temp;
		if (chk_num(temp)) {//temp가 숫자
			int num = stoi(temp);
			cout << str_tmp[num] << '\n';
		}
		else {//temp가 문자열
			int start = 1, end = N, mid = (start + end) / 2;
			while (true) {
				if (temp < pkm_arr[mid].name) {
					end = mid;
				}
				else if (temp > pkm_arr[mid].name) {
					start = mid;
				}
				else {
					cout << pkm_arr[mid].num << '\n';
					break;
				}
				mid = (start + end) / 2;
			}
		}
	}
	return 0;
}

bupjae 4년 전 1

이분 탐색이 잘못 작성되었습니다.

입력 데이터:
2 1
Bulbasaur
Ivysaur
Ivysaur


정답:
2


오답:
(시간 초과)

compa513 4년 전 0

조언 감사드립니다.

이분탐색을 수정하여

end=mid-1

start=mid+1로 바꾸어 언급해주신 오류를 해결하였습니다만

계속 시간초과가 뜨네요.

예외처리를 덜해서 무한루프가 도는 것일까요?

아니면 제 이분탐색의 코드가 아직 탐색속도의 개선이 더 필요한 것일까요?

bupjae 4년 전 1

cin 과 cout 를 번갈아가며 사용하면 매번 무거운 연산인 buffer flush 가 발생합니다.

프로그램 시작할 때 cin.tie(nullptr); 를 사용해 보세요

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

문제

문제

출처

ICPC

이분탐색 시간초과 질문

compa513 4년 전 0

bupjae 4년 전 1

compa513 4년 전 0

bupjae 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말