1. 부품 찾기

메모

부품 n개

손님은 m개 종류의 부품을 구매하고싶음

가게 안에 해당 부품 m개가 모두 있는지 Yes or No

알고리즘 및 방법

• 내가 생각한 방법 1

n 입력받고
m 입력받고

n = sorted()      # (중요!!!!!! 이진탐색)

for i in m:
    n안에서 바이너리서치 i
        if 찾았으: ans += 1
if ans == m:
    print("yes")
else:
    print("no")

• 간단한 방법 2

for i in m:
    if i in n:
        ans += 1

if ans == m:
    print("yes")
else:
    print("no")

동빈나 해설

브루트포스로도 풀 수는 있겠지만,
부품 종류가 많거나, 손님이 찾는게 많을 경우 시간복잡도 오래걸릴 수 있따

• 브루트포스로 풀 경우
  • n을 전부 확인하면서 m에 해당하는 값들을 각각 찾는다
  • 그럼 O(M * N)이 걸릴 것이다. (= O(N^2)이나 다름없음)
• 이진탐색으로 풀 경우
  • O(M * logN) 이 걸릴것이다

솔루션 코드

• 문제가 쉽고, 다른거 풀거 많으니 안풀겠음
• 동빈나 코드

---

2. 정렬된 배열에서 특정 수의 개수 구하기

메모

이미 오름차순 정렬된 배열에서

x가 등장하는 횟수 계산해라

단, 시간복잡도가 O(logN)으로 설계하지 않으면 시간초과를 받습니다.

알고리즘 및 방법

biscet 사용하면 될듯

lower_left 찾고, lower_right 찾아서
둘을 빼주면 정답

솔루션 코드 - 내가 푼

• python
  • bisect_left, bisect_right는 원하는 값을 못찾으면
    그 배열의 length값을 리턴하는듯

from bisect import bisect_left, bisect_right

n, x = map(int, input().split())
arr = list(map(int, input().split()))

left = bisect_left(arr, x)
right = bisect_right(arr, x)

print(right - left if right - left > 0 else -1)

솔루션 코드 - 동빈나 cpp

• cpp
  • vector는 lower_bound(), upper_bound() 함수를 제공
    • 파라미터 : bound(v.begin(), v.end(), rightValue);
    • 사용법 : vector<>::iterator a = ~~bound();

#include <bits/stdc++.h>

using namespace std;

// 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
int countByRange(vector<int>& v, int leftValue, int rightValue) {
    vector<int>::iterator rightIndex = upper_bound(v.begin(), v.end(), rightValue);
    vector<int>::iterator leftIndex = lower_bound(v.begin(), v.end(), leftValue);
    return rightIndex - leftIndex;
}

int n, x;
vector<int> v;

int main() {
    // 데이터의 개수 N, 찾고자 하는 값 x 입력받기
    cin >> n >> x;

    // 전체 데이터 입력 받기
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }

    // 값이 [x, x] 범위에 있는 데이터의 개수 계산
    int cnt = countByRange(v, x, x);

    // 값이 x인 원소가 존재하지 않는다면
    if (cnt == 0) {
        cout << -1 << '\n';
    }
    //  값이 x인 원소가 존재한다면
    else {
        cout << cnt << '\n';
    }
}