1874번: 스택 수열
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
www.acmicpc.net
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.
package fourthday;
import java.io.*;
import java.util.Stack;
public class P1874 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Integer> stack = new Stack<>();
int N = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder(); // 출력할 결과물 저장
int start = 0;
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); //할당된 버퍼에 값 넣어주기
stack.push(0);
StringBuilder S = new StringBuilder();
boolean NO = true;
for(int i=0;i<N;i++){
int put = Integer.parseInt(br.readLine());
while(stack.peek() < put){
start++;
stack.push(start);
// sb.append('+').append('\n');
//bw.write("+\n");
bw.write("+");
bw.newLine();
}
if(stack.peek() == put) {
stack.pop();
// sb.append('-').append('\n');
bw.write("-");
bw.newLine();
//bw.write("-\n");
}else{
NO = false;
}
}
if(NO == false){
BufferedWriter bw2 = new BufferedWriter(new OutputStreamWriter(System.out)); //할당된 버퍼에 값 넣어주기
bw2.write("NO");
bw2.flush();
//System.out.println("NO");
}else{
// System.out.println(sb);
// bw.newLine();
bw.flush();
}
}
}알고리즘 자체는 별 문제없이 잘 구현해냈다.
그러나 출력하는 부분에 있어서 문제를 좀 겪었는데 인텔리제이상으론 문제가 전혀 없었으나 백준으로 옮기면 문제가 발생했다.
BufferWriter를 사용할 때 그 문제가 발생했는데 매니저님과 얘기를 나눌 때 반복문 안에서 계속 버퍼를 사용하게 되면 문제가 생기는 경우가 있다고 조언을 들었다.
1021번: 회전하는 큐
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가
www.acmicpc.net
지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
- 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
- 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
- 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.
package fourthday;
import java.io.*;
import java.util.StringTokenizer;
// 회전하는 큐 1021
public class P1021 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String S = bf.readLine();
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); //할당된 버퍼에 값 넣어주기
StringTokenizer st = new StringTokenizer(S);
int N = Integer.parseInt(st.nextToken()); // 큐의 크기
int M = Integer.parseInt(st.nextToken()); // 뽑아 내려고 하는 수의 개수
Que A = new Que(N);
String S2 = bf.readLine(); // 둘째 줄 입력
st = new StringTokenizer(S2);
int[] answer = new int[M];
for (int i = 0; i < M; i++) {
answer[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < M; i++) {
A.findnum(answer[i]);
}
System.out.println(A.answer());
// bw.write(A.answer());
// bw.flush();
// bw.close();
}
public static class Que {
int[] X;
int num=0;
int count = 0;
public Que(int num) {
X = new int[num];
this.num = num;
for (int i = 0; i < num; i++) {
X[i] = i + 1;
}
}
public int pop() { // 출력
int result = X[0];
int a1 = X[0];
for (int i = 0; i < num-1; i++) {
X[i] = X[i + 1];
}
X[num-1] = a1;
num--; // 스택의 최대 크기 감소
return result;
}
public void moveLeft() { // 왼쪽으로 이동
count++;
int a1 = X[0]; //제일 왼쪽에 있는 수를 저장
for (int i = 0; i < num-1; i++) {
X[i] = X[i + 1]; // 오른쪽에 있는 수를 왼쪽에 삽입
}
X[num-1] = a1; // 제일 왼쪽에 있던 수를 제일 오른쪽에 있는 위치에 삽입
}
public void moveRight() { // 오른쪽으로 이동
count++;
int a1 = X[num-1]; // 제일 오른쪽에 있는 수를 저장
for (int i = 0; i < num-1; i++) {
X[num - i - 1 ] = X[num - i - 2]; // 왼쪽에 있는 수를 오른쪽에 삽입
}
X[0] = a1; // 제일 왼쪽에 제일 오른쪽에 있던 수를 삽입
}
public void findnum(int num) { // 해당하는 숫자가 현재 배열에 왼쪽에 가까운지 오른쪽에 가까운지 출력
int location = 0; // 왼쪽에 가까우면 left, 오른쪽에 가까우면 right를 return한다.
for (int i = 0; i < this.num; i++) {
if (X[i] == num) {
location = i;
break;
}
}
if(location == 0){
pop();
} else if (location <= ( this.num / 2) && location > 0) {
while (X[0] != num) {
moveLeft();
}
pop();
} else {
while (X[0] != num) {
moveRight();
}
pop();
}
}
public int answer(){
return this.count;
}
public void write(){
System.out.println(X[0]);
for (int i =0;i<num;i++){
System.out.print(X[i]+" ");
}
System.out.println("");
}
}
}이 문제에 경우에 처음에 문제를 많이 겪었다. Java 에서 지원하는 Queue를 사용하지 않고 문제를 해결하고 싶었는데 그러다 보니 ArrayList를 사용해서 구현했었는데 그로 인해서인지 메모리 문제가 많이 발생했고, 그 이후에도 Scanner 나 여러 메모리 문제가 발생해서 해결하기 위해서 노력을 했었다.
9012번: 괄호
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고
www.acmicpc.net
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
package fourthday;
import java.io.*;
public class P9012 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
// String S = bf.readLine();
// BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); //할당된 버퍼에 값 넣어주기
int N = Integer.parseInt(bf.readLine());
for(int i = 0;i<N;i++){
int count1 = 0; // (의 갯수 count
int count2 = 0; // )의 갯수 count
String VPS = bf.readLine();
char[] arr = VPS.toCharArray();
String answer = "YES";
for(int j = 0;j < arr.length;j++){
if(arr[j] == '('){
count1++;
}else if(arr[j]== ')'){
count2++;
}else{
System.out.println("잘못된 값 탐지");
}
if(count1< count2){
count1 += 500; //boolean을 이용하면 더 깔끔하게 사용 가능함
}
}
if(count1 == count2){
answer = "YES";
}else{
answer = "NO";
}
if(arr[0] == ')' || arr[arr.length-1] == '('){
answer = "NO";
}
System.out.println(answer);
}
}
}
해당 문제는 어려움 없이 잘 해결했다.
