입력된 N개의 수에 대한 산술평균, 중앙값, 최빈값, 범위를 출력한다. 산술평균 - 소수 첫째 자리에서 반올림 중앙값 - 요소가 홀수 일 때는 중앙에 위치한 값, 짝수일 때는 중앙에 위치한 두 수의 평균 최빈값 - 가장 많이 출현한 수. 여러 개 있을 경우 두 번째로 작은 값
테스트 케이스
5 1 3 8 -2 2
2 2 1 10
1 4000
4000 4000 4000 0
5 -1 -2 -3 -1 -2
-2 -2 -1 2
문제 풀이
입력하는 횟수가 50만개로 많고, 반대로 정수의 범위는 -4000 ~ 4000으로 좁은 편이다. 입력 순서를 고려하지 않아도 되고 중복값이 존재하므로 인덱스를 만들고 이를 바탕으로 계산하는 것이 좋다.
산술평균 - 합계가 양수일 경우에는 +0.5를, 음수일 경우에는 -0.5를 한 후에 int로 형변환하면 된다. 중앙값 - N / 2개에 해당하는 인덱스 값을 출력한다. 최빈값 - 오름차순으로 인덱스를 탐색한다. 현재 최빈값과 같을 경우 중복 여부를 확인하고, 더 높은 수가 나오면 중복 체크를 초기화한다. 최빈값 - 입력받는 시점에 min, max를 구하고 max - min을 출력한다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_2108()
{
int N;
cin >> N;
int32_t index[8001] = { 0 };
int32_t sum = 0;
int16_t min = 4000;
int16_t max = -4000;
for (int i = 0; i < N; ++i)
{
int16_t input;
cin >> input;
if (min > input)
{
min = input;
}
if (max < input)
{
max = input;
}
sum += input;
index[input + 4000]++;
}
// 산술평균
double average = (double)sum / N;
average = average > 0 ? average + 0.5 : average - 0.5;
cout << static_cast<int32_t>(average * 10) / 10 << endl;
// 중앙값
int32_t middle = N / 2;
for (int i = 0; i < 8001; i++)
{
middle -= index[i];
if (middle < 0)
{
middle = i - 4000;
break;
}
}
cout << middle << endl;
// 최빈값
int16_t mode;
int32_t count = 0;
bool overlap = false;
for (int i = 0; i < 8001; ++i)
{
if (count < index[i])
{
count = index[i];
mode = i - 4000;
overlap = false;
}
else if (count == index[i] && !overlap)
{
mode = i - 4000;
overlap = true;
}
}
cout << mode << endl;
// 범위
cout << max - min << endl;
return;
}
최대 1000만개의 숫자를 오름차순으로 출력한다. 입력되는 수는 10000보다 작거나 같은 자연수다.
테스트 케이스
10 5 2 3 1 4 2 3 5 1 7
1 1 2 2 3 3 4 5 5 7
문제 풀이
제목은 정렬하기라고 하지만 처리에는 실제로는 정렬 알고리즘을 사용하지 않는 문제다. 순순히 정렬을 사용해서 풀 경우 매우 오랜 시간이 소요된다. 입력되는 수의 종류가 10000개 이하로 매우 적고, 입력되는 수가 1000만 개까지 되므로 int형 배열 10001개를 선언하여 인덱스를 기록하는 방식으로 진행하여야 한다.
1. int 배열 10001개를 선언한다. 2. 수를 입력 받는다. 3. 입력받의 수의 인덱스에 +1을 한다. 4. 입력이 종료될 때까지 2~3을 반복한다. 5. 1부터 배열에 입력된 수만큼 해당 수를 출력한다.
입출력이 각각 1000만 번씩 이루어지므로 입출력에 소요되는 시간을 최대한 줄여야 한다. 정렬이 아무리 빨라도 입출력이 오래 걸리면 시간 초과가 되기 때문. 빠른 입출력에 대해서는 15552번 문제 설명을 참고하도록 한다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_10989()
{
ios::ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
int index[10001] = { 0 };
for (int i = 0; i < N; i++)
{
int temp;
cin >> temp;
index[temp]++;
}
for (int i = 1; i <= 10000; i++)
{
for (int j = 0; j < index[i]; j++)
{
cout << i << "\n";
}
}
return;
}void BAEKJOON_번호()
{
return;
}
n(log n) 복잡도의 정렬까지 허용되는 문제. algorithm의 sort를 이용해 풀면 된다. 출력이 많으므로 endl은 사용하지 않는다. algorithm의 sort를 사용하면 ios::ios_base::sync_with_studio(false), cin.tie(NULL)을 적용하여 296ms까지 시간을 줄일 수 있다.
풀이 코드
#include <iostream>
#include <algorithm>
using namespace std;
void BAEKJOON_2751()
{
int N;
cin >> N;
int* arr = new int[N];
for (int i = 0; i < N; i++)
{
cin >> arr[i];
}
sort(arr, arr + N);
for (int i = 0; i < N; i++)
{
cout << arr[i] << "\n";
}
delete[] arr;
return;
}
1. 데이터를 입력 받는다. N을 먼저 입력 받고, M을 그 다음에 입력 받는다. 2. 기준이 되는 8 * 9 사이즈 체스판 배열을 만들어 아래와 같이 초기화한다. WBWBWBWB - WB 판일 때의 비교 시작 BWBWBWBW - BW 판일 때의 비교 시작 WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB
3. 입력받은 데이터와 체스판을 !=으로 비교연산 하여 그 합계와 현재 값을 비교한다. 4. 3을 통해 구한 가장 적은 합계를 출력한다. ※ 다른 테스트 케이스는 다 맞는데 11 8, 8 11이 틀린다면 반복문을 돌리는 기준이 잘못됐을 가능성이 높다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_1018()
{
/*----------기준 체스판----------*/
char standard[9][8];
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 8; j++)
{ // i + j가 짝수면 흰색, 홀수면 검정색
standard[i][j] = (i + j) % 2 ? 'B' : 'W';
}
}
/*----------데이터 입력----------*/
int N;
int M;
cin >> N >> M;
char** data = new char*[N];
for (int i = 0; i < N; i++)
{
data[i] = new char[M + 1];
cin >> data[i];
}
/*----------비교 시작----------*/
int changePt = 64;
for (int i = 0; i <= N - 8 && changePt; i++)
{// 비교 시작 위치 지정, changePt == 0인 경우 반복문 종료
for (int j = 0; j <= M - 8 && changePt; j++)
{
int valueWB = 0;
int valueBW = 0;
for (int m = 0; m < 8; m++)
{// 비교 진행
for (int n = 0; n < 8; n++)
{
valueWB += standard[m][n] != data[i + m][j + n];
valueBW += standard[m + 1][n] != data[i + m][j + n];
}
}
changePt = changePt > valueWB ? valueWB : changePt;
changePt = changePt > valueBW ? valueBW : changePt;
}
}
cout << changePt << endl;
/*----------메모리 해제----------*/
for (int i = 0; i < N; i++)
{
delete[] data[i];
}
delete[] data;
return;
}
몸무게와 키로 이루어진 덩치값이 주어졌을 때 A가 B보다 몸무게, 키 값이 모두 크면 A는 B보다 덩치가 크다고 한다. 알 수 없을 때는 동일한 덩치라고 한다. 자신보다 덩치가 큰 사람보다는 등수가 낮지만, 자신과 동일한 덩치끼리는 등수가 같다. 덩치값 배열이 주어졌을 때 각자의 등수를 입력된 순서대로 출력한다.
테스트 케이스
5 55 185 58 183 88 186 60 175 46 155
2 2 1 2 5
2 10 10 10 10
1 1
5 10 10 20 20 30 30 40 40 50 50
5 4 3 2 1
5 50 50 40 40 30 30 20 20 10 10
1 2 3 4 5
5 10 50 20 40 30 30 40 20 50 10
1 1 1 1 1
문제 풀이
각 인원에 대해 배열을 할 때 몸무게, 키와 더불어 N으로 초기화 되는 랭킹 변수를 선언한다. 이후 각 인원간에 비교를 진행하면서 A.weight > B.weight && A.height > B.height 처럼 명확한 경우에는 우위가 있는 쪽의 랭킹 값을 1 낮추고, 우위를 가릴 수 없는 경우에는 양쪽 모두의 랭킹값을 낮춘다. 조정이 모두 완료되면 입력된 순서대로 랭킹 값을 출력해준다.
풀이 코드
#include <iostream>
using namespace std;
int N;
cin >> N;
/*----------데이터 구성----------*/
// data[0] 몸무게
// data[1] 키
// data[2] 등수
/*-------------------------------*/
int** data = new int*[N];
for (int i = 0; i < N; i++)
{
data[i] = new int[3];
cin >> data[i][0] >> data[i][1];
data[i][2] = N;
}
/*----------덩치값 비교----------*/
for (int i = 0; i < N - 1; i++)
{
for (int j = i + 1; j < N; j++)
{
if (data[i][0] > data[j][0] && data[i][1] > data[j][1])
{// i가 j보다 덩치값이 크면
data[i][2]--;
}
else if (data[i][0] < data[j][0] && data[i][1] < data[j][1])
{// j가 i보다 덩치값이 크면
data[j][2]--;
}
else
{// 덩치값의 우위를 알 수 없으면
data[i][2]--;
data[j][2]--;
}
}
}
/*----------등수 출력하기----------*/
for (int i = 0; i < N; i++)
{
cout << data[i][2];
if (i != N - 1)
{
cout << ' ';
}
}
cout << "\n";
/*----------메모리 해제----------*/
for (int i = 0; i < N; i++)
{
delete[] data[i];
}
delete[] data;
