BOJ_10815 숫자 카드 c++_머지소트,이진탐색 과 코드를 앞으로 어떻게 짜야 할지 와 내 오답노트.

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

10815번: 숫자 카드

시행착오: 

 

이 밑에 코드처럼 동적으로 배열을 두개 파고 하려 그랬으나

멍청한 짓이라는걸 깨닫는데 세시간이 걸렸고

이 기억들이 그대로 남은 상태로 전역변수를 선언해버리고

그다음날 어디까지한지 기억이 안나서 새로 코드를 짜고

그 새로 짠 코드랑 어제 짠 코드가 헷갈려서

개판이 났다.

아래 코드를 보면 알겠지만

진짜개판임.

다음엔 끝내기전엔 잠을 자지 말던가 해야겠다.

/*
//https://www.acmicpc.net/problem/10815
#include <iostream>
using namespace std;
int *sorted;

void merge(int arr[], int left, int mid, int right){
    int i, j, k;
    i = left;
    j = mid + 1;
    k = left;
    while(i <= mid && j <= right){
        if(arr[i] <= arr[j]){
            sorted[k++] = arr[i++];
        }
        else{
            sorted[k++] = arr[j++];
        }
    }
    if(i > mid){
        for(int q = j; x <= mid; x++){
            sorted[k++] = arr[x];
        }
    }
    else{
        for(int w = i; w<= mid; w++){
            sorted[k++] = arr[x];
        }
    }
    for(int x = left; x <=right; x++){
        arr[x] = sorted[x];
    }
}

void mergesort(int arr[], int left, int right){
    int mid;
    if(left < right){
        mid = (left + right)/2;
        mergesort(arr, left, mid);
        mergesort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}
int main(){
    int n, m, *arrA, *arrB;
    cin >> n;
    arrA = new int[a];
    arrB = new int[b];
    for(int i = 0; i < n ; i++){
        cin>>arrA[i];
    }
    cin >> m;
    for(int j = 0; j < m ; j++){
        cin>>arrB[i];
    }
    mergesort(arrA, 0, n-1);
    mergesort(arrB, 0, m-1);

    for(int i = 0; i < m; i++){
        int first = 0;
        int end = n - 1;

        while(first <= end){
            int mid = (first + end) / 2;
            if(arrA[mid] == b[i]){
                sorted[i] = 1;
                break;
            }
            if(a[mid] > b[i]){
                end = mid - 1;
            }
            else{
                first = mid + 1;
            }
        }
    }
    for(int i = 0; i < m ; i++){
        cout << sorted[i] << ' ';
    }
    cout << '\n';
    return 0;
}
*/

 

 

 

 

 

 

 

어려웠따. 어려운문제는 아녔는데 어려웠따

머리속에 정리좀 하고 풀껄.

오답토느 :
1. 포인터만 띡 만들어두고 아무것도 안했음.
-> 선언을 했으면 할당을 하던가 합시다.

int *sorted; 했으면
main에서
sorted = new int[];

2. 디버깅 breakpoint 잡고 할것
->이건 잊어먹었으니까 나중에 다시 해보겠음.

3.포문마다 첨자 여러개쓰지말것.
->포문끝내면 초기화 하니까 하나만 쓸것.

4. 배열 크기 잘 만들고

5. 주석 잘 달아두기.

6. 마지소트할때 처음은 0이 아닙니다.
-> 처음이라고 생각한 변수에 처음값 위치 잘 잡아주기

7. 전역할꺼면 전역만 하고 지역 할꺼면 지역만 하기.

8.그냥 값 찾아오는 함수면 그냥 리턴해버리는게 빠르고 편함.

9. 일단 함수 틀 만들고 함수의 역할 생각할것.
->딴짓하지말기, 얘는 뭘 받아서 뭘 검색을 해서 돌려줘야지 가상으로 생각하기.

10.  배열 크기 n 이라고 하면 선언하자마자 받아서 초기화해주기. 
->안하면 또 쓰레기값들어가있음.

11. 메인부터 시작하는데 메인부터 디버깅할것.

12. 문제에서 요구하는대로 출력할것.

13. 전역은 할꺼면 꼭 꼭 꼭 기억할것.

14. 백만개 넘어가면 동적으로.

15. 입력순서 바꾸지말것.

16.        ios_base::sync_with_stdio(false); cin.tie(NULL)
--> 하면 빨라짐. 차이 개큼.

상근이 카드수 입력받고 배열에 넣고

문제 카드수 입력받고 배열에 넣고

겹치면 1 아니면 0 출력하는 문제이다.

 

시간이 짧기 때문에 넣는건 문제가 아닌데 빠르게 찾아야한다. 이진탐색으로 찾는게 제일 빠르고. 이진탐색을 쓰기 위해서는 정렬을 해 두어야 하는 문제이다. 여기서 나는 마지소트로 정렬하였다.

 

//https://www.acmicpc.net/problem/10815
#include <iostream>
using namespace std;
int *sorted;
int *answer;
int arr[50]; //상근이 숫자카드
int n, m;

void merge(int arr[], int left, int mid, int right){
    int i, j, k;
    i = left;
    j = mid + 1;
    k = left;
    while(i <= mid && j <= right){
        if(arr[i] <= arr[j]){
            sorted[k++] = arr[i++];
        }
        else{
            sorted[k++] = arr[j++];
        }
    }
    if(i > mid){
        for(int q = j; q <= right; q++){
            sorted[k++] = arr[q];
        }
    }
    else{
        for(int w = i; w<= mid; w++){
            sorted[k++] = arr[w];
        }
    }
    for(int x = left; x <=right; x++){
        arr[x] = sorted[x];
    }
}

void merge_sort(int arr[],int left,int right){
	if (left<right){
		int mid = (left+right)/2;
		merge_sort(arr,left,mid);
		merge_sort(arr,mid+1,right);
		merge(arr,left,mid,right);
	}
}

int search(int key){
    int first = 0;
    int end = n-1;
    int mid = 0;
    int ret = 0;

    while(first <= end){
        mid = (first + end)/2;
        if(key == arr[mid]){
            ret = 1;
            break;
        }
        else{
            if(key < arr[mid]){
                end = mid -1;
            }
            else{
                first = mid + 1;
            }
        }
    }
    return ret;
}

int main(){
    cin >> n;
    sorted = new int[n];

    int arrA[50] = {0,};//문제의 숫자카드
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    cin >> m;
    answer = new int[m];
    for(int j = 0; j < m; j++){
        cin >> arrA[j];
    }
    merge_sort(arr, 0, n-1);

    for(int k = 0; k < m; k++){
        answer[k] = search(arrA[k]);
    }
    for(int q = 0; q < m; q++){
        cout << answer[q] << " ";
    }
    delete sorted;
    delete answer;
    return 0;
}

//https://www.acmicpc.net/problem/10815
#include <iostream>
using namespace std;
int *sorted;
int *answer;

전역배열로 sorted랑 answer를 선언해준다. 사이즈는 main에서 지정해준다.

int n, m;

전역변수로 n,m도 해준다.

void merge(int arr[], int left, int mid, int right){
    int i, j, k;
    i = left;
    j = mid + 1;
    k = left;
    while(i <= mid && j <= right){
        if(arr[i] <= arr[j]){
            sorted[k++] = arr[i++];
        }
        else{
            sorted[k++] = arr[j++];
        }
    }
    if(i > mid){
        for(int q = j; q <= right; q++){
            sorted[k++] = arr[q];
        }
    }
    else{
        for(int w = i; w<= mid; w++){
            sorted[k++] = arr[w];
        }
    }
    for(int x = left; x <=right; x++){
        arr[x] = sorted[x];
    }
}

void merge_sort(int arr[],int left,int right){
if (left<right){
int mid = (left+right)/2;
merge_sort(arr,left,mid);
merge_sort(arr,mid+1,right);
merge(arr,left,mid,right);
}
}

int search(int key){ //이진탐색부분이다.
    int first = 0;
    int end = n-1;
    int mid = 0;
    int ret = 0; //RET변수를 추가해주어서 만약 찾을 경우 RET를 1로 만들어 반환한다.
    while(first <= end){
        mid = (first + end)/2;
        if(key == arr[mid]){
            ret = 1;
            break;
        }
        else{
            if(key < arr[mid]){
                end = mid -1;
            }
            else{
                first = mid + 1;
            }
        }
    }
    return ret;
}

int main(){
    cin >> n;
    sorted = new int[n];
 
    int arr[50]; //상근이 숫자카드
    int arrA[50] = {0,};//문제의 숫자카드
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    cin >> m;
    answer = new int[m];
    for(int j = 0; j < m; j++){
        cin >> arrA[j];
    }
    merge_sort(arr, 0, n-1);

    for(int k = 0; k < m; k++){
        answer[k] = search(arrA[k]); //만약 1이면 바로 들어가게 된다.
    }
    for(int q = 0; q < m; q++){
        cout << answer[q] << " "; //그렇게 해서 그냥 이걸 출력만 해주면 끝난다.
    }
    delete sorted;
    delete answer;
    return 0;
}

 

그리고 앞으로 코드를 짤 때에는...

이렇게 짜도록 해야겠다.

 

#define For(i,n) 이렇게 정의해서 사용하면 빠르고 편리해 보인다.

 

메인부터 시작을 하도록 하고.

메인에 크게 세개가 들어간다.

input

process

output

그러고 이렇게만 해두고 메인에서는 호출만한다.

에러나니까 맨 위에 선언만 해주고

다음부터 짤 때엔 이렇게 짜보도록 해야겠다.

#include <iostream>
using namespace std;
#define For(i,n) for(int (i)=0;(i)<(n);(i)++)

// global variables
int n, m;
int *card, *question;
int *sorted;

// function prototypes
void input();
void solve();
void output();

void merge_sort(int left, int right);
void merge(int left, int mid, int right);
int search(int key);

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

    input();
    solve();
    output();

    return 0;
}

void input() {
    cin >> n;
    card = new int[n];
    For(i, n) {
        cin >> card[i];
    }

    cin >> m;
    question = new int[m];
    For(i, m) {
        cin >> question[i];
    }
}

void solve() {
    sorted = new int[n];
    merge_sort(0, n-1);
    //delete [] sorted;
}

void output() {
    For(i, m) {
        cout << search(question[i]) << " ";
    }
}

void merge_sort(int left, int right) {
    int mid;
    if(left<right) {
        mid = (left+right)/2;
        merge_sort(left, mid);
        merge_sort(mid+1, right);
        merge(left, mid, right);
    }
}

void merge(int left, int mid, int right) {
    int i,j,k;
    i = k = left;
    j = mid+1;

    while(i<=mid && j<=right) {
        if(card[i]<=card[j])
            sorted[k++] = card[i++];
        else
            sorted[k++] = card[j++];
    }
    if(i>mid) {
        for(int x=j;x<=right;x++) {
            sorted[k++] = card[x];
        }
    }
    else {
        for(int x=i;x<=mid;x++) {
            sorted[k++] = card[x];
        } 
    }
    for(int x=left;x<=right;x++) {
        card[x] = sorted[x];
    }
}

int search(int key) {
    int mid;
    int left = 0;
    int right = n-1;
    int ret = 0;
    while(left<=right) {
        mid = (left+right)/2;
        if(card[mid] == key) {
            ret = 1;
            break;
        }
        else {
            if(key < card[mid])
                right = mid-1;
            else
                left = mid+1;
        }
    }
    return ret;
}