여기서는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 난이도 SIlver IV에 해당하는 문제인 9012번 괄호, 10845번 큐, 1920번 수 찾기 문제를 풀이하도록 하겠습니다.
9012번 : 괄호
괄호로 이루어진 문자열들을 입력받아, 각 문자열에서 괄호가 제대로 닫힌 올바른 문자열인지 검사하여 출력하는 문제입니다.
괄호가 어떻게 해야 제대로 닫히는지에 대한 조건을 생각해야하는 문제입니다.
문자열을 처리하는 과정이 상당히 귀찮을 수 있습니다.
#include<stdio.h>
int main() {
int N, state = 0, isVPS;
char c;
scanf("%d\n", &N);
for(int i=0; i<N; i++) {
state = 0;
isVPS = 1;
while(1) {
scanf("%c", &c);
if(c == '\n') break;
if(c == '(') state++;
else if(c == ')') state--;
if(state < 0) isVPS = 0;
}
if(state) isVPS = 0;
if(isVPS) printf("YES\n");
else printf("NO\n");
}
}
생각을 해보면 문자열이 올바른 VPS인지를 검사하는 조건은 2가지입니다.
첫 번째는, 여는 괄호와 닫는 괄호의 수가 동일해야 합니다.
두 번째는, 문자열 중간의 어느 지점에서도 여는 괄호의 수보다 닫는 괄호의 수가 많이 나오면 안됩니다.
따라서 우선 N개의 문자열 각각을 검사하기 위해 바깥 for문을 열어주고, 내부 for문에서는 각 문자를 입력받을 때마다 두 번째 조건을 계속 체크해줍니다.
state는 여는 괄호가 나오면 +1, 닫는 괄호가 나오면 -1을 하여 상태를 체크해주는 변수로, state가 중간에 음수가 되면 두 번째 조건을 만족하지 않음을 알 수 있습니다.
마지막에는 state가 0인지를 확인하여 첫 번째 조건을 확인해주면 됩니다.
10845번 : 큐
이전 포스트에서 다루었던 스택과 비슷한 부류의 자료구조 구현 문제입니다.
큐의 경우 후입선출인 스택과 다르게 선입선출의 형태로 데이터가 관리된다는 특징이 있습니다.
명령어가 10000개 이하로 주어지므로, push만 10000개 주어지더라도 배열은 10000칸 이상으로 사용될 수 없습니다. (front와 rear를 제외하고)
따라서 메모리에 대한 걱정은 하지 않아도 됨을 알 수 있습니다.
push, pop, size, empty, front, back의 함수들을 구현해보도록 하겠습니다.
#include<stdio.h>
#include<string.h>
int main() {
int N, queue[10005] = {0, }, front = 0, rear = 1, digit;
char input[20];
queue[front] = -1, queue[rear] = -1;
scanf("%d", &N);
for(int i=0; i<N; i++) {
scanf("%s", input);
if(!strcmp(input, "push")) {
scanf("%d", &digit);
queue[rear++] = digit;
queue[rear] = -1;
}
else if(!strcmp(input, "pop")) {
if(front+1 == rear) printf("-1\n");
else {
printf("%d\n", queue[front+1]);
queue[front++] = 0;
queue[front] = -1;
}
}
else if(!strcmp(input, "size")) printf("%d\n", rear-front-1);
else if(!strcmp(input, "empty")) printf("%d\n", front+1 == rear);
else if(!strcmp(input, "front")) printf("%d\n", queue[front+1]);
else if(!strcmp(input, "back")) printf("%d\n", queue[rear-1]);
}
}
함수들은 대부분 간단히 구현이 가능합니다.
명령어의 수가 1만개 이하로 제한되어있기 때문에, 크기가 1만인 1차원 배열을 선언하고 배열을 계속 뒤로 이동시키면서 사용해주어도 됩니다.
또한 front와 back과 같은 명령어의 경우 비어있는 큐일 때 front도 -1, back도 -1이므로 queue[front+1]이나 queue[rear-1]과 같이 출력해줘도 비어있는 경우까지 상관없이 구현이 됩니다.
1920번 : 수 찾기 (합병 정렬 Merge Sort + 이진 탐색 Binary Search 알고리즘 문제)
N개의 정수가 입력될 때 그 안에 어떤 정수가 존재하는지의 여부를 알아내는 코드를 작성하는 문제입니다.
다만 이 문제의 경우 난이도와 시간을 보았을 때, O(n^2)의 시간에는 해결하지 못할 가능성이 큽니다.
따라서 O(n log n) 시간 안에 해결하기 위해서 Merge Sort와 이진 탐색을 이용하도록 하겠습니다.
+ Quick Sort가 아닌 Merge Sort를 사용하는 이유는 문제에서 모든 정수들이 다른 값을 가진다는 조건을 알려주지 않았기 때문입니다. (같은 정수들이 있는 배열에서 Quick Sort를 수행할 시 무한 루프에 빠짐)
#include<stdio.h>
void merge(int A[], int p, int q, int r) {
int B[100005], i = p, j = q+1, k = p;
while(i<=q && j<=r) {
if(A[i] <= A[j]) B[k++] = A[i++];
else B[k++] = A[j++];
}
while(i<=q) B[k++] = A[i++];
while(j<=r) B[k++] = A[j++];
for(int a=p; a<=r; a++) A[a] = B[a];
}
void mergeSort(int A[], int p, int r) {
int q;
if(p < r) {
q = (p+r)/2;
mergeSort(A, p, q);
mergeSort(A, q+1, r);
merge(A, p, q, r);
}
}
int binarySearch(int A[], int N, int key) {
int low = 0, high = N-1, mid;
while(low <= high) {
mid = (low + high)/2;
if(key == A[mid]) return 1;
else if(key < A[mid]) high = mid - 1;
else if(key > A[mid]) low = mid + 1;
}
return 0;
}
int main() {
int N, M, A[100005], key;
scanf("%d", &N);
for(int i=0; i<N; i++) scanf("%d", &A[i]);
mergeSort(A, 0, N-1);
scanf("%d", &M);
for(int i=0; i<M; i++) {
scanf("%d", &key);
printf("%d\n", binarySearch(A, N, key));
}
}
정석적인 풀이는 위와 같습니다.
우선 mergeSort 함수는 수들을 묶음으로 분리하는 과정의 함수이고, merge는 이를 크기 순으로 합치는 함수입니다.
즉 mergeSort 함수가 실행된 이후 배열의 정수들은 오름차순으로 정렬이 되게 됩니다.
그 다음 binarySearch 함수는 이진탐색을 수행하는 함수로, 정렬되어 있는 배열에서 중점을 기준으로 계속 반으로 나누어 적절한 그룹을 찾아가며 수를 찾게 됩니다.
만약 최대한 key에 가깝게 도달했음에도 mid(현재 위치한 수)가 key에 해당하지 않는다면, 해당 수는 존재하지 않는 것이므로 0을 return 해주면 됩니다.