[BOJ알고리즘, C++]#10816_숫자 카드2, lower_bound, upper_bound

2022. 9. 25. 18:29· 문제 풀이/BOJ 문제 풀이
목차
  1.  
  2. [BOJ 알고리즘, C++] #10816_숫자 카드 2, lower_bound, upper_bound

 

[BOJ 알고리즘, C++] #10816_숫자 카드 2, lower_bound, upper_bound

 

BOJ 알고리즘 문제 풀이, 10816_숫자 카드2

정렬 알고리즘을 통해 주어진 숫자 카드가 존재하는지 탐색합니다.

 

 


 

문제

 

풀이

1. Map 컨테이너 활용

// 1. Map 컨테이너를 활용했지만, 2번 코드보다 소요 시간과 메모리 사용량이 비교적 훨씬 높음...

#include <iostream>
#include <map>
#include <algorithm>
typedef long long ll;
using namespace std;

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

    int N, M;
    // 숫자 + 개수
    map<ll, int> m;
    vector<ll> v;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        ll num;
        cin >> num;

        m[num]++;
    }

    cin >> M;

    for (int i = 0; i < M; i++)
    {
        ll num2;
        cin >> num2;

        v.push_back(m[num2]);
    }

    for (int val : v)
        cout << val << " ";
}
1. Map 컨테이너 활용

먼저, 입력받은 숫자 카드와 각 숫자 카드의 개수를 한 쌍으로 Map 컨테이너에 삽입합니다.

2. v.push_back(m [num2])

입력받은 M개의 숫자 카드를 "Key"로 "Value" 값을 벡터에 순서대로 삽입합니다. 이때, Map 컨테이너에 존재하지 않는 새로운 숫자 카드, 혹은 "Key"값을 반환하면 0이 반환되는 것을 이용합니다.

* 수행 속도와 메모리 사용량이 너무 높아서 새로운 방법을 생각해보았습니다.

 

2. 정렬 알고리즘 및 lower_bound + upper_bound 활용

// 2. Sort 알고리즘과 lower_bound와 upper_bound 활용 코드, 시간 + 성능 모두 훨씬 뛰어남

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;

using namespace std;

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

    int N, M;
    vector<ll> v;
    vector<int> v2;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        ll num;
        cin >> num;

        v.push_back(num);
    }

    sort(begin(v), end(v));

    cin >> M;

    for (int i = 0; i < M; i++)
    {
        ll num2;
        cin >> num2;

        auto upper = upper_bound(begin(v), end(v), num2);
        auto lower = lower_bound(begin(v), end(v), num2);

        v2.push_back(upper - lower);
    }

    for (auto val : v2)
        cout << val << " ";
}
1. lower_bound + upper_bound

같은 수의 lower_bound와 upper_bound를 구해서 빼주면 해당 숫자의 개수를 얻을 수 있습니다. 주의할 점은 lower_bound와 upper_bound 알고리즘을 사용하기 위해선 정렬이 선행되어야 합니다!

 

 

 

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ알고리즘, C++]#9663_N-Queen 문제, 백 트래킹  (0) 2022.10.24
[BOJ알고리즘, C++]#15649_N과 M(1), 깊이 우선 탐색  (0) 2022.10.23
[BOJ알고리즘, C++]#10815_숫자 카드, 이진 탐색, Binary Search  (0) 2022.09.06
[BOJ알고리즘, C++]#1008_A/B, C++ 부동 소수점, precision(), fixed  (0) 2022.09.04
[BOJ알고리즘, C++]#25305_커트 라인, 정렬 알고리즘, STL, 내림차순  (0) 2022.09.04
  1.  
  2. [BOJ 알고리즘, C++] #10816_숫자 카드 2, lower_bound, upper_bound
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#9663_N-Queen 문제, 백 트래킹
  • [BOJ알고리즘, C++]#15649_N과 M(1), 깊이 우선 탐색
  • [BOJ알고리즘, C++]#10815_숫자 카드, 이진 탐색, Binary Search
  • [BOJ알고리즘, C++]#1008_A/B, C++ 부동 소수점, precision(), fixed
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • 최단 경로
  • BOJ
  • Unreal Blueprint
  • DP
  • 알고리즘
  • 디자인 패턴
  • Effective C++
  • stl
  • programmers
  • 정렬
  • set
  • 그래프
  • unreal
  • 기술 질문
  • 트리
  • 우선순위 큐
  • dfs
  • 개발
  • BFS
  • C++

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#10816_숫자 카드2, lower_bound, upper_bound
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.