[이분탐색 & ios::sync_with_stdio,cin.tie] IF문 좀 대신 써줘 - 백준 19637번

19637번: IF문 좀 대신 써줘

풀이

! 칭호는 전투력 상한값의 비내림차순으로 주어진다.

캐릭터의 전투력을 나타내는 음이 아닌 정수가 주어진다. (정렬, 순서 없음)

1. 캐릭터의 전투력을 정렬 시킨다.
2. 전투력 상한값과 비교한다.

⇒ 정렬되어 있기 때문에 전투력 상한값을 처음부터 돌릴 필요가 없다. O(m^n) 방지

정렬된 캐릭터 전투력 for문을 한번만 돌리면 된다. → O(m)

하지만 결과는 기존 입력한 대로 나와야 하기 때문에 정렬 전의 모습으로 바꿔줘야 한다.

⇒ 나는 map을 사용했다. 숫자에 맞는 칭호를 연결하여 정렬 이전의 전투력을 돌려 해당하는 칭호를 출력한다.

map<전투력, 칭호>

-뭔가 투포인터?-

이분탐색 풀이

for (int i = 0; i < M; i++) {
    cin >> characters;
    
    auto upper = upper_bound(power.begin(), power.end(), characters-1); //characters-1 : characters 포함
    int index = distance(power.begin(), upper);

    cout << style[index] << "\n";
}

characters-1 보다 큰 첫번째 요소 == characters 보다 크거나 같은 첫번째 요소를 찾는다.
찾은 곳과 첫 시점과의 거리를 비교하여 index를 구한다.

• upper_bound: 정렬된 범위에서 특정 값보다 큰 첫 번째 요소를 찾는 함수
  • iterator를 반환
  • 이터레이터의 타입이 모호할 경우 명시적으로 auto 키워드를 사용해 변수에 할당
• distance: 두 이터레이터 사이의 거리를 반환하는 함수

메인 루프는 총 M번 반복되므로, 각 반복마다 upper_bound가 O(log N)의 시간 복잡도를 가집니다.

따라서 메인 루프의 총 시간 복잡도는 O(M * log N)입니다.

최종 시간 복잡도

모든 부분을 합치면:

• 벡터 입력: O(N)
• 메인 루프: O(M * log N)

따라서 전체 프로그램의 시간 복잡도는 O(N + M * log N)가 됩니다.

---

다만 이 코드만 적을 시 시간초과가 발생한다.

그래서 다음 두 줄을 작성해야한다.

ios::sync_with_stdio(0);
cin.tie(0); 

1. ios::sync_with_stdio(false)의 역할

ios::sync_with_stdio(false)는 C++ 표준 입력/출력 스트림(cin, cout)과 C의 표준 입출력 함수(scanf, printf)를 동기화하는 기능을 비활성화하는 명령어입니다.

• 기본적으로, C++의 cin/cout은 C의 scanf/printf와 동기화되어 실행됩니다. 이 동기화로 인해 속도가 느려질 수 있습니다.
• ios::sync_with_stdio(false)를 호출하면 C++의 cin, cout이 C의 입출력 함수와 분리되어 입출력 성능이 크게 향상됩니다.
• 즉, 이 동기화를 끄면 cin, cout의 성능이 향상되어 더 빠르게 작동합니다.

2. cin.tie(0)의 역할

cin.tie(0)은 cin과 cout의 연결을 끊는 것입니다.

• 기본적으로, cin과 cout은 서로 연결되어 있어서 cin이 입력을 받을 때마다 cout이 자동으로 출력 버퍼를 비웁니다.
• cin.tie(0)을 사용하면 이 연결을 끊어 cin이 입력을 받을 때 출력 버퍼를 강제로 비우지 않도록 하여 불필요한 작업을 줄일 수 있습니다. 이는 cin과 cout이 자주 사용되는 경우 성능을 향상시킵니다.

왜 시간 초과가 해결되었을까?

기본적으로 C++의 cin과 cout은 매우 안전하게 동작하지만, 상대적으로 느립니다. 특히 N과 M의 크기가 매우 큰 경우, 반복적인 입출력이 성능에 큰 영향을 미칩니다.

• ios::sync_with_stdio(false)와 cin.tie(0)를 적용하지 않으면, 입출력에 많은 시간이 소요되어 시간 초과가 발생할 수 있습니다.
• 반면, 이 두 줄을 추가하면 C++ 표준 스트림의 성능이 크게 향상되어 입출력 처리 속도가 빨라져 시간 초과 문제를 해결할 수 있습니다.

코드

https://github.com/KimGyeongLock/CodingTest/blob/main/19637.cpp