[Algorithm] 백준 - IF문 좀 대신 써줘 (19637번)

문제

[백준] IF문 좀 대신 써줘

사용 알고리즘

- 이분 탐색 (Binary Search)

해결방법

• 입력받은 전투력 배열(level_num)을 이분탐색으로 탐색한다.
• 예제 2에서 살펴보면 다음과 같은 흐름으로 계산된다

• 99가 입력되었을 때
  • lv : 99
    • left : 0, right : 3
      • mid : 1
      • level_num[mid] : 100 (A)
      • right => 0 (mid - 1)
    • left : 0, right : 0
      • mid : 0
      • level_num[mid] : 100 (B)
      • right => -1 (mid - 1)
    • level_name[mid] : B
      . . .
  • lv : 101
    • left : 0, right : 3
      • mid : 1
      • level_num[mid] : 100 (A)
      • left => 2 (mid + 1)
    • left : 2, right : 3
      • mid : 2
      • level_num[mid] : 1000 (C)
      • right => 1 (mid - 1)
    • level_name[mid] : C

소스코드

사용언어 : C++

#include <iostream>
#include <string>

using namespace std;

int N, M;
int level_num[100001]; //전투력
string level_name[100001]; //칭호

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> M;

    for (int i=0; i<N; i++){
        cin >> level_name[i] >> level_num[i];
    }
    
    for (int i=0; i<M; i++){
        long lv;
        cin >> lv;

        int left = 0;
        int right = N;
        int mid;
        
	// 이분 탐색
        while (left <= right) {
            mid = (left + right) / 2;
            if (level_num[mid] < lv) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        if (lv > level_num[mid]) {
            cout << level_name[mid+1] << "\n";
        } else {
            cout << level_name[mid] << "\n";
        }
    }

    return 0;
}

 

another solution : lower_bound 사용

* https://dkswnkk.tistory.com/594

[백준,c++] 19637번 - IF문 좀 대신 써줘

* multimap의 경우 레드 블랙 트리로 구현되어 있어 binarysearch 메서드를 제공하는데, lower_bound는 입력값보다 처음으로 같거나 높은 값을 리턴해주는 메서드이다. 때문에 lower_bound를 사용해 간단하게 풀이할 수 있다.

 

 

"\n" vs. endl

* https://untitle-ssu.tistory.com/45 

* endl 함수는 개행만 해주는게 아닌 내부 버퍼를 비워주는 역할도 하기 때문에 시간이 많이 소요됨

 

한줄평

endl 때문에 시간초과가 계속 나다니. . . . 스터디 아니었으면 영영 몰랐을 뻔 했다. 스터디의 순기능 체고 ^_< b