[BAEKJOON] 19637번 IF문 좀 대신 써줘

2024. 3. 25. 12:33·Algorithm/Binary Search

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

 

19637번: IF문 좀 대신 써줘

첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭

www.acmicpc.net

문제조건
  1. N개의 줄에 각 칭호의 이름과 칭호의 상한 값이 주어진다.
  2. 칭호는 전투력 상한값의 비내림차순으로 주어진다. 
  3. M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.

처음 봤을때 너무 쉬워서 빠르게 구현부터했다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int n, m;
vector<int> power;
vector<pair<string, int> > symbol;
int main(){
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		int up;
		cin >> s >> up;
		symbol.push_back(make_pair(s, up));

	}
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		power.push_back(a);
		for (auto up : symbol){
			if (up.second >= a) {
				cout << up.first << '\n';
				break;
			}
		}
	}
	
}

ㅋㅋㅋㅋ

그럼 그렇지 이렇게 쉽게 단순 구현으로 해결될 것이 아니었다.

문제를 다시 자세히 보니, 칭호의 개수와, 캐릭터의 개수가 각각 10^5이고, 내가 위에 짠 코드에서는 최악의 경우 10^5^5 까지 시간복잡도가 증가 할 수 있는데, 자그마치 100억이다 ㄷㄷ,,,, 1억번 연산당 1초가 걸리는데, 문제 제한조건인 1초보다 훨씬 많이 걸린다. 완탐 말고 시간 줄일 수 있는 좋은 알고리즘이 없나하는 찰나 비내림차순으로 정렬되어 전투력 상한값을 주어진다는 조건에서 이분탐색을 이용하는 방법을 떠올렸다. 

 

map에다 저장해놓고, 전투력 이상인 첫번째로 만나는 칭호를 출력하는 것이다.

https://chanhuiseok.github.io/posts/algo-55/

 

알고리즘 - c++ lower_bound, upper_bound 활용하기

컴퓨터/IT/알고리즘 정리 블로그

chanhuiseok.github.io

이 글이 lower_bound에 대해서 자세히 설명해줬다. 많은 도움이 되었다. 따라서 이분탐색을 lower_bound로 간단하게 구현했다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int n, m;
map<int, string> symbol;
int main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		int up;
		cin >> s >> up;
		symbol.insert({ up,s });
	}
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		auto iter = symbol.lower_bound(a);
		cout << iter->second << '\n';
	}
	
}

'Algorithm > Binary Search' 카테고리의 다른 글

[BAEKJOON] 1348번 주차장  (0) 2024.06.01
[BAEKJOON] 1806번 부분합  (1) 2024.04.16
[BAEKJOON] 2568번 전깃줄 - 2  (0) 2024.03.30
[BAEKJOON] 2613번 숫자구슬  (1) 2024.03.16
[BAEKJOON] 6236번 용돈 관리  (3) 2024.03.14
'Algorithm/Binary Search' 카테고리의 다른 글
  • [BAEKJOON] 1806번 부분합
  • [BAEKJOON] 2568번 전깃줄 - 2
  • [BAEKJOON] 2613번 숫자구슬
  • [BAEKJOON] 6236번 용돈 관리
Ls._.Rain
Ls._.Rain
안되면 될때까지 삽질했던 기록
  • Ls._.Rain
    Ls{Diary}
    Ls._.Rain
  • 전체
    오늘
    어제
    • 분류 전체보기 (136)
      • Github (2)
      • Spring (51)
        • Batch Programming (13)
        • 결제 (4)
        • 대용량 트래픽 (32)
        • OpenAI (0)
        • Security (0)
        • WebSocket (0)
        • JPA (1)
      • Algorithm (67)
        • DFS (6)
        • BFS (6)
        • Dynamic Programming (10)
        • Brute Force (4)
        • Binary Search (6)
        • 구현, 시뮬레이션 (15)
        • Stack (1)
        • Greedy (4)
        • Priority_Queue (2)
        • Back Tracking (3)
        • Geometry (2)
        • SCC (1)
        • 투포인터 (4)
        • 최대유량 (1)
        • 정렬 (1)
      • OS (0)
      • DevOps (15)
        • AWS (11)
        • Docker (4)
  • 블로그 메뉴

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

  • hELLO· Designed By정상우.v4.10.0
Ls._.Rain
[BAEKJOON] 19637번 IF문 좀 대신 써줘
상단으로

티스토리툴바