[C++] 백준 10815번 숫자 카드

도서관 3일차...

 

문제를 찾아보다가 예전에 풀었던 문제가 보였다.

그런데 지금은 기억이 안 나고 자바로 풀었던 것이라서 다시 풀어보려고 한다.

 

문제

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

10815번: 숫자 카드

 

상근이의 카드를 입력받고 다음에는 상근이가 가지고 있는지 궁금한 카드를 입력받는다. 내 생각에는 vector와 pair를 이용하여 처음에는 0을 삽입한 후 가지고 있으면 1을 증가시키면 될 것 같다. 그리고 상근이가 가지고 있는 카드를 오름차순으로 정렬한 후 이분 탐색을 통해 카드가 있는지 확인하면 되겠다(이분 탐색을 하기 전 정렬은 필수)!

 

푸는데 또 바보같은 실수를 했다. 이것때문에 시간을 한참 잡아먹었네...

 

// 실수한 부분 코드

for (int i = 0; i < m; i++) {
		start = 0;
		end = n - 1;
		mid = (start + end) / 2;
		while (start<end) {
			if (card[i].first > s_card[mid]) {
				start = mid;
				mid = (end + mid)/2;
			}
			else if (card[i].first == s_card[mid]) {
				card[i].second++;
				break;
			}
			else if (card[i].first < s_card[mid]) {
				end = mid;
				mid = (start+mid)/2;
			}
			
		}
 }

이분 탐색을 해주는 부분에서 중간 인덱스 값인 mid를 다시 계산해줄때 start와 end를 이용하면 되는데 mid를 이용해서 잘못된 값이 나왔다. 게다가 시작 인덱스와 끝 인덱스인 start와 end를 옮길 때 mid로 옮겨주는 것이 아닌 각각 mid+1과 mid-1로 해주어야 한다. 왜냐하면 mid는 이미 비교해본 원소이기 때문에 그것의 오른쪽이나 왼쪽이 시작점 또는 끝점이 되어야한다. 그리고 mid를 그때마다 다시 계산할 필요없이 while위에 있는 'mid = (start + end) / 2;' 이것을 while문 안에 포함시켜주면 되는 것이다!! 그러면 굳이 if 문 안에 적을 필요가 없어진다.(while의 조건에서 start<=end 로 해야하는데 또 =은 안 적어주었다...예전에도 그랬는데...꼭 기억하자!!!!)

 

 

그러면 다시 고쳐보면 다음과 같은 코드가 나온다.

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

vector<int> s_card; //상근이가 가지고 있는 카드

int main() {
	int a,n, m, num, mid=0;
	vector<pair<int,int>> card;	//주어진 카드(상근이가 과연 가지고 있을까??)
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		s_card.push_back(a);
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> num;
		card.push_back(make_pair(num, 0));
	}
	sort(s_card.begin(), s_card.end()); //상근이의 카드를 오름차순으로 정렬

	int start, end;

	for (int i = 0; i < m; i++) {
		start = 0;	//비교할 처음
		end = n - 1;	//비교할 끝
		while (start<=end) {
			mid = (start + end) / 2;	// 중간값
			if (card[i].first > s_card[mid]) {
				start = mid+1;
			}
			else if (card[i].first == s_card[mid]) {
				card[i].second++;
				break;
			}
			else if (card[i].first < s_card[mid]) {
				end = mid-1;
			}
			
		}
		
		
	}
	for (int i = 0; i < m;i++) {
		cout << card[i].second << " ";
	}
	

	return 0;
}

 

이렇게 하면 맞았다고 나온다 ㅠㅠ

 

 

 

오늘은 집중이 안돼서 오래 생각했더니 머리 아프다...

그래도 마무리 단계는 진행해야지...

 

다른 분들은 어떻게 풀었을까 Time~~

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

...

 

슬퍼...

 

 

 

ㅎㅎㅎ... C++에서 binary_search()를 제공한다는 것을 까먹고 있었다... 분명히 옛날에 봤는데;

뭐...이렇게 배워...가는..거..겠지...?(잘 모르니 몸이 고생하는군)

다음번에는 꼭 생각해야지...!

#include<iostream>
#include<algorithm>

using namespace std;

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

    int M, N, num;

    cin >> M;
    int *arr = new int[M];
    for(int i = 0; i < M; i++){
        cin >> arr[i];
    }
    
    sort(arr, arr + M);

    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> num;
        if(binary_search(arr, arr + M, num)){
            cout << '1' << ' ';
        }
        else{
            cout << '0' << ' ';
        }
    }
}
출처: https://infjin.tistory.com/19

이렇게 코드가 간단하구나... 코드가 너무 깔끔해보여서 부러웠다.

카드의 수가 최대 50만으로 잡혀있기 때문에 이 분도 비교할 때 탐색 시간을 줄이기 위해 이분 탐색을 사용하셨다.

binary_search(배열 시작, 배열 끝, 찾는 요소) 함수의 리턴 타입은 boolean이라고 한다. 저렇게 하니까 pair로 해서 하나하나 체크해주고 마지막에 다 출력해주는 것보다 깔끔한 것 같다.

 

 

 

 

또 다른 분은 이중 for 문으로 접근하게 되면 O(n^2)가 되어 시간 안에 통과하지 못하기 때문에 다음과 같이 코드를 작성했다고 한다.

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

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int len, temp;
    vector<int> v;
    cin >> len;
    
    while (len--) {
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(), v.end());
    cin >> len;
    while (len--) {
        cin >> temp;
        cout << binary_search(v.begin(), v.end(), temp) << ' ';
    }
    
}
출처: https://codejin.tistory.com/128

이 분은 개수를 --로 줄여주며 while문을 돌려주었다. 그리고 위에 분과 마찬가지로 binary_search()를 통해 이분 탐색을 하여 바로 출력했다.

 

 

 

 

 

 

오늘의 교훈...

 

풀었던 거라고 안 보지 말자

 

 

그럼 마무리~~~~

 

 

 

 

 

아! 마지막으로 이 분은 처음보는 방법으로 풀어서 참고로 넣어봐야겠다.

https://www.gigong.io/2022/11/09/baekjoon-10815-cpp