[C++]백준(BOJ) 33272 TAIDADA 문제풀이

 

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

---

문제

 

1 이상 M 이하의 서로 다른 정수 N개를 나열하여 다음 조건을 만족하는 수열 A를 만들어 보자.

• Ai ⊕ Aj ≠ K (1 ≤ i < j ≤ N)

 

⊕ 는 Bitwise XOR 연산을 의미한다.

---

입력

첫째 줄에 수열 A의 길이 N과 양의 정수 M, K가 공백으로 구분되어 주어진다.

(1 ≤ N ≤ 200,000, 1 ≤ M, K ≤ 10^9)

 

 

 

 

출력

수열 A를 만들 수 있다면 수열 A의 N개의 원소를 공백으로 구분하여 한 줄에 출력한다. 그렇지 않다면 -1을 대신 출력한다. 조건을 만족하는 출력이 여러 가지인 경우 그중 아무거나 출력한다.

---

 

예제 입력, 출력

 

---

알고리즘 분류

 

# 그리디 알고리즘

# 해 구성하기

---

해설

특정한 조건을 만족하는 수열 A를 만들 수 있으면 해당 수열을 출력하고 불가능하다면 -1을 출력하는 문제이다. 수열의 조건은 다음과 같다

 

1. 1이상 M이하의 서로 다른 N개의 정수로 구성되어야함

 

2. 수열의 각각의 원소들에 대한 모든 두개의 조합에 대해 ⊕연산(XOR)을 수행했을 때 K가 나오면 안됨

 

가능한 정수의 범위가 10의 9제곱이고, 최대 200,000개의 서로다른 N개 조합을 고려해야 할 수 있으므로, 시간복잡도의 최적화에 유념하여 해결해야하는 문제이다. 예외상황은 따로 조건을 두어 반복문에 진입하는 경우를 최소화 하고, 조건을 만족하는 수열을 찾으면 반복을 즉시 종료하도록 코드를 구성하였다 또한, 수열의 요소들의 순서는 관계없으므로, 해시셋을 사용하여 조건검사할 때 시간복잡도를 최소화하였다.

 

시간초과가 발생할 것 같아 여러가지 최적화를 해두었지만 막상 제외하고 제출해도 맞긴했었으므로 좀더 널널하게 잡고 문제를 해결해도 좋을 것 같다.

 

코드의 대략적인 로직은 다음과 같다.

 

1. 서로 다른 숫자들을 골라야 하기때문에 M이 N보다 작다면 애초에 불가능한 경우임, -1 출력하고 프로그램 종료

 

2. 1부터 M까지 순회하며 수열 조건 검사(i ⊕ K가 res셋에 존재하면 안된다), 선택한 숫자의 개수가 N개에 도달하면 완료된것이므로 중간에 종료

 

3. for문의 조건에 대해: xor 연산은 교환법칙, 결합법칙이 성립하므로 A ⊕ B != K 이라면 A ⊕ K != B임은 자명하다, 따라서 A ⊕ K 한 값이 res셋에 존재하지 않아야 조건을 만족한다.

 

4. for 문이 끝난 뒤 만약 res셋의 크기가 N보다 작다면 조건을 만족하는 수열이 없는 것이므로 -1을 출력하고, 아니라면 조건을 만족하는 것이므로 res셋을 출력한다.

 

---

소스코드

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    int N;
    long long M, K;
    cin >> N >> M >> K;

    // M개의 숫자 중에서 N개를 고를 수 없는 경우
    if (M < N) {
        cout << -1 << endl;
        return 0;
    }

    unordered_set<int> res; // 해시셋 사용 (수열의 요소간 순서는 상관 없으므로)

    for (int i = 1; i <= M && res.size() < N; i++) {
        if (res.find(i ^ K) == res.end()) { // XOR 조건 검사
            res.insert(i); // 조건을 만족한다면 숫자 추가
        }
    }

    // 조건을 만족하는 수열을 생성하지 못한 경우
    if (res.size() < N) {
        cout << -1 << endl;
    }
    else {
        for (int num : res) {
            cout << num << " ";
        }
        cout << "\n";
    }

    return 0;
}