[백준] 1822번 차집합

2025. 3. 13. 22:36·백준 문제/이분탐색

문제: 1822번: 차집합

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

 

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

바킹독의 실전 알고리즘 강의 자료. Contribute to encrypted-def/basic-algo-lecture development by creating an account on GitHub.

github.com

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

bool binarySearch(int target, vector<int>& B) {
    int st = 0;
    int en = B.size() - 1;

    while (st <= en) {
        int mid = (st + en) / 2;

        if (B[mid] == target)
            return true;
        else if (B[mid] > target)
            en = mid - 1;
        else
            st = mid + 1;
    }
    // 여기까지 도달하면 false 리턴해
    // A 의 요소가 B 에 존재하지 않아여
    return false;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int nA, nB;
    cin >> nA >> nB;

    vector<int> A(nA);
    vector<int> B(nB);
    for (int i = 0; i < nA; i++)
        cin >> A[i];
    for (int i = 0; i < nB; i++)
        cin >> B[i];

    // 일단 B 오름차순 정렬해
    sort(B.begin(), B.end());
    sort(A.begin(), A.end());

    // 이제 A 를 for 문으로 전체 돌면서 이분탐색해
    // B 에 A 의 요소가 존재하면 cnt 값 증가시키고 answer 에 넣어
    queue<int> answer;
    for (int i = 0; i < nA; i++) {
        if (!binarySearch(A[i], B)) {
            // A 의 요소가 B 에 존재하지 않으면 cnt 값 증가시ㅕㅋ
            answer.push(A[i]);
        }
    }
    cout << answer.size() << "\n";
    while (!answer.empty()) {
        cout << answer.front() << " ";
        answer.pop();
    }

    return 0;
}

 

A 에는 존재하지만 B 에는 존재하지 않는 값을 찾으려면 for 문으로 A 돌면서 B 에 대해 이분탐색 돌리면 된다.

'백준 문제/이분탐색' 카테고리의 다른 글
  • [백준] 3151번 합이 0
  • [백준] 16401번 과자 나눠주기
  • [백준] 2295번 세 수의 합
  • [백준] 18870번 좌표 압축
dubu0721
dubu0721
dubu0721 님의 블로그 입니다.
  • dubu0721
    dubu0721 님의 블로그
    dubu0721
  • 전체
    오늘
    어제
    • 분류 전체보기 (343) N
      • 프로그래밍언어론 정리 (5)
      • 컴퓨터네트워크 정리 (5)
      • 알고리즘&자료구조 공부 (64)
        • it 취업을 위한 알고리즘 문제풀이 입문 강의 (60)
        • 학교 알고리즘 수업 (3)
        • 실전프로젝트I (0)
      • 백준 문제 (196) N
        • 이분탐색 (7)
        • 투포인트 (10)
        • 그래프 (7)
        • 그리디 (24)
        • DP (25)
        • BFS (18) N
        • MST (7)
        • KMP (4)
        • Dijkstra (3)
        • Disjoints Set (4)
        • Bellman-Ford (2)
        • 시뮬레이션 (3)
        • 백트래킹 (15)
        • 위상정렬 (5)
        • 자료구조 (25)
        • 기하학 (1)
        • 정렬 (11)
        • 구현 (8)
        • 재귀 (8)
        • 수학 (8)
      • 유니티 공부 (11)
        • 레트로의 유니티 게임 프로그래밍 에센스 (11)
        • 유니티 스터디 자료 (0)
        • C# 공부 (0)
      • 유니티 프로젝트 (48)
        • 케이크게임 (13)
        • 점토게임 (35)
      • 언리얼 공부 (10)
        • 이득우의 언리얼 프로그래밍 (10)
      • 진로 (1)
      • 논문 읽기 (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    시뮬레이션
    골드메탈
    자료구조
    우선순위큐
    레트로의 유니티 프로그래밍
    유니티
    유니티 프로젝트
    스택
    해시
    그래프
    백트래킹
    바킹독
    투포인터
    그리디
    언리얼
    BFS
    이분탐색
    C#
    티스토리챌린지
    이득우
    수학
    dp
    유니티 공부 정리
    백준
    오블완
    큐
    맵
    이벤트 트리거
    재귀
    정렬
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
dubu0721
[백준] 1822번 차집합
상단으로

티스토리툴바