프로그래머스 숫자게임 c++ // 이진탐색, 투포인터

https://school.programmers.co.kr/learn/courses/30/lessons/12987

[프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/12987)

• 처음접근
  • 이분탐색 && visit 이용
  • upper_bound로 초과인 것 선택 -> 그것 제출
  • 문제 : A가 정렬이 아니기때문에 뒤의 작은숫자에대해 B가 점수를 얻는경우를 계산못함.
  • 반례 : A [ 2 2 1]
  • B [ 1 2 3]
  • 3제출 , 1점
  • 2보다 큰 미방문 없음 -> break, 종료
  • 실제정답 : 2점

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    int n = A.size();
    sort(B.begin(),B.end());
    vector<bool> vis(n,false);

    for(auto i : A){
        int idx = upper_bound(B.begin(),B.end(),i)-B.begin();

        // cout<<idx<<" ";
        if(idx>=n){
            break;
        }
        if(vis[idx])
            while(1){
                if(vis[idx]==false) break;
                idx++;
            }
        if(idx>=n){
            break;
        }


        vis[idx]=true;
        answer++;

    }
    return answer;
}

• 해결 : A도 정렬하면 되겠다.

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    int n = A.size();
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    vector<bool> vis(n,false);

    for(auto i : A){
        int idx = upper_bound(B.begin(),B.end(),i)-B.begin();

        // cout<<idx<<" ";
        if(idx>=n){
            break;
        }
        if(vis[idx])
            while(1){
                if(vis[idx]==false) break;
                idx++;
            }
        if(idx>=n){
            break;
        }

        vis[idx]=true;
        answer++;

    }
    return answer;
}

• pos증가시키는 부분을 깔끔하게 정리할수 있을까?
• set을 이용한방법
  • 삽입삭제 모두 logN
  • upper_bound 지원함. (unorederd는 지원안함)
  • but, 시간초과

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> A, vector<int> B) {
    int n = A.size();
    int score = 0;
    set<int> unused(B.begin(), B.end());  // 미사용 숫자들을 set으로 관리

    sort(A.begin(), A.end());

    for(int num : A) {
        auto it = unused.upper_bound(num);  // num보다 큰 첫 번째 미사용 숫자 찾기
        if(it != unused.end()) {
            unused.erase(it);  // 사용한 숫자 제거
            score++;
        }
    }

    return score;
}

N=100,000일 때 각 연산의 시간복잡도를 상세히 계산해보겠습니다:

1. 초기화 단계:
2. set<int> unused(B.begin(), B.end()); // N개 원소를 set에 삽입 // 각 삽입은 O(log N) // 총 N * log(100,000) = 100,000 * log(100,000) ≈ 100,000 * 16.61 ≈ 1,661,000 연산
3. A 정렬:
4. sort(A.begin(), A.end()); // O(N log N) // 100,000 * log(100,000) ≈ 1,661,000 연산
5. 메인 루프:
6. for(int num : A) { // N번 반복 = 100,000번 auto it = unused.upper_bound(num); // O(log N) ≈ 16.61 if(it != unused.end()) { unused.erase(it); // O(log N) ≈ 16.61 score++; } } // 총 100,000 * (16.61 + 16.61) ≈ 3,322,000 연산

총 연산 수:

• 초기화: ≈ 1,661,000
• 정렬: ≈ 1,661,000
• 메인 루프: ≈ 3,322,000
• 총 합: ≈ 6,644,000 연산

이는 제한시간인 1초 내에 충분히 실행 가능한 연산량입니다 (보통 1초에 1억 번 정도의 연산 수행 가능).

하지만 실제로 시간초과가 발생하는 이유:

1. set의 red-black tree 재구성 오버헤드
2. 메모리 할당/해제 오버헤드
3. 캐시 미스로 인한 추가 지연

그래서 실제로는 vector와 static 변수를 사용한 방법이 더 효율적입니다:

static int nextPos = 0;  
auto pos = upper_bound(B.begin() + nextPos, B.end(), num) - B.begin();

이 방법은:

1. 추가 메모리 할당/해제 없음
2. 연속된 메모리 접근으로 캐시 효율 좋음
3. 이미 확인한 범위는 다시 검사하지 않음

 

* 개선 : Pointer(nextPos) 사용

• 핵심은 정답을 찾은경우, A도 정렬되었기 때문에 그 이전 index는 탐색할 필요가 없다는 것이다.
• ex) 3의 ub는 6임 -> 중간의 2, 6은 탐색할필요x (다음 8부터 탐색) 
• 3보다 큰 값이 6 -> 다음 탐색은 무조건 3보다 큰값 -> B에서 6다음 부터 찾으면됨.
• 못찾을경우 자동으로 0점으로 간주됨.
•  
• ptr = 찾은 index+1
• 탐색을 begin + ptr 부터 진행하면 된다.
• 방문체크할 필요가 없어진다.

#include <bits/stdc++.h>

using namespace std;

int nextPos; // num보다 큰 가장 작은 미사용 숫자의 위치

int solution(vector<int> A, vector<int> B) {
    int n = A.size();
    int score = 0;
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    for(int num : A) {

        auto pos = upper_bound(B.begin() + nextPos, B.end(), num) - B.begin();
        
        if(pos < n) {
            score++;
            nextPos = pos + 1;
        }
    }
    
    return score;
}

 

 

* 참고 : 투포인터 풀이

• 잘 안와닿는다.. 투포인터
• 이게 이해하기는 더 좋긴하네

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> A, vector<int> B) {
    int n = A.size();
    int answer = 0;
    
    // B팀의 숫자들을 내림차순으로 정렬
    sort(B.begin(), B.end(), greater<int>());
    // A팀의 숫자들을 내림차순으로 정렬
    sort(A.begin(), A.end(), greater<int>());
    
    int left = 0;    // B팀의 가장 큰 수들을 가리키는 포인터
    int right = n-1; // B팀의 가장 작은 수들을 가리키는 포인터
    
    // A팀의 각 숫자에 대해 큰 수부터 처리
    for(int i = 0; i < n; i++) {
        // B팀의 현재 가장 큰 수가 A팀의 수보다 크면
        if(B[left] > A[i]) {
            answer++; // 승점 획득
            left++;   // 다음으로 큰 B팀의 수로 이동
        }
        // A팀의 수가 더 크거나 같으면
        else {
            right--; // B팀의 가장 작은 수 중 하나를 사용
        }
    }
    
    return answer;
}