백준 1920번 : 수 찾기

dldzm·2021년 2월 23일
0

알고리즘 공부

목록 보기
32/42
post-thumbnail

링크 : https://www.acmicpc.net/problem/1920

문제읽기

N까지의 배열이 주어져 있다. X라는 정수가 존재하는지 찾아야 한다.
애초에 배열에 넣을 때 이분트리로 넣고 탐색하면 딱 좋을 것 같다.

코드

  1. Out Of Bounds : 만약 계속 오른쪽 노드로만 쌓인다면? 노드의 갯수는 100000개지만 배열은 그 크기를 2100000+22*100000+2로 가져야 한다.
#include<iostream>
using namespace std;

int arr[100001]{ 0, };
bool full[100001]{ false, };

int main() {
	int N, elem, tmp;
	cin >> N;
    
	for (int i = 0; i < N; i++) {
		cin >> elem;
		tmp = 0;
		while (full[tmp] == true){
			if (arr[tmp] < elem)
				tmp = (2 * tmp) + 2;
			else
				tmp = (2 * tmp) + 1;
		}
		arr[tmp] = elem;
		full[tmp] = true;
	}


	cin >> N;
	for (int j = 0; j < N; j++) {
		cin >> elem;
		tmp = 0;
		while (full[tmp] == true && arr[tmp] != elem) {
			if (arr[tmp] < elem)
				tmp = (2 * tmp) + 2;
			else
				tmp = (2 * tmp) + 1;
		}
		if (arr[tmp] == elem)
			cout << 1 << "\n";
		else
			cout << 0 << "\n";
	}

	return 0;
}
  1. 간단한 struct를 만들어봅시당
    -> 포인터 정리 못해서 error

  2. algorithm 라이브러리의 sort의 힘을 빌려서

#include<iostream>
#include<algorithm>
using namespace std;

int arr[100001];
int main() {
	cin.tie(NULL);
	int N, M, elem;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N);
    
	bool check = false;
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> elem;
		int start = 0, end = N - 1, mid;
		while (start <= end){
			mid = (start + end) / 2;
			if (arr[mid] < elem) {
				start = mid+1;
			}
			else if(arr[mid] > elem){
				end = mid-1;
			}
			else {
				check = true;
				break;
			}
		}
		if (check) {
			cout << "1\n";
			check = false;
		}
		else
			cout << "0\n";
	}
	return 0;
}

분석

아 쉬운건데 왜 시작할 때 1번째 out of bounds를 놓쳤는지 모르겠다. 마지막으로 while (start <= end) 이 조건을 세울 때 mid는 설정하지 않아도 start<=end만 세워준다면 문제 없을 것이라는 것도 잊어버렸다.

그리고 한번 체크된 거 다시 초기화해주는 것. 또 까먹었다.

if (check) {
	cout << "1\n";
	check = false;
}
profile
🛰️ 2021 fall ~

0개의 댓글