[C++] 백준 10816번: 숫자 카드2 #auto, upper_bound & lower_bound

문제

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

10816번: 숫자 카드 2

 

 

1920번 문제와 같은 방식으로 풀면 되는가~? 했더니 아니었다.

우선 코드를 보자면

 

//
//  main.cpp
//  백준 10826
//
//  Created by 신지원 on 2022/07/14.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);cin.tie(0);
    
    int n,m;
    vector<int> v;
    
    cin >> n;
    
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        v.push_back(a);
    }
    
    sort(v.begin(), v.end());
    
    cin >> m;
    for(int i=0;i<m;i++){
        int target, res;
        cin >> target;
        
        int start = 0; int end = n-1;
    
        while(1){
            int mid = (start + end)/2;
                    
            if(start > end){
                res = 0;
                break; // 배열 안에 타겟이 없을 때 break;
            }
                    
            if(v[mid] == target){
                // 다시 이분탐색해서 처음과 끝 찾아줘야 함
            }
                    
            else if(target < v[mid]){
                end = mid-1; //mid 보다 타겟이 작으면 끝값을 옮겨서 mid 작게만들기
            }
                    
            else{
                start = mid + 1; //mid 보다 타겟이 크면 시작값을 옮겨서 mid 크게만들기
            }
        }
                
        cout << res << "\n";
    }

    return 0;
}

 

이렇게 나왔는데 

이 부분이 관건이었다. 해보려고 했는데 for 문과 if 문이 너무 많고 복잡해서 다시 while 문을 이중으로 작성해서 만들어보기로 했다.

 

//
//  main.cpp
//  백준 10826
//
//  Created by 신지원 on 2022/07/14.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);cin.tie(0);
    
    int n,m;
    vector<int> v;
    
    cin >> n;
    
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        v.push_back(a);
    }
    
    sort(v.begin(), v.end());
    
    cin >> m;
    for(int i=0;i<m;i++){
        int target;
        cin >> target;
        
        int start = 0; int end = n-1; int res = 0;
    
        while(start <= end){
            int mid = (start + end)/2;
            if(v[mid] == target){
                int j = 1;
                while(v[mid + j] == v[mid]){
                    res++;
                    j++;
                }
                j=1;
                while(v[mid - j] == v[mid]){
                    res++;
                    j++;
                }
            }
                    
            else if(target < v[mid]) end = mid-1;
            else start = mid + 1;
            
        }
                
        cout << res << "\n";
    }

    return 0;
}

 

잘했다고 생각했는데 x-code 에서는 테스트 값이 잘 안나왔다 ㅠ 그래서 다른 분들의 풀이를 참고했다.

내가 몰랐던 새로운 함수를 이용하여 쉽게 풀이하는 방식이 대부분이었다.

바로바로 upper_bound & lower_bound

 

//
//  main.cpp
//  백준 10826
//
//  Created by 신지원 on 2022/07/14.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);cin.tie(0);
    
    int n,m;
    vector<int> v;
    
    cin >> n;
    
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        v.push_back(a);
    }
    
    sort(v.begin(), v.end());
    
    cin >> m;
    for(int i=0;i<m;i++){
        int target;
        cin >> target;
        
        auto upper = upper_bound(v.begin(),v.end(),target);
        auto lower = lower_bound(v.begin(),v.end(),target);
                
        cout << upper - lower << " ";
    }
    cout << "\n";

    return 0;
}

 

정말 신기하다 어떻게 컴퓨터는 이렇게 똑똑할까?

c언어만 하다가 c++하니까 산업사회에서 정보사회의 격변을 직접 체감하는 기분이 든다.

 

이때 auto 가 무엇일까?

 

정리를 하자면 "auto는 초기화 값에 따라 알아서 데이터 타입을 정해주는 키워드" 입니다. 더 똑똑해,,

 

auto를 사용하면 아래 예제 처럼 변수를 선언할 수 있습니다.

auto a1 = 10;                       // int 타입

auto a2 = 10.0f;                  // float 타입

auto a3 = "c";                      // char 타입

auto a4 = "BlockDMask";    // string 타입

auto a5 = {10, 20, 30};       //int 배열 타입

 

출처: https://blockdmask.tistory.com/384 [개발자 지망생:티스토리]

 

복잡한 타입이나 for 문에 쓰면 좋다고 한다. 

 

1. 매개 변수로 쓰일 수 없다.

2. 멤버변수로 쓰일 수 없다. 리턴은 가능 (templete과 함께 사용해야 의미있음)

 

신기하게도 위에 식에서 auto 를 int 로 바꾸니 실행이 되지 않는다 

이유는 upper_bound & lower_bound 는 int 나 float 이 아닌 주소값 변수이기 때문이다.  thanks to 피준

따라서 포인터 변수를 써야 하는데 그 대신 데이터 값을 알아서 정해주는 auto 를 사용한 것이다.

 

준서가 내가 쓴 블로그를 보고 카톡해줬는데 정말 짜릿한 무언가를 느꼈다.