이번에 풀어볼 문제는 Baekjoon Online Judge의 solved.ac 난이도 기준 Silver V 난이도의 문제 1158번 : 요세푸스 문제, 1181번 : 단어 정렬, 1183번 : 약속이며, 문제 설명과 풀이 코드를 첨부하고, 풀이 알고리즘에 대한 해설도 같이 하도록 하겠습니다.
1158번 : 요세푸스 문제
N명의 사람이 있을 때, 남아있는 사람들 중 K번을 이동하여 지목된 사람을 계속해서 제거해나간다고 할 때, 제거되는 순서를 출력하는 문제입니다.
시작 번호는 항상 K로 고정이며, 이미 제거된 번호는 체크하면서 지나가기만 하면 되므로 특별이 어려울 것 없어보이는 문제입니다.
#include<stdio.h>
int main() {
int N, K, check[5002] = {0, }, cur;
scanf("%d %d", &N, &K);
cur = K;
printf("<%d", cur);
check[cur] = 1;
for(int i=0; i<N-1; i++) {
for(int j=0; j<K; j++) {
while(1) {
cur++;
if(cur > N) cur = 1;
if(!check[cur]) break;
}
}
printf(", %d", cur);
check[cur] = 1;
}
printf(">");
}
제가 해결한 방법은, 우선 이중 for문을 만들어 바깥쪽 loop는 N개의 번호가 모두 제거될 때까지 반복되는 구조이고, 안쪽 loop는 K개의 번호를 지나갈 때마다 하나씩 제거할 수 있도록 K개의 번호를 지나가는 용도로 반복되는 구조입니다.
cursor를 하나 선언하여 현재 체크하고 있는 번호가 어디인지를 확인하고, 또한 check라는 배열을 선언하여 0 또는 1로 제거된 번호인지 아닌지를 확인하는 용도로 사용합니다.
또한 출력 양식이 <번호, ... , 번호> 형태이기 때문에 마지막 번호만 따로 출력할지 첫 번째 번호만 따로 출력할지 선택해야 하는데, 저의 경우에는 첫 번째 번호가 K로 고정이기 떄문에 첫 번째 번호를 먼저 출력해주는 형식을 선택하였습니다.
1181번 : 단어 정렬
입력으로 주어진 단어들을 조건에 맞게 정렬하는 문제입니다.
다만 일반적인 단어 정렬과 다른 것은 길이순으로 먼저 정렬한 뒤, 길이가 동률일 때 사전순으로 정렬한다는 것입니다.
위의 스크린샷에는 나오지 않았지만 제한 시간이 짧기 때문에 O(n^2) 정렬 알고리즘을 사용할 수 없습니다.
#include<stdio.h>
#include<string.h>
void mergeSort(char word[][51], char temp[][51], int start, int end) {
int i = start, k = start, mid = (start + end)/2;
int j = mid + 1;
if(start >= end) return;
mergeSort(word, temp, start, mid);
mergeSort(word, temp, mid + 1, end);
while((i <= mid) && (j <= end)) {
if(strlen(word[i]) < strlen(word[j]) || (strlen(word[i]) == strlen(word[j]) && strcmp(word[i], word[j]) < 0)) temp[k][0] = '\0', strcpy(temp[k++], word[i++]);
else temp[k][0] = '\0', strcpy(temp[k++], word[j++]);
}
while(i <= mid) temp[k][0] = '\0', strcpy(temp[k++], word[i++]);
while(j <= end) temp[k][0] = '\0', strcpy(temp[k++], word[j++]);
for(i=start; i<=end; i++) word[i][0] = '\0', strcpy(word[i], temp[i]);
}
int main() {
int n;
char word[20001][51], temp[20001][51];
scanf("%d", &n);
for(int i=0; i<n; i++) scanf("%s", word[i]);
mergeSort(word, temp, 0, n-1);
for(int i=0; i<n; i++) {
if(!strcmp(word[i], word[i+1])) continue;
printf("%s\n", word[i]);
}
}
처음에는 퀵 정렬을 이용해서 구현을 하려 했으나, 퀵 정렬의 경우 데이터의 순위가 같은 경우는 고려하지 않기 때문에 Merge 정렬을 이용하였습니다.
정렬 조건은, strlen 함수를 이용하여 길이 비교를 우선으로 하고, 만약 길이가 같을 경우 strcmp 함수를 이용하여 사전순으로 앞에 오는 단어가 먼저 오도록 순서를 바꾸어줍니다.
단어를 교체하거나 배열 사이에서 문자열 사이에서 이동시킬 때는 문자열 입력이 끝난 뒤 그 뒤에 널문자를 넣어 오류가 발생하지 않도록 안전하게 작성해줍니다.
1183번 : 약속
이 문제는 절댓값에 관련된 문제인데, 수학적인 문제를 적절하지 않은 상황에 어거지로 끼워맞추려다 보니까 문제 자체의 난이도보다 문제가 무슨 상황인지 이해하기가 더 힘든 문제입니다.
쉽게 말해, abs(S[i]+T-A[i]) = abs(A[i]-S[i]-T)의 총합이 최소가 되는 T가 몇 개나 존재하는지를 구하여 출력하는 문제입니다.
이를 수식 자체만으로 한번에 이해하면 좋겠지만, 그래프를 이용해서 풀면 훨씬 쉽게 이해가 가능하므로 Desmos Graph를 이용하여 그래프로 직접 보여드리겠습니다.
우선 식에서 A[i]-S[i]는 입력되는 정해진 값이므로 수식에서는 상수로 볼 수 있습니다.
따라서 만약 만나는 사람의 쌍의 수가 홀수일 때, 그래프의 예시는 대략적으로 위와 같이 그려볼 수 있습니다.
그려 보면 그래프의 최솟값이 반드시 존재하기 때문에 N이 홀수일 때 T의 개수는 1개입니다.
그 다음 만나는 사람의 쌍의 수가 짝수일 때, 그래프의 예시는 대략적으로 위와 같이 그려볼 수 있습니다.
그려보면 가운데 두 개의 값을 경계로 그 안쪽에 있는 값들은 모두 최솟값이므로, N이 짝수일 때 T의 개수는 가운데 두 정수의 차 + 1입니다. (양 끝에 존재하는 정수까지 포함해야 하므로)
#include<stdio.h>
int main() {
int N, A[10001] = {0, }, S[10001] = {0, }, diff[10001] = {0, }, temp;
scanf("%d", &N);
for(int i=0; i<N; i++) scanf("%d %d", &A[i], &S[i]);
if(N%2) {
printf("1");
return 0;
}
else {
for(int i=0; i<N; i++) diff[i] = A[i]-S[i];
for(int i=N-1; i>0; i--)
for(int j=0; j<i; j++)
if(diff[j] > diff[j+1]) {
temp = diff[j];
diff[j] = diff[j+1];
diff[j+1] = temp;
}
printf("%d", diff[N/2] - diff[(N/2)-1] + 1);
}
}
따라서 결과적으로 답만 출력하면 되기 때문에, N의 홀짝에 따라 위에서 얻어낸 결론만 구해주도록 합니다.
우선 N이 홀수인 경우에는 1을 출력하고 프로그램을 종료하도록 합니다.
만약 N이 짝수인 경우에는, A[i]-S[i] 값의 정렬이 우선적으로 필요하므로, 정렬을 먼저 해줍니다. (위의 문제와 다르게 시간 제한이 촉박한 문제가 아니므로 O(n^2)의 bubble sort를 이용해도 됩니다.)
이후 정렬이 되고 나서 가운데 두 값들의 차 + 1을 답으로 출력해주도록 하면 됩니다.