눈으로 보니 쉬운거 같아 보였다. 그때까지만 해도...
Baekjoon / Problem No.10815 (숫자 카드)
Problem
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
Input
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다
Output
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.
Solution 1
처음 생각했을때, 당연히 첫번째로 입력받은 배열(편의상 arr1 로 부르겠다.)을 정렬하고 두번째 배열(arr2)의 원소들과 비교해보면 된다는 생각이었다. 그래서 동적배열을 이용해 카드들을 받은 후, Insertion Sort(삽입 정렬) - Binary Search(이진 탐색)을 이용하기로 했다.
#include <stdio.h>
#include <iostream>
using namespace std;
void InsertionSort(int array[], int length)
{
int key, j, i;
for (i = 1; i < length; i++)
{
key = array[i];
for (j = i - 1; j >= 0 && array[j] > key; j--)
{
array[j + 1] = array[j];
}
array[j + 1] = key;
}
}
int BinarySearch(int arr[], int length, int x)
{
int low, high, mid;
low = 0;
high = length - 1;
while (low <= high)
{
mid = (low + high) - 1 / 2;
if (x == arr[mid])
{
return 1; // 탐색 성공
}
else if (x < arr[mid])
{
high = mid - 1; // 탐색범위 아래로
}
else if (x > arr[mid])
{
low = mid + 1; // 탐색범위 위로
}
}
return 0; // 탐색 실패
}
int main()
{
int i, j, k;
int N, M; // 받을 배열의 길이
cin >> N;
int* arr1 = new int[N];
for (i = 0; i < N; i++)
{
cin >> arr1[i];
}
cin >> M;
int* arr2 = new int[M];
for (j = 0; j < M; j++)
{
cin >> arr2[j];
}
InsertionSort(arr1, N); // 정렬하기
for (k = 0; k < M; k++)
{
printf("%d ", BinarySearch(arr1, N, arr2[k]));
}
delete[]arr1;
delete[]arr2; // 동적할당 해제
return 0;
}
물론 이렇게 하면 답이 나오기는 한다. 단지 이 문제에 시간제한이 걸려있다는 점만 빼면 답이 될수는 있다.
더 빠른 코드를 위해 Insertion Sort(삽입 정렬)를 Quick Sort(퀵 정렬)등으로 바꾸어 보았지만, 여전히 시간 초과가 발생했다.
Solution 2
두 개의 배열을 동적할당하고, 정렬하고, 탐색하는 과정이 생각보다 오래걸리기에 벡터를 이용, 조금 더 코드를 간략하게 바꾸어 보았다.
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int BinarySearch(vector<int> &vec, int length, int x)
{
int low, high, mid;
low = 0;
high = length - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (x == vec[mid])
{
return 1; // 탐색 성공
}
else if (x < vec[mid])
{
high = mid - 1; // 탐색범위 아래로
}
else if (x > vec[mid])
{
low = mid + 1; // 탐색범위 위로
}
}
return 0; // 탐색 실패
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
// C언어의 버퍼와 C++의 버퍼를 분리시킨다.
// 멀티스레드나 C,C++의 입출력 방식을 혼용할 시 오류 가능성 있음
int i, j;
int N, M;
cin >> N;
vector<int> vec(N);
for (i = 0; i < N; i++)
{
cin >> vec[i];
}
sort(vec.begin(), vec.end()); // 정렬하기
cin >> M;
int comp; // 두번째로 받은 비교할 카드가 한개씩 이 변수에 들어온다.
for (j = 0; j < M; j++)
{
cin >> comp;
cout << BinarySearch(vec, vec.size(),comp) << " ";
}
}
여기서 낯선 부분이 있는데,
ios_base::sync_with_stdio(0);
cin.tie(NULL);
이 부분은 C 표준 stream과 C++ 표준 stream의 동기화를 끊는 역할을 한다. 이렇게 되면 C++가 독립적인 버퍼를 갖게 되므로 C언어와 C++의 입출력 방식을 혼용하거나, 멀티스레드 사용시 오류가 발생하기도 한다.
다만 사용 버퍼의 수가 줄기 때문에 실행속도가 빨라지는 효과가 있다고 한다.
Solution 3
문제를 풀며 헤메다 굉장히 흥미로운 아이디어도 발견했다. 문제의 조건을 잘 살펴봤을때, 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 즉, 중복을 전혀 생각하지 않아도 된다. 그렇다면 단 한개의 배열 만으로도 답을 만들어 낼 수 있다.
상근이가 가지고 있던 숫자카드의 숫자들의 집합을 A, 비교해야할 정수들의 집합을 B라고 하자
- 카드에 적힌 숫자 값의 범위는 -10,000,000 ~ 10,000,000 이다.
- 이를 배열 인덱스에 매칭시키기위해 0 ~ 20,000,000 + 1 로 바꾸어주고, 0으로 초기화한다. (주석 1번)
- A의 각 수들 + RANGE에 더한 인덱스에 "1"을 집어넣는다. EX) 숫자카드 10 → 인덱스 10000010
- 위 과정으로 집합 A에 대응되는 배열의 인덱스 공간이 1로 마스킹(Masking) 된다. (주석 2번)
- 집합 B + RANGE에 해당하는 매칭된 인덱스로 찾아가면, 아까 방문해서 1로 마스킹 된 곳은 1로, 그렇지 않은곳은 초기화된 0으로 나타난다. (주석 3번)
#include <cstdio>
#define RANGE 10000000
bool CardSets[(RANGE << 1) + 1] = {0,}; // 1번
int main()
{
int N, M;
scanf("%d", &N);
int input;
for (int i = 0; i < N; i++)
{
scanf("%d", &input);
CardSets[input + RANGE] = 1; // 2번
}
scanf("%d", &M);
for (int i = 0; i < M; i++)
{
scanf("%d", &input);
printf("%d ", CardSets[input + RANGE]); // 3번
}
}출처 : https://www.gigong.io/2022/11/09/baekjoon-10815-cpp [GiGong Blog]
처음에 코드를 보고 '아름답다'고 느꼈다. 이만큼 획기적이고 깔끔하게 정리할 수 있었다니...
간단히 말해서,
| 1번 | 2번 | 3번 | 4번 | 5번 | 6번 | 7번 | 8번 | 9번 | 10번 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
으로 초기화된 방들에
| 1번 | 2번 | 3번 | 4번 | 5번 | 6번 | 7번 | 8번 | 9번 | 10번 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
상근이가 가진 카드에 적힌 숫자들을 적어준다.
여기서 만약 내가 가진 카드가 2,3,4,5,6 번이라면,
| 1번 | 2번 | 3번 | 4번 | 5번 | 6번 | 7번 | 8번 | 9번 | 10번 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
0, 1, 0, 1, 0 을 출력 해주면 되는 원리이다.
이미 지나간 자리를 1로 색칠 해놓고 다음번에 지나갈때 색칠이 되었는지 아닌지만 출력하는 원리이다.
이 방법은 간단하면서 빠르게 풀 수 있지만 20,000,001이나 되는 크기의 배열을 사용하기 때문에 메모리 사용량이 많아졌고,(대략 2MB) 직접 실행해본 결과 실행 시간도 Solution 2의 벡터를 활용한 방법보다 약 100ms 정도 느렸다.
Code
아이디어나 코드에나 그 어떤것에도 절대적으로 완벽한 정답과 오답은 존재하지 않는다.
간단하고 쉬운 풀이가 있었는가 하면, 조금 복잡하지만 그래도 빠르고 나름 효율적인 내가 짠 코드(사실 코드를 짠 본인한테는 효율적이지는 않았다. 그로 그럴것이 3시간은 붙어있었기 때문이다.)도 있었다.
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int BinarySearch(vector<int> &vec, int length, int x)
{
int low, high, mid;
low = 0;
high = length - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (x == vec[mid])
return 1; // 탐색 성공
else if (x < vec[mid])
high = mid - 1; // 탐색범위 아래로
else if (x > vec[mid])
low = mid + 1; // 탐색범위 위로
}
return 0; // 탐색 실패
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
// C언어의 버퍼와 C++의 버퍼를 분리시킨다.
// 멀티스레드나 C,C++의 입출력 방식을 혼용할 시 오류 가능성 있음
int i, j;
int N, M;
cin >> N;
vector<int> vec(N);
for (i = 0; i < N; i++)
cin >> vec[i];
sort(vec.begin(), vec.end()); // 정렬하기
cin >> M;
int comp; // 두번째로 받은 비교할 카드가 한개씩 이 변수에 들어온다.
for (j = 0; j < M; j++)
{
cin >> comp;
cout << BinarySearch(vec, vec.size(),comp) << " ";
}
}
그렇기에 다른 사람의 코드보다는 본인이 짜본 코드를 올려보며 마무리 하겠다. 나름 정이 가기도 한다.
Review
문제의 난이도를 떠나, 여러가지 알고리즘을 사용해야하고, 어느정도 길이가 있는 코드를 작성하면서 헤메는 일이 많았다.
또한 다른사람의 아이디어들을 보니 정말 천재적이라고 생각했다. 약간의 생각의 전환으로 문제를 보다 쉽게 풀 수 있다는 사실이 꽤 신기했고, 한편으로 일면식도 없는 사람들의 아이디어를 보고 여러 생각을 하며 마치 새로운 발견을 한 것인양 감탄했고, 기뻤다. 다른 사람의 생각을 읽어보는 것 같았다.
이런 점 때문에 사람들이 코딩을 하는게 아닐까?
'오늘의 코드' 카테고리의 다른 글
| 오늘의 코드. 3일차 (백준/25305번 커트라인) (1) | 2024.02.07 |
|---|---|
| 오늘의 코드. 2.5일차 (백준/19532번 수학은 비대면강의입니다) (0) | 2024.02.06 |
| 오늘의 코드. 1.5일차 (백준/1085번 직사각형에서 탈출) (2) | 2024.02.05 |
| 오늘의 코드. 1일차 (백준/2869번 달팽이는 올라가고 싶다) (3) | 2024.02.05 |
| 오늘의 코드. 0일차 (Prologue) (2) | 2024.02.04 |