So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

yes
yes
no
no
no
yes
yes

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char check(char* start, char* end) {
	int check_small = 0;
	int check_big = 0;
	char* position_small = NULL;
	char* position_big = NULL;

	char* small_history[101] = { NULL };
	char* big_history[101] = { NULL };
	int small_history_index = 0;
	int big_history_index = 0;

	
	for (char* i = start; i <= end; i++) {
		if (*i == '(') {
			check_small++;
			position_small = i;
			small_history[small_history_index++] = position_small;
		}
		else if (*i == '[') {
			check_big++;
			position_big = i;
			big_history[big_history_index++] = position_big;
		}
		else if (*i == ')') {
			check_small--;
			if (check_small < 0 || check_big < 0) {
				return 0;
			}
			if (check(position_small + 1, i - 1) == 0)
				return 0;
			if (small_history_index >= 2) {
				small_history_index--;
				position_small = small_history[small_history_index-1];
			}
				
			else
				position_small = NULL;
			
		}
		else if (*i == ']') {
			check_big--;
			if (check_small < 0 || check_big < 0) {
				return 0;
			}
			if (check(position_big + 1, i - 1) == 0)
				return 0;
			if (big_history_index >= 2) {
				big_history_index--;
				position_big = big_history[big_history_index-1];
			}
				
			else
				position_big = NULL;
		}
		
	}
	if (check_small == 0 && check_big == 0) {
		return 1;
	}
	else {
		return 0;
	}
	
}

char check_gpt(char* start, char* end) {
	char stack[101]; // 스택으로 사용할 배열
	int stackIndex = 0; // 스택의 현재 인덱스
	for (char* i = start; i != end; i++) {
		if (*i == '(' || *i == '[') {
			// 여는 괄호를 스택에 추가
			stack[stackIndex++] = *i;
		}
		else if (*i == ')' || *i == ']') {
			// 스택이 비었거나, 짝이 맞지 않는 경우
			if (stackIndex == 0 || (stack[stackIndex - 1] == '(' && *i != ')') || (stack[stackIndex - 1] == '[' && *i != ']')) {
				return 0;
			}
			// 짝이 맞는 경우 스택에서 제거
			stackIndex--;
		}
	}
	// 스택이 비어있지 않다면 괄호의 짝이 맞지 않음
	return stackIndex == 0 ? 1 : 0;
}

int main() {
	char input[101] = { 0, };
	char* end_of_string = NULL;

	while (1) {
		fgets(input, sizeof(input), stdin);
		end_of_string = strrchr(input, '.');

		if (end_of_string == NULL) //'.'을 안친 경우
			continue;

		if (end_of_string == input) // '.'만 친 경우
			break;
		else {
			if (check_gpt(input, end_of_string))
				printf("yes\n");
			else
				printf("no\n");
		}
			
	}
	return 0;
}

본래 생각했던 풀이 방법은, '('와 '['의 위치를 계속 기록하고, 만약 괄호가 닫힌다면 괄호 사이에 있는 문자열을 인자로 재귀호출하여, 내부 문장이 적절한지 판단하는 방법이였다.

이전 괄호의 위치를 포인터 배열로 관리하며, 재귀호출로 인해 코드가 읽기 힘들고, 비효율적으로 동작하는 안좋은 코드가 만들어졌다.

반면 gpt가 작성한 코드는 stack을 이용해서 짝이 맞는 경우아 최종적으로 스택에 아무것도 남지 않을 경우 1을 리턴, 짝이 맞지 않는 경우 0을 리턴하는 코드를 작성하였다. 이는 훨씬 직관적이고 이해하기 쉬우며, 효율적이다.

함수를 직관적으로 작성하다 재귀함수를 사용해야 할 경우, 스택을 이용해볼 생각을 하는게 좋다고 한다.

하지만, 스택을 이용했을때 보기 더 힘들거나, 재귀 함수를 이용하므로써 tail recursion optimization을 받을 수 있는 경우엔 재귀 함수를 사용하는게 더 좋다고 한다.

자료구조를 배운 만큼, 사용해보려 노력해야겠다 ㅜ

7 3

<3, 6, 2, 7, 5, 1, 4>

해당 문제는 queue를 이용해서, 일정한 간격대로 pop하는 문제이다.

본인은 이 문제를 출제 의도에 맞지 않게 풀었는데, 방법으론 원형 링크드 리스트를 사용해 모든 수를 출력할때까지, 일정한 간격으로 출력하는 방법이였다. 의도에 맞지 않게 풀었기에, 코드가 보기 좋지 않다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct CircleQueue {
	int id;
	char is_out;
	struct CircleQueue* next;
}UserQueue;

int main() {
	int n, k;
	int printed_num = 0, count = 1;
	scanf("%d %d", &n, &k);
	UserQueue* p = (UserQueue*)malloc(sizeof(UserQueue) * n);

	for (int i = 0; i < n - 1; i++) {
		p[i].id = i + 1;
		p[i].is_out = 0;
		p[i].next = &p[i + 1];
	}

	p[n-1].id = n; //원형 링크드 리스트를 위해 직접 초기화
	p[n-1].is_out = 0;
	p[n-1].next = &p[0];//마지막 구조체는 첫 구조체를 가리킴

	UserQueue* temp = &p[0]; //체크를 위한 임시 구조체 할당, 첫번째 사람으로 설정

	while (printed_num != n) { //다 출력할때까지 반복


		while (count != k) { //나갈 차례가 될 때까지 반복
			if (temp->is_out == 0)//나가지 않은 사람들은 
				count++; //count. 나간 사람의 자리도 count하지 않기 위함
			temp = temp->next; //다음 자리로
		}

		//나갈 차례가 된 경우
		if (count == k && temp->is_out != 1) { //차례가 되었고 해당 자리가 나간 사람의 자리가 아닌 경우
			if (printed_num == 0) {//첫 출력일 경우, 
				printf("<%d", temp->id); //'<'를 붙여줌
			}
			else {//기본 출력 양식
				printf(", %d", temp->id);
			}
			printed_num++; //출력된 횟수 업데이트
			
			count = 1; //count 초기화
			temp->is_out = 1; //나간 자리로 표시
		}
		//차례가 되었지만 해당 자리가 나간 사람의 자리인 경우, pass

		temp = temp->next; //다음 자리로 
	}
	printf(">"); //출력이 끝난 경우, '>'을 붙여줌

	free(p);

	return 0;
}

이 문제를 푸는 정석 코드는 다음과 같다.

//#11866 요세푸스 문제 0
#include <stdio.h>
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
int n,k;

int main()
{
	scanf("%d %d", &n, &k);
	queue<int> q;
	for(int i=1; i<=n; i++)
		q.push(i);
		
	int t = 1;
	cout << "<";
	while(q.size()>1) 
	{
		if(t%k==0)
		{
			cout << q.front() << ", ";
			q.pop();
		}
		else
		{
			q.push(q.front());
			q.pop();
		}
		t++;
	}
	cout << q.front()<<">";
}

//출처: 백준, id : myjun0321

15
push_back 1
push_front 2
front
back
size
empty
pop_front
pop_back
pop_front
size
empty
pop_back
push_front 3
empty
front

2
1
2
0
2
1
-1
0
1
-1
0
3

22
front
back
pop_front
pop_back
push_front 1
front
pop_back
push_back 2
back
pop_front
push_front 10
push_front 333
front
back
pop_back
pop_back
push_back 20
push_back 1234
front
back
pop_back
pop_back

-1
-1
-1
-1
1
1
2
2
333
10
10
333
20
1234
1234
20

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int deque[200001];
int front_index = 100000;
int back_index = 100001;

int size() {
	return (back_index - front_index) - 1;
}
char empty() {
	if (size() == 0)
		return 1;
	else
		return 0;
}

void push_front(int num){
	deque[front_index--] = num;
}

void push_back(int num){
	deque[back_index++] = num;
}

int pop_front() {
	if (!empty()) {
		front_index++;
		return deque[front_index];
	}
	return -1;
}
int pop_back() {
	if (!empty()) {
		back_index--;
		return deque[back_index];
	}
	return -1;
}

int front() {
	if(!empty())
		return deque[front_index + 1];
	return -1;
}
int back() {
	if(!empty())
		return deque[back_index - 1];
	return -1;
}

int main() {
	int num = 0;
	char line[100] = { 0, };
	char cmd[11] = { 0, };
	int arg = 0;

	scanf("%d", &num);
	fgets(line, sizeof(line), stdin);

	for (int i = 0; i < num; i++) {
		memset(line, 0, sizeof(line));
		memset(cmd, 0, sizeof(cmd));
		arg = 0;

		fgets(line, sizeof(line), stdin);
		sscanf(line, "%s %d", cmd, &arg);

		if (!strncmp("push_front", cmd, 10)) {
			push_front(arg);
		}
		else if (!strncmp("push_back", cmd, 9)) {
			push_back(arg);
		}
		else if (!strncmp("pop_front", cmd, 9)) {
			printf("%d\n", pop_front());
		}
		else if (!strncmp("pop_back", cmd, 8)) {
			printf("%d\n", pop_back());
		}
		else if (!strncmp("size", cmd, 4)) {
			printf("%d\n", size());
		}
		else if (!strncmp("empty", cmd, 5)) {
			printf("%d\n", empty());
		}
		else if (!strncmp("front", cmd, 5)) {
			printf("%d\n", front());
		}
		else if (!strncmp("back", cmd, 4)) {
			printf("%d\n", back());
		}
	}
}

전역변수로 아주 거대한 배열을 덱으로 활용하려 할당하였다.

덱은, 스택과 큐를 섞어놓은 자료구조로 front, back 모두 입출력이 가능하다.

특징으로 pop 연산은, 인덱스만 조정후 덱을 초기화하진 않는다.

따라서, 큰 배열 전체를 검색하여 사이즈를 구하는것에 비해 인덱스를 이용하여 사이즈를 계산하므로 더 빠른 동작을 할 수 있다.

하지만, 해당 코드에 인덱스값에 이상이 생기는 순간 보안취약점이 생기므로 인덱스 확인 로직 추가, 좀 더 효율적인 공간 할당방법을 택하면 좋은 코드가 되지 않을까?

또한 새로 배운점으로, 

stdin에 엔터를 기준으로 스트링을 받아놓은 후, 띄어쓰기를 기준으로 sscanf를 이용해 다시 스트링의 위치를 할당할 수 있다. (c언어의 입출력은 항상 까다로운것 같다)

6

4

이 문제는 STL을 활용하여 간단하게 풀 수 있다.

문제에서 카드를 섞고 버리는 방식은 queue 자료구조 (FIFO)이므로, c++ 의  queue라이브러리를 활용하여 작성하였다.

#include <queue>
#include <iostream>
using namespace std;
int main() {
	queue<int> q;
	int num, temp;
	cin >> num;

	//initial
	for (int i = 1; i <= num; i++) {
		q.push(i);
	}

	//pop_push
	while (q.size() != 1) {
		temp = 0; //initialize

		q.pop();
		temp = q.front();
		q.pop();
		q.push(temp);

	}

	cout << q.front();
}

1부터 차례로 카드를 쌓으므로 for문을 활용하여 차례대로 push하고, 

while문에서 첫 카드를 버리고 (pop), 두번째 카드를 뽑아 가장 아래 위치로 넣는 작업 (temp에 front를 저장한 후, pop, push(temp)) 을 구현하였다.

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

1
2
5

큐를 직접 구현하는것도 좋지만, 이번엔 stl문제인 만큼 오랜만에 c++ 라이브러리를 활용하여 풀어보았다.

#include <iostream>
#include <deque>
using namespace std;

struct PrintJob {
	int priority;
	bool check;
};

void printer_queue(int num_of_document, int index_of_searching){
	
	int most_prior = 0;
	int num_printed = 1;
	std::deque<PrintJob> q1;
	struct PrintJob temp = { 0,0 };

	//우선순위 배열 입력받기
	for (int i = 0; i < num_of_document; i++) {
 		std::cin >> temp.priority;

		if (i == index_of_searching) {
			temp.check = 1;
			q1.push_back(temp);
		}
		else {
			temp.check = 0;
			q1.push_back(temp);
		}
	}

	while (q1.size() != 0) {
		most_prior = 0; //초기화

		for (int i = 0; i < q1.size(); i++) { //가장 우선순위 탐색
			if (q1[i].priority > most_prior)
				most_prior = q1[i].priority;
		}

		while (q1[0].priority != most_prior) { //가장 앞의 문서가 가장 우선순위가 높은 문서일때까지
			if (q1[0].priority < most_prior) { //우선순위가 낮은 문서는 뒤로
				temp = q1[0];
				q1.pop_front();
				q1.push_back(temp);
			}
		}

		if (q1[0].check == 1) { //찾는 문서이면 출력 횟수를 출력한 후, 리턴
			cout << num_printed << endl;
			return;
		}
		else { //찾는 문서가 아닐 경우, pop하고 다시 탐색
			q1.pop_front();
			num_printed++;	
		}
		
	}
	

}


int main() {
	int num_of_testcase;
	int num_of_document;
	int index_of_searching;

	std::cin >> num_of_testcase;
	for (int i = 0; i < num_of_testcase; i++) {
		std::cin >> num_of_document; 
		std::cin >> index_of_searching; 
		printer_queue(num_of_document, index_of_searching);
	}
	return 0;
}

8
4
3
6
8
7
5
2
1

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

5
1
2
5
3
4

NO

 스택이 오름차순으로 올라갈 수 있다.

문제를 예를 들어서 설명하면, 만약 3가지 숫자의 배열 1 3 2 를 스택에 넣고 빼서 구현하고 싶다면, 

스택에 1을 push

스택 상단에서 1을 pop

스택에 2를 push

스택에 3을 push

스택 상단에서 3을 pop

스택 상단에서 2를 pop

하면 된다.

이를 코드로 구현하면, 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct stack {
	int stack[100001];
	int stack_index;
	int high_num; //넣은 수 중 가장 큰 수
} custom_stack;


void push(custom_stack* p, char* ans, int search_value) {
	do {
		p->high_num++;
		p->stack[p->stack_index++] = p->high_num;
		strncat(ans, "+\n", 3);//printf("+\n");
	} while (p->high_num != search_value);
}

/*
* sequence_sort의 반환값은, 
* 1 이상의 정수를 리턴할 경우, 해당 값은 스택 최상단에서 pop 된 값이고
* 0 을 반환할 경우 에러이다.
*/
int sequence_sort(custom_stack* p, char* ans, int search_value, int num) {
	//search and pop
	if (search_value <= p->high_num) {//이전에 넣은 수보다 작은 값을 찾으면 스택 최상단에서 찾고, 
		if (p->stack[p->stack_index - 1] == search_value) {
			strncat(ans, "-\n", 3);
			return p->stack[--(p->stack_index)]; //pop
		}
		else {
			return 0; //case NO
		}
	}
	else if (search_value <= num) { //이전에 넣은 수보다 큰 값을 찾으면 push, 대신 num 범위 안에서만
		push(p, ans, search_value);
		strncat(ans, "-\n", 3);//printf("-\n");
		return p->stack[--(p->stack_index)];
	}
	else
		return 0;
}

int main() {
	int num = 0;
	scanf("%d", &num); //user input 1

	//declare
	int flag = 1;
	int* array = (int*)malloc(sizeof(int) * num);
	char* ans = (char*)malloc(sizeof(char) * 400001);
	custom_stack* my_stack = (custom_stack*)malloc(sizeof(custom_stack));
	
	//initialization
	if (ans != NULL && my_stack != NULL && array != NULL) {
		memset(array, 0, sizeof(array)); //int pointer array
		memset(ans, 0, sizeof(ans)); //char pointer ans
		memset(my_stack->stack, 0, sizeof(my_stack->stack)); //struct pointer my_stack
		my_stack->high_num = 0;
		my_stack->stack_index = 0;
	}
	else {
		printf("Allocation failed\n");
		return -1;
	}

	for (int i = 0; i < num; i++) {
		scanf("%d", &array[i]);  //user input 2~N
	}
	for (int i = 0; i < num && flag; i++) {
		flag = sequence_sort(my_stack, ans, array[i], num);
	}
	if (flag) {
		printf("%s", ans);
	}
	else
		printf("NO\n");

	//free allocated area
	free(array);
	free(my_stack);
	free(ans);

	return 0;
}

 코드의 특징으론, 전역변수를 많이 사용하거나 함수 인자를 많이 사용하지 않기 위해 구조체를 사용하였고, 

답안을 제출하기 위해 "ans"  char 포인터를 선언하였고, +,-를 strncpy로 공간에 넣어준다.

또한, 만약에 불가능한 경우가 조건문에 걸린다면, "flag"로 설정한 "sequence_sort" 반환값을 활용하여(오류일 경우 반환값이 0) for 루프의 동작을 멈추고, NO를 출력하도록 하였다.

 array의 크기를 100,001로 설정한 이유는, 문제의 조건에서 N의 최댓값이 100,000이라고 하였고, 현재 스택 포인터는 가장 앞(가장 밑)에 비어있는 스택 위치를 가리키도록 설정하였기 때문에, worst-case인 100,000개가 모두 들어왔을 경우, index는 100,001을 가르키고 있기 때문이다.

또한, ans 배열의 크기를 400,001로 설정한 이유는, 한개의 데이터에 push-pop 두가지 연산이 와야하므로 100,000 x 2 = 200,000에, push-pop 각각 "+\n", "-\n" 2글자씩 들어가므로 (\n은 문자 하나로 메모리에 들어간다) 200,000 x 2 = 400,000에, worst-case 경우 null값까지 고려하여 400,001로 설정하였다. 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef enum{
    PUSH,
    POP,
    SIZE,
    EMPTY,
    FRONT,
    BACK,
    UNKNOWN    
} CommandType;

void push(int **q_front, int **q_back); //정수 X를 큐에 넣는 연산이다.
int pop(int **q_front, int **q_back); //큐에서 가장 앞에 있는 정수를 빼고, 그 수를 리턴한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 리턴한다.
int size(int **q_front, int **q_back); //큐에 들어있는 정수의 개수를 리턴한다.
int empty(int **q_front, int **q_back); //큐가 비어있으면 1, 아니면 0을 리턴한다.
int front(int **q_front, int **q_back); //큐의 가장 앞에 있는 정수를 리턴한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 리턴한다.
int back(int **q_front, int **q_back); //큐의 가장 뒤에 있는 정수를 리턴한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 리턴한다.

CommandType getCommandType(const char* input){
    if (strcmp(input, "push") == 0 || strcmp(input, "PUSH") == 0)
        return PUSH;
    else if (strcmp(input, "pop") == 0 || strcmp(input, "POP") == 0)
        return POP;
    else if (strcmp(input, "size") == 0 || strcmp(input, "SIZE") == 0)
        return SIZE;
    else if (strcmp(input, "empty") == 0 || strcmp(input, "EMPTY") == 0)
        return EMPTY;
    else if (strcmp(input, "front") == 0 || strcmp(input, "FRONT") == 0)
        return FRONT;
    else if (strcmp(input, "back") == 0 || strcmp(input, "BACK") == 0)
        return BACK;
    else 
        return UNKNOWN;
}

int main(int argc, char *argv[]){
    int number_of_commands = 0;
    int i = 0, j = 0;
    char user_input_command[6];
    int *queue;
    int *q_front, *q_back;

    scanf("%d",&number_of_commands);

    if(number_of_commands > 10000 || number_of_commands < 1)
        return -1;

    queue = (int *)malloc(sizeof(int)*number_of_commands);
    q_front = queue;
    q_back = queue;

    for(i = 0; i < number_of_commands; i++){
        scanf("%s", user_input_command);
        CommandType cmd = getCommandType(user_input_command);
        
        switch(cmd){
            case PUSH:
                push(&q_front, &q_back);
                break;
            case POP:
                printf("%d\n",pop(&q_front, &q_back));
                break;
            case SIZE:
                printf("%d\n",size(&q_front, &q_back));
                break;
            case EMPTY:
                printf("%d\n",empty(&q_front, &q_back));
                break;
            case FRONT:
                printf("%d\n",front(&q_front, &q_back));
                break;
            case BACK:
                printf("%d\n",back(&q_front, &q_back));
                break;
            case UNKNOWN:
                break;
            default:
                printf("Error on switch.\n");
                return -1;                
        }

        //memset(user_input_command, 0, sizeof(user_input_command));
    }
    free(queue);
    return 0;
}

void push(int **q_front, int **q_back){
    int X = 0;
    scanf("%d",&X);
    if(X <= 100000 && X >= 1){
        **q_back = X;
        (*q_back)++; 
    }
    
}//정수 X를 큐에 넣는 연산이다.

int pop(int **q_front, int **q_back){
    if(*q_front == *q_back)
        return -1;
    int temp = **q_front;
    (*q_front)++;
    return temp;
} //큐에서 가장 앞에 있는 정수를 빼고, 그 수를 리턴한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 리턴한다.

int size(int **q_front, int **q_back){
    if(*q_back == *q_front)
        return 0;
    else
        return (*q_back - *q_front);// / sizeof(int)라 생각했으나, 컴파일러에서 포인터간의 차를 계산할때 자동으로 타입 크기로 나눠준다고 한다!;
} //큐에 들어있는 정수의 개수를 리턴한다.

int empty(int **q_front, int **q_back){
    return *q_front == *q_back;
} //큐가 비어있으면 1, 아니면 0을 리턴한다.

int front(int **q_front, int **q_back){
    if(*q_front != *q_back)
        return **q_front;
    else
        return -1;
} //큐의 가장 앞에 있는 정수를 리턴한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 리턴한다.

int back(int **q_front, int **q_back){
    if(*q_front != *q_back)
        return *(*q_back-1);
    else
        return -1;
} //큐의 가장 뒤에 있는 정수를 리턴한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 리턴한다.

enum을 활용하여 switch_case구문으로 메뉴를 구성하였다. (3개 이상의 if문은 컴파일러에 따라 비효율적일 수 있다고 한다)

위 코드의 로직대로 공간을 할당하면, 큐의 크기를 push할 때 확인하지 않아도 된다는 장점이 있지만, 명령의 수만큼 공간을 할당하므로 실제 사용하는 양에 비해서 불필요할 정도로 공간을 할당한다. 따라서, 최적화를 위해서는 push를 할 때마다 malloc하는 방식을 생각해 볼 수도 있을 것 같다.