백준 문제에 적용하기
이번 글에서는 지금까지 구현한 큐, 원형 큐, 덱을 실제 문제에 활용하는 것을 작성하려 한다. 백준 온라인 저지 -> '문제' -> '단계별로 풀어보기' -> '큐, 덱'에 포함되는 문제들이다.
① 18258번: 큐 2
문제 소개, 풀이 방법
문제를 요약하면 위처럼 큐와 관련된 명령어를 받아 그에 맞는 함수를 실행시키는 것이다.
명령어를 입력 받을 횟수가 정해지므로 for문을 사용하여 N번만큼 반복하였다. 입력된 명령어를 저장할 문자열을 선언하고 문자열에 저장된 명령어가 어떤 명령어인지 if문과 strcmp 함수로 검사하여 그에 맞는 함수를 실행하면 될 것 같다.
풀이
큐에 대한 내용은 이전 게시물에 있으므로 메인 함수를 어떻게 구성하였는지만 공유했다. 문자열을 입력 받고 strcmp 함수를 활용하여 풀었다.
메인 함수를 보기 전에 큐의 배열에 저장되는 요소의 정의를 수정해야 한다. 이전에는 변수 age와 name으로 구성되었지만 지금은 정수를 저장하므로 구조체로 정의할 필요가 없었다.
typedef int Element;이제 main.c의 내용을 살펴보자.
int main(void)
{
Queue* queue = QueCreate();
if (queue == NULL || queue->darr == NULL)
return;
int N;
scanf("%d", &N);
char commend[MAX_CMD];
Element num;
for (int i = 0; i < N; i++) {
scanf("%s", commend);
if (strcmp(commend, "push") == 0) {
scanf("%d", &num);
QueEnqueue(queue, num);
}
else if (strcmp(commend, "pop") == 0) {
if (QueDequeue(queue, &num))
PrintInt(&num);
else printf("%d\n", -1);
}
else if (strcmp(commend, "front") == 0) {
if (QueIsEmpty(queue) != TRUE) {
DAGet(queue->darr, 0, &num);
PrintInt(&num);
}
else printf("%d\n", -1);
}
else if (strcmp(commend, "back") == 0) {
if (QueIsEmpty(queue) != TRUE) {
DAGet(queue->darr, queue->index, &num);
PrintInt(&num);
}
else printf("%d\n", -1);
}
else if (strcmp(commend, "size") == 0) {
printf("%d\n", queue->index + 1);
}
else if (strcmp(commend, "empty") == 0) {
printf("%d\n", QueIsEmpty(queue));
}
else printf("잘못된 명령어\n");
}
QueDestroy(queue);
}크게 어려운 내용이 없다. 바로 제출하려 했는데 생각해보니 분할 컴파일로 실행했기 때문에 제출하기가 매우 불편하다. 각각의 소스 파일의 내용을 모두 복사해서 하나의 파일로 옮겨야 한다. 순간 머리가 지끈거리면서 그냥 c++이나 java로 아주 간단한 클래스를 구현할걸 하는 생각이 들었다.
하나의 파일로 옮기니 246줄이나 되었다. 아..
그리고 제출 결과는 '시간 초과'가 떴다. 명령의 수 N의 최대값이 2,000,000이었기 때문에 예상했던 일이다. 가장 시간을 많이 필요로 할 것으로 예상되는 부분은 역시 pop연산이다. 데이터를 삭제할 때마다 많은 값이 복사될 것이기 때문이다.
이런 부분을 고려하여 만든 것이 원형 큐인 만큼, 원형 큐의 소스를 가져와 위에서 작성한 코드를 실행해본다.
int main(void)
{
CircularQueue* cqueue = CQueCreate();
if (cqueue == NULL || cqueue->arr == NULL)
exit(1);
int N;
scanf("%d", &N);
char commend[MAX_CMD];
Element num;
for (int i = 0; i < N; i++) {
scanf("%s", commend);
if (strcmp(commend, "push") == 0) {
scanf("%d", &num);
CQueEnqueue(cqueue, num);
}
else if (strcmp(commend, "pop") == 0) {
if (CQueDequeue(cqueue, &num))
PrintInt(&num);
else printf("%d\n", -1);
}
else if (strcmp(commend, "front") == 0) {
if (CQueIsEmpty(cqueue) != TRUE) {
num = cqueue->arr[cqueue->front];
PrintInt(&num);
}
else printf("%d\n", -1);
}
else if (strcmp(commend, "back") == 0) {
if (CQueIsEmpty(cqueue) != TRUE) {
int idx = ((cqueue->rear - 1) + MAX_LEN) % MAX_LEN;
num = cqueue->arr[idx];
PrintInt(&num);
}
else printf("%d\n", -1);
}
else if (strcmp(commend, "size") == 0) {
printf("%d\n", CQueGetSize(cqueue));
}
else if (strcmp(commend, "empty") == 0) {
printf("%d\n", CQueIsEmpty(cqueue));
}
else printf("잘못된 명령어\n");
}
CQueDestroy(cqueue);
}원형 큐에서는 큐와 달리 동적 배열을 활용하지 않았기 때문에 메인 함수의 내용을 생각보다 많이 수정했다.
성공하긴 했는데 이렇게까지 할 일인가라는 생각이 들기 시작한다.
② 11866번: 요세푸스 문제 0
문제 소개, 풀이 방법
내 앞에 N명이 사람이 한 줄로 서 있는 상황을 상상했다. 나는 속으로 1번부터 카운트하여 K번째가 올 때마다 바로 앞 사람을 줄에서 제거한다. K번째가 아니라면 줄의 맨 뒤로 보내 다시 서게 한다.
큐의 성질을 이용하면 이 문제를 풀 수 있다. 저장된 순서대로 (1부터 N까지) pop연산으로 하나씩 꺼내어 K번째인지 검사하고, K번째가 아니라면 다시 push하여 저장한다. 이 때 push된 데이터는 맨 뒤에 저장된다. 이 과정을 반복하다가 K번째 데이터가 오면 다시 push하지 않음으로써 완전히 제거한다.
풀이
int main(void)
{
CircularQueue* cqueue = CQueCreate();
if (cqueue == NULL || cqueue->arr == NULL)
exit(1);
int N, K;
scanf("%d %d", &N, &K);
for (int i = 1; i <= N; i++)
CQueEnqueue(cqueue, i);
int count = 0;
printf("<");
while (CQueIsEmpty(cqueue) != TRUE) {
count++;
Element tmp;
CQueDequeue(cqueue, &tmp);
if (count % K == 0) {
if (CQueIsEmpty(cqueue) == TRUE)
printf("%d>\n", tmp);
else printf("%d, ", tmp);
//else PrintInt(&tmp);
count = 0;
}
else CQueEnqueue(cqueue, tmp);
}
CQueDestroy(cqueue);
}위에서 설명한 방법을 코드로 그대로 옮긴 것이다.
주석 처리된 부분은 기존에 구현한 출력 함수 PrintInt를 사용하여 제출하니까 계속 '틀렸습니다.'라는 결과가 나와서 수정한 것이다.
출력하는 함수에 이상이 있을 거라는 생각은 못했다. 예시로 주어진 7, 3을 입력해도 정확히 출력되고, '질문 검색'에서 다른 사람들의 반례를 모두 대입해봐도 정확한 결과가 출력되어서 내 코드의 오류를 찾는데 애를 먹었다.
③ 10866번: 덱
문제 소개, 풀이 방법
앞서 가장 먼저 풀이한 '18258번: 큐 2'와 결이 같은 문제이다. if문과 strcmp 함수를 활용하면 빠르게 풀 수 있을 것 같다.
풀이
int main(void)
{
Deque* deque = DQueCreate();
if (deque == NULL || deque->arr == NULL)
exit(1);
int N;
scanf("%d", &N);
char commend[MAX_CMD];
Element num;
for (int i = 0; i < N; i++) {
scanf("%s", commend);
if (strcmp(commend, "push_front") == 0) {
scanf("%d", &num);
DQueAddFirst(deque, num);
}
else if (strcmp(commend, "push_back") == 0) {
scanf("%d", &num);
DQueAddLast(deque, num);
}
else if (strcmp(commend, "pop_front") == 0) {
if (DQueRemoveFirst(deque, &num))
PrintInt(&num);
else printf("%d\n", -1);
}
else if (strcmp(commend, "pop_back") == 0) {
if (DQueRemoveLast(deque, &num))
PrintInt(&num);
else printf("%d\n", -1);
}
else if (strcmp(commend, "front") == 0) {
if (DQueGetFirst(deque, &num)) {
PrintInt(&num);
}
else printf("%d\n", -1);
}
else if (strcmp(commend, "back") == 0) {
if (DQueGetLast(deque, &num)) {
PrintInt(&num);
}
else printf("%d\n", -1);
}
else if (strcmp(commend, "size") == 0) {
printf("%d\n", DQueGetSize(deque));
}
else if (strcmp(commend, "empty") == 0) {
printf("%d\n", DQueIsEmpty(deque));
}
else printf("잘못된 명령어\n");
}
DQueDestroy(deque);
}각 명령어에 맞는 함수를 실행시키면 된다.
