백준 5430번: AC

문제

https://www.acmicpc.net/problem/5430

5430번: AC

---

풀이

언어 AC의 두 가지 함수 R(배열에 있는 수의 순서 뒤집기)과 D(맨 앞의 수 버리기)를 이용하여 배열의 초기값에 대한 연산 결과를 구하는 문제입니다.

맨 앞의 수가 R 연산에 의해 바뀔 수 있기 때문에 덱을 사용하여 문제를 해결하였습니다.

---

코드

C언어

수행할 함수 p와 배열의 수의 개수 n를 입력받고 [x1,...,xn]과 같은 형태로 배열에 들어갈 정수를 입력받습니다.

이때 n을 입력받은 후에 개행을 하고 그다음에 '['를 입력해야 하기 때문에 getchar()를 사용해서 개행을 표현하였습니다.

그다음 n이 0이 아니라면 scanf("%c", &c)를 사용하여 '['를 입력받고 그 후에 n만큼 for문을 사용해서 scanf("%d%c", &x, &c)를 사용하여 배열(덱)에 넣을 수 x와 ',' 혹은 ']'를 입력받고 x를 deque의 뒤에 삽입합니다.

n이 0이라면 아무런 입력이 없는 것이 아니라 "[]"를 입력해야 하므로 scanf("%c%c", &c, &c)로 이를 표현합니다.

위의 입력이 끝나면 곧바로 다음 테스트 케이스로 넘어가서 p를 입력받기 전에 개행을 하기 때문에 getchar()를 사용했습니다.

이후 i를 포함한 for문에서 p[i]가 'R'이라면 회전한 것이기 때문에 bool형 정수 swap의 값을 바꿔줍니다. p[i]가 'D'라면 swap의 값에 따라 덱의 맨 앞의 값을 버리거나 맨 뒤의 값을 버립니다. 이때 버릴 수 있는 값이 없다면(덱이 비어있다면) "error"를 출력하고 이를 bool형 정수 error를 1로 바꿔줍니다.
error가 0이라면 에러가 발생하지 않은 것이므로 덱에 남아있는 값 모두를 조건에 맞게 출력합니다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct node {
	int data;
	struct node* prev;
	struct node* next;
} node;
typedef struct {
	node* front;
	node* rear;
	int count;
} Deque;
void initDeque(Deque* deque) {
	deque->front = deque->rear = NULL;
	deque->count = 0;
}
int is_empty(Deque* deque) {
	if (deque->count == 0) return 1;
	else return 0;
}
void add_back(Deque* deque, int data) {
	node* now = (node*)malloc(sizeof(node));
	if (is_empty(deque)) {
		deque->front = now;
		deque->rear = now;
		now->prev = NULL;
	}
	else {
		now->prev = deque->rear;
		deque->rear->next = now;
		deque->rear = now;
	}
	now->next = NULL;
	now->data = data;
	(deque->count)++;
}
int delete_front(Deque* deque) {
	if (is_empty(deque)) return -1;
	else {
		int rdata;
		node* rnode;
		rdata = deque->front->data;
		rnode = deque->front;
		deque->front = deque->front->next;
		if (deque->count == 1) deque->rear = NULL;
		free(rnode);
		(deque->count)--;
		return rdata;
	}
}
int delete_back(Deque* deque) {
	if (is_empty(deque)) return -1;
	else {
		int rdata;
		node* rnode;
		rdata = deque->rear->data;
		rnode = deque->rear;
		deque->rear = deque->rear->prev;
		if (deque->count == 1) deque->rear = NULL;
		free(rnode);
		(deque->count)--;
		return rdata;
	}
}
main() {
	int t, n, x;
	char p[100000], c;
	Deque deque;
	scanf("%d", &t);
	while (t--) {
		initDeque(&deque);
		scanf("%s", p);
		scanf("%d", &n);
		getchar();
		if (n != 0) {
			scanf("%c", &c);
			for (int i = 0; i < n; i++) {
				scanf("%d%c", &x, &c);
				add_back(&deque, x);
			}
		}
		else scanf("%c%c", &c, &c);
		getchar();
		int swap = 0, error = 0;
		for (int i = 0; i < strlen(p); i++) {
			if (p[i] == 'R') {
				swap = !swap;
			}
			else if (p[i] == 'D') {
				if (is_empty(&deque)) {
					printf("error\n");
					error = 1;
					break;
				}
				else if (swap) {
					delete_back(&deque);
				}
				else delete_front(&deque);
			}
		}
		if (!error) {
			printf("[");
			if (!swap) {
				while (!is_empty(&deque)) {
					printf("%d", delete_front(&deque));
					if (!is_empty(&deque)) {
						printf(",");
					}
				}
			}
			else {
				while (!is_empty(&deque)) {
					printf("%d", delete_back(&deque));
					if (!is_empty(&deque)) {
						printf(",");
					}
				}
			}
			printf("]\n");
		}
	}	
}

자바

위의 C언어를 이용한 풀이와 동일한 방법으로 덱을 구현할 때 자바 util 패키지의 LinkedList 클래스를 사용했습니다.

또한 배열에 들어갈 수를 입력할 때 StringTokenizer에서 '['와 ']', 그리고 ','를 기준으로 구분하여 덱의 뒤에 삽입하였기 때문에 위의 코드처럼 입력 부분의 코드를 복잡하게 작성하지 않아도 됐습니다.

모든 입력이 끝난 후에 Stringbuilder를 이용하여 한꺼번에 출력했습니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            LinkedList<Integer> deque = new LinkedList<Integer>();
            String p = br.readLine();
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), "[],");
            for (int i = 0; i < n; i++) {
                deque.addLast(Integer.parseInt(st.nextToken()));
            }
            boolean swap = false, error = false;
            for (int i = 0; i < p.length(); i++) {
                if (p.charAt(i) == 'R') {
                    swap = !swap;
                } else if (p.charAt(i) == 'D') {
                    if (deque.isEmpty()) {
                        sb.append("error\n");
                        error = true;
                        break;
                    } else if (!swap) {
                        deque.pollFirst();
                    } else deque.pollLast();
                }
            }
            if (!error) {
                sb.append("[");
                if (!swap) {
                    while (!deque.isEmpty()) {
                        sb.append(deque.pollFirst());
                        if (!deque.isEmpty()) sb.append(",");
                    }
                } else {
                    while (!deque.isEmpty()) {
                        sb.append(deque.pollLast());
                        if (!deque.isEmpty()) sb.append(",");
                    }
                }
                sb.append("]\n");
            }
        }
        System.out.print(sb);
    }
}

 

---

결론

이 문제에서 입력 부분의 코드를 작성할 때 C언어와 비교했을 때 자바의 장점을 더 명확하게 알 수 있었습니다.

또한 C언어로 is_empty() 함수를 구현할 때 어떠한 이유에서인지 return (deque.count == 0); 로 작성하면 시간 초과가 발생했습니다. if문을 이용하여 return값을 나누는 것과 그렇게 큰 차이가 있는지에 대해서 더 알아보고 싶다는 생각이 들었습니다.