입력받은 N개의 문자를 길이가 짧은 순서대로 출력한다. 길이가 동일할 경우 사전순으로 출력한다. 단, 같은 단어를 한 번만 출력한다.
테스트 케이스
13 but i wont hesitate no more no more it cannot wait im yours
i im it no but more wait wont yours cannot hesitate
문제 풀이
문제에서 제시한 규칙에 맞춰 algorithm의 sort 함수에 사용할 비교용 함수를 만들면 된다. 비교용 함수를 만들기 싫다면 문자열 길이별로 묶어서 각 길이마다 sort 하는 방식을 사용해도 된다. 출력 시에는 현재 문자열과 이전 or 다음 문자열과 비교하여 동일하지 않으면 출력하도록 한다.
풀이 코드
#include <iostream>
#include <iostream>
#include <string>
using namespace std;
// 비교함수를 만들어서 sort 하는 경우
bool cmp_1181(const string& left, const string& right)
{
if (left.length() == right.length())
{
return left < right;
}
return left.length() < right.length();
}
void BAEKJOON_1181()
{
int N;
cin >> N;
string* word = new string[N + 1];
for (int i = 0; i < N; ++i)
{
cin >> word[i];
}
sort(word, word + N, cmp_1181);
for (int i = 0; i < N; ++i)
{
if (word[i] == word[i + 1])
{
continue;
}
cout << word[i] << "\n";
}
delete[] word;
return;
}
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// length별로 그룹을 나눈 후 sort 하는 경우
void BAEKJOON_1181()
{
int N;
cin >> N;
string word;
vector<string> wordList[51];
for (int i = 0; i < N; ++i)
{
cin >> word;
wordList[word.size()].push_back(word);
}
for (int i = 0; i < 51; ++i)
{
sort(wordList[i].begin(), wordList[i].begin() + wordList[i].size());
for (auto it = wordList[i].begin(); it != wordList[i].end(); ++it)
{
if (it != wordList[i].begin())
{
if (*it == *(it - 1))
{
continue;
}
}
cout << *it << "\n";
}
}
return;
}
입력된 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;
}
