0과 1의 쉼터

풀이 입력받은 배열 A를 오름차순으로 정렬(sorted_A)했을 때, 원본 배열의 요소가 정렬된 배열에서 몇 번째에 위치하는지 구하는 문제다. N은 최대 50으로 모든 요소에 대해 배열을 전부 선형탐색해도 O(N^3) 제한시간 내 통과할 수 있다. 동일한 원소에 대해서도 순서는 별도로 부여되므로, 이미 찾은 요소는 범위를 벗어난 수(-1)로 채워넣어 탐색이 되지 않도록 해주자. 소스코드 소스코드 보기 출처 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net

풀이 정렬된 점수들의 절사평균을 구하는 문제이다. 가장 작은 15%의 인원과, 가장 큰 15%의 인원을 제외한 후 나머지 인원에 대해 평균을 구한 후 반올림을 해서 출력해주면 된다. 문제는 단순하지만 Python을 사용하다보니 예상치 못한 복병들이 많았다. 우선 첫 번째로 주어지는 점수들의 개수가 최대 3 x 10^5 이다. 실버 난이도의 문제답지 않게 많은 입력이 주어진다. 빠른 입출력을 해주자. 그 다음으로는 전체 인원에 대한 절사평균이 성립하지 않는 경우다. 즉, 인원이 너무 적어 절사평균을 구하기 위해 제외해야할 인원이 적은 경우이다. 15%에 해당하는 인원의 반올림한 값이 0보다 큰 경우에만 인원을 제외시켜 주자. 다른 하나는 Python의 round()의 작동 방식에 대한 문제다. 일반적으로 ..

풀이 i번째 공이 잡을 수 있는 크기는 i번째 공보다 크기가 작고, 색상이 다른 공들의 합이기 때문에, 입력받은 공들을 공의 크기, 색별로 정렬을 해주었다. 출력순서는 입력순서와 동일해야 하므로, 정렬된 정보들에 대해 index별로 담아 줄 수 있는 배열들을 사용했다. for (int i = 0; i < N; i++){ scanf("%d %d", &b[i].color, &b[i].size); b[i].idx = i; } qsort(b, N, sizeof(Ball), compare); int sum_all = 0; for (int i = 0; i < N; i++){ int s = b[i].size, c = b[i].color, idx = b[i].idx; sum_all += s; same_color[c] ..

풀이 index를 이용해 쉽게 풀이할 수 있는 문제다. bubble sort를 했을 때, 정렬이 다 되기까지의 횟수, 즉 요소들이 좌측으로 밀려났 횟수 중 가장 큰 횟수를 찾으면 된다. 입력받을 때 다음과 같이 index를 달아주고, num 10 1 5 2 3 index 0 1 2 3 4 정렬을 하면 다음과 같은 모습이 된다. num 1 2 3 5 10 index 1 3 4 2 0 정렬한 배열의 요소들에 달린 index값에 대해 이전의 index값들을 뺀 값들 중 최댓값이 정답과 일치한다. 소스코드 #include #include #define max(a, b) a > b ? a : b typedef struct{ int num, idx; }Point; int compare(const void *a, c..

풀이 "백준 2470, 두 용액"의 응용 문제이다. 세 개의 특성값을 비교해야 하므로, 맨 왼쪽부터 기준이 되는 idx번째 특성값과, idx+1 ~ N-1의 특성값을 더해 0에 가장 가까운 용액을 만들어내는 특성값을 찾으면 된다. 단, 세 개 특성값의 최댓/최솟값이 int 범위를 벗어나므로, llabs()를 사용하고, 연산의 범위를 long long으로 선언했다. 소스코드 #include #include #define ll long long int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } int main(){ int N; scanf("%d", &N); int arr[N]; for (int i = 0; i < N; i++) ..

풀이 "백준 2467, 용액"과 동일한 문제이다. 단, 입력되는 특성값이 항상 오름차순이라는 문구가 빠졌다. 정렬 후 탐색을 해주자. 소스코드 #include #include #include int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } int main(){ int N; scanf("%d", &N); int arr[N]; for (int i = 0; i < N; i++) scanf("%d", &arr[i]); qsort(arr, N, sizeof(int), compare); int left = 0, right = N-1, sum = 2e9; int left_val = arr[left], right_val = arr[rig..

풀이 제한시간이 12초이기 때문에 모든 쌍을 확인하면 시간초과가 발생한다. 때문에, A~B, C~D의 합을 저장하고, Binary Search을 사용해 풀이했다. 합이 0인 쌍의 개수를 모두 구해야 하므로, 다음과 같이 upper/lower bound를 구현했다. qsort(AB, N, sizeof(int), compare); qsort(CD, N, sizeof(int), compare); long long cnt = 0; for (int i = 0; i 0) right = mid; else left = mid ..

풀이 입력받은 좌표들을 오름차순으로 정렬하고, 중복을 제거했을 때, 각 요소들이 몇 번째인지 출력하는 문제다. 입력받은 수들을 두 벡터에 저장하고, v2는 오름차순으로 정렬 후, 중복을 제거했다. 중복된 수가 제거된 v2에서 lower_bound()를 사용하면, 원하는 결과를 얻을 수 있다. 소스코드 #include #include #include using namespace std; int main(){ int N, temp; scanf("%d", &N); vector v1(N), v2(N); for (int i = 0; i < N; i++){ scanf("%d", &temp); v1[i] = v2[i] = temp; } sort(v2.begin(), v2.end()); v2.resize(unique(..

풀이 입력받은 시간을 오름차순으로 정렬 후, 기존의 대기시간(sum)과 i번째 사람이 인출하는데 걸리는 시간(arr[i])을 result에 누적 합으로 저장해주면 된다. 소스코드 #include #include int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } int main(){ int N; scanf("%d", &N); int arr[N]; for (int i = 0; i < N; i++) scanf("%d", &arr[i]); qsort(arr, N, sizeof(int), compare); int result = 0; for (int i = 0, sum = 0; i < N; result+=(sum+=arr[i++]))..

풀이 알고리즘은 엄청 간단하다. N명의 이름을 입력받아서 정렬 후, M명의 이름을 입력받아 이진탐색으로 찾은 명단과 총 인원을 출력하면 된다. 하지만, 이를 C로 구현하는 것은 끔찍하다... 소스코드 #include #include #include #include using namespace std; int main(){ int N, M, i; scanf("%d %d", &N, &M); vector v1(N), v2; char name[21]; for (i = 0; i < N; i++){ scanf("%s", name); v1[i] = name; } sort(v1.begin(), v1.end()); for (i = 0; i < M; i++) { scanf("%s", name); if (binary_sea..