[ BOJ - 31091번 ] 거짓말 (C++)

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

 

 거짓말을 하는 사람의 수를 어떻게 정의할 지 올바르게 생각하지 못해 틀렸던 문제이다.

 

 서로 상충하는 주장을 하는 사람끼리 주장하는 거짓말 하는 사람의 수가 일치하면

(n  > m 일 때, n 이상이 거짓말, m 이하가 거짓말을 한다고 주장하는 사람의 수가 각각 m명과 n명일 경우),

n과 m이 거짓말 하는 사람의 수가 될 것이라 생각하고 문제를 풀었으나 정답을 받지 못했다.

 

 결국 문제를 풀지 못했고 나중에 정답을 맞춘 사람의 아이디어를 보고 나서야 올바른 풀이 방법을 알아낼 수 있었다.

 

 거짓말 하는 사람의 수가 K명이 되기 위해서는,

K-1명 이하가 거짓말을 한다고 주장하는 사람과 K+1명 이상이 거짓말 한다고 주장하는 사람의 수의 합이 K가 되어야 한다.

 

[ 풀이 방법 ]

 

 따라서, 거짓말하는 사람의 수로 가능한 모든 경우(0~N)를 돌며 위의 조건을 만족하는 K를 모두 찾으면 된다.

그러나 N이 최대 500000의 값을 가지므로 O(n log n)의 시간복잡도를 가져야 하기 때문에 STL의 lower_bound와 upper_bound를 이용해 K-1명 이하가 거짓말을 한다고 주장하는 사람과 K+1명 이상이 거짓말 한다고 주장하는 사람의 수의 합을 O(log n)의 시간 안에 구할 수 있도록 구현하였다.

 

양수와 음수의 절대값을 저장하는 벡터를 만들고 lower_bound와 upper_bound를 사용하기 위해 정렬한 뒤,

 

0~n까지  반복하면서 K-1명 이하가 거짓말을 한다고 주장하는 사람의 수와 K+1명 이상이 거짓말 한다고 주장하는 사람의 수의 합을 구하고 K와 비교하여 같다면 정답을 담는 벡터인 res에 K값을 저장했다.

// K+1명 이상이 거짓말한다고 말한 사람의 수: 
// 양수를 말한 사람의 수 - 양수를 말한 사람 중 1~K(K 이하)명 이상이 거짓말 한다고 말한 사람의 수
int(pos.size() - (upper_bound(pos.begin(), pos.end(), K) - pos.begin()));

// K-1명 이하가 거짓말한다고 말한 사람의 수: 
// 음수를 말한 사람 중 K명 미만이 거짓말 한다고 말한 사람의 수
int(lower_bound(neg.begin(), neg.end(), K) - neg.begin());

 

 반복이 끝난 뒤 저장된 k값들을 올바른 형태로 출력하여 문제를 해결하였다.

 

[ 정답 코드 ]

#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    vector<int> pos;
    vector<int> neg;
    for(int i = 0; i < n; i++) {
        int t;
        cin >> t;
        
        if (t > 0) {
            pos.push_back(t);
        } else {
            neg.push_back(abs(t));
        }
    }
    
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());
    
    vector<int> res;
    for (int i = 0; i <= n; i++) {
        int posCnt = int(pos.size() - (upper_bound(pos.begin(), pos.end(), i) - pos.begin()));
        int negCnt = int(lower_bound(neg.begin(), neg.end(), i) - neg.begin());
        
        if (posCnt + negCnt == i) {
            res.push_back(i);
        }
    }
    
    cout << res.size() << '\n';
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    
    return 0;
}