정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
# 입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다.
둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다.
문제에 나와있지 않은 명령이 주어지는 경우는 없다.
# 출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
# 제출한 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st;
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String command = st.nextToken();
if (command.equals("push")) {
queue.offer(Integer.parseInt(st.nextToken()));
} else if (command.equals("pop")) {
if (queue.isEmpty()) System.out.println("-1");
else System.out.println(queue.poll());
} else if (command.equals("size")) {
System.out.println(queue.size());
} else if (command.equals("empty")) {
if (queue.isEmpty()) System.out.println("1");
else System.out.println("0");
} else if (command.equals("front")) {
if (queue.isEmpty()) System.out.println("-1");
else System.out.println(queue.peek());
} else if (command.equals("back")) {
if (queue.isEmpty()) System.out.println("-1");
else System.out.println(queue.getLast());
}
}
}
}
"back" 부분을 해결하기 위해 Deque를 사용해 버렸다. => Deque를 사용하지 않고 "back" 조건을 해결해보기로 했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st;
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String command = st.nextToken();
if (command.equals("push")) {
queue.offer(Integer.parseInt(st.nextToken()));
} else if (command.equals("pop")) {
if (queue.isEmpty()) System.out.println("-1");
else System.out.println(queue.poll());
} else if (command.equals("size")) {
System.out.println(queue.size());
} else if (command.equals("empty")) {
if (queue.isEmpty()) System.out.println("1");
else System.out.println("0");
} else if (command.equals("front")) {
if (queue.isEmpty()) System.out.println("-1");
else System.out.println(queue.peek());
} else if (command.equals("back")) {
System.out.println(queueBack(queue));
}
}
}
private static String queueBack(Queue<Integer> queue) {
if (queue.isEmpty()) { return "-1"; }
int n = queue.size();
for (int i = 1; i <= n - 1; i++) {
queue.add(queue.remove());
}
int result = queue.peek();
queue.add(queue.remove());
return String.valueOf(result);
}
}
함수를 따로 만들어서 문제를 해결했다.
"back" 1. queue.isEmpty()가 true이면 "-1"을 리턴한다. 2. queue의 사이즈의 - 1(n - 1)만큼 반복문을 돌려서 제일 먼저 들어가있는 값들을 다시 넣어준다. 3."back"에 적합한 숫자가 제일 앞에 와있기 때문에 해당 숫자를 peek() 한다. 4. "back"에 조건에 부합한 숫자(맨 뒤에 있던 숫자)를 다시 맨 뒤에 넣어준다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
customQueue<Integer> customQueue = new customQueue<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String command = st.nextToken();
switch (command) {
case "push":
customQueue.push(Integer.parseInt(st.nextToken()));
break;
case "pop":
sb.append(customQueue.pop()).append("\n");
break;
case "size":
sb.append(customQueue.size()).append("\n");
break;
case "empty":
sb.append(customQueue.empty()).append("\n");
break;
case "front":
sb.append(customQueue.front()).append("\n");
break;
case "back":
sb.append(customQueue.back()).append("\n");
break;
}
}
System.out.println(sb);
}
}
class customQueue<T> {
transient Node<T> first;
transient Node<T> last;
int size = 0;
public void push(T e) {
final Node<T> l = last;
final Node<T> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
}
public String pop() {
if (size ==0) return "-1";
final Node<T> f = first;
final T element = f.item;
final Node<T> next = f.next;
f.item = null;
f.next = null;
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
return element.toString();
}
public int size() {
return size;
}
public int empty() {
if (size == 0) return 1;
else return 0;
}
public T front() {
if (first == null) return (T) "-1";
return first.item;
}
public T back() {
if (last == null) return (T) "-1";
return last.item;
}
private class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
LinkedList에 구현되어있는 코드를 참고해서 직접 queue를 구현했습니다. queue와 LinkedList의 구조도 배울 수 있고 상당히 도움이 되는 공부였습니다. => queue, stack 관련해서 직접 구현하고 블로그에 내용 정리하기(블로그글 링크)
# 참고자료
블로그 <성장하는 코더의 스토리> => 링크 => 위 블로그가 각 조건에 대해 설명도 잘 나와있다.
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
push X: 정수 X를 스택에 넣는 연산이다.
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 스택에 들어있는 정수의 개수를 출력한다.
empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
# 입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다.
둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다.
문제에 나와있지 않은 명령이 주어지는 경우는 없다.
# 출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
# 제출한 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Stack<Integer> stack = new Stack();
for (int i = 0; i < n; i++) {
String[] tempStrArr = br.readLine().split(" ");
String command = tempStrArr[0];
if (command.equals("push")) {
int tempNum = Integer.parseInt(tempStrArr[1]);
stack.push(tempNum);
} else if(command.equals("top")) {
if (!stack.empty()) System.out.println(stack.peek());
else System.out.println("-1");
} else if (command.equals("size")) {
System.out.println(stack.size());
} else if (command.equals("empty")) {
if (stack.empty()) System.out.println("1");
else System.out.println("0");
} else if (command.equals("pop")) {
if (stack.empty()) System.out.println("-1");
else System.out.println(stack.pop());
}
}
}
}
스택과 조건문을 사용해서 쉽게 푼 방법 => 스택에 있는 메서드들을 직접 구현해서 풀어보자
Stack 클래스 직접 구현해서 푼 것
import java.io.IOException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
customStack customStack = new customStack(n);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
String command = sc.next();
switch (command) {
case "push":
customStack.push(sc.nextInt());
break;
case "top":
sb.append(customStack.peek()).append("\n");
break;
case "size":
sb.append(customStack.size()).append("\n");
break;
case "empty":
sb.append(customStack.empty()).append("\n");
break;
case "pop":
sb.append(customStack.pop()).append("\n");
break;
}
}
System.out.println(sb);
}
}
class customStack {
int[] stack;
int size = 0;
public customStack(int n) {
stack = new int[n];
}
public void push(int num) {
stack[size] = num;
size++;
}
public int pop() {
if (size == 0) {
return -1;
}
int num = stack[size - 1];
stack[size - 1] = 0;
size--;
return num;
}
public int size() {
return size;
}
public int empty() {
if (size == 0) return 1;
else return 0;
}
public int peek() {
if (size == 0) return - 1;
return stack[size - 1];
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int result = 0;
for (int i = 0; i < n; i++) {
String tempStr = br.readLine();
Stack<Character> stack = new Stack<>();
int tempNum = 0;
for (int j = 0; j < tempStr.length(); j++) {
char tempChar = tempStr.charAt(j);
char top = ' ';
if (!stack.empty()) {
top = stack.peek();
}
if (top == tempChar) {
if (j < tempStr.length() - 1 && tempStr.charAt(j + 1) == tempChar) {
break;
}
result++;
break;
}
stack.push(tempChar);
}
}
System.out.println(result);
}
}
예시에 나오는것만 맞출려고 하다보니 코드를 이렇게 작성했다.
문장 내에 인접한 글자가 한 쌍이라도 같은 문자이면 좋은 문자인줄 알았다.
입력 값으로 AAAA 들어온다고 하면 좋은 단어의 수에 +1 를 못하고 끝나는 로직이라 틀린 답이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int result = 0;
for (int i = 0; i < n; i++) {
String tempStr = br.readLine();
Stack<Character> stack = new Stack<>();
for (int j = 0; j < tempStr.length(); j++) {
char tempChar = tempStr.charAt(j);
char top = ' ';
if (!stack.empty()) {
top = stack.peek();
}
if (top == tempChar) {
stack.pop();
} else {
stack.push(tempChar);
}
}
if (stack.empty()) result++;
}
System.out.println(result);
}
}
j번째 있는 글자와 stack에 top에 있는 글자가 같으면 pop을 해준다.
여기서 고려해야 할 건 입력된 문장을 아치형 곡선 형태로 만들어 좌 우 같은 패턴을 이루면 좋은 단어라는 것이다.
입력된 문장의 문자만큼 for문을 돌리는 부분이 핵심 로직이다. 1. j번째 문자를 char자료형 tempChar 변수에 할당한다. 2. stack이 비어있지 않다면 맨 위에 있는 값(top)을 char자료형인 top에 할당한다. 3. j번째 문자를 stack에 push 하기 전에 top에 있는 문자와 같은지 확인한다. => j번째 문자와 stack의 top의 문자가 같으면 pop을 한다. => 같지 않으면 j번째 문자를 stack에 push한다. 4. 반복문이 종료되고 stack이 비어있다면 result 값에 1을 더한다(좋은 단어의 수 + 1).
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.
쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.
아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.
이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.
레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.
위 예의 괄호 표현은 그림 위에 주어져 있다.
쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.
# 입력
한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다.
괄호 문자의 개수는 최대 100,000이다.
# 출력
잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.
# 제출한 소스코드
import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
String inputStr = sc.nextLine();
// 잘라진 막대기의 총 수를 저장하는 int형 변수
int result = 0;
// stack<Character>를 사용한다.
Stack<Character> stack = new Stack<>();
// 입력된 문자열의 길이만큼 반복문 실행
for (int i = 0; i < inputStr.length(); i++) {
// i번째 문자를 tempchar에 할당한다.
char tempChar = inputStr.charAt(i);
// i번째 문자가 ')'이면 조건문 실행
if (tempChar == ')') {
// stack에 저장된 '('를 pop한다.
// 먼저 pop을 해주기 때문에 레이저의 괄호는 계산식에서 제외된다.
stack.pop();
// i - 1번째 문자가 ')'이면 조건문 실행
if (inputStr.charAt(i - 1) == ')') {
// 맨 위에 있는 막대기의 마지막 부분이기 때문에 마지막 조각을 + 1 한다.
result++;
} else {
// 맨 위에 있는 막대기의 마지막 부분이 아니라면 잘린 막대기 조각만큼 더한다.
result += stack.size();
}
} else {
// stack에 있는 '(' 수 만큼 막대기가 깔려있는 것이다.
stack.push(tempChar);
}
}
System.out.println(result);
}
}
재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.
재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!
# 입력
첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)
이후 K개의 줄에 정수가 1개씩 주어진다.
정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고,
아닐 경우 해당 수를 쓴다.
정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.
# 출력
재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.
# 제출한 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int k = Integer.parseInt(br.readLine());
Stack<Integer> stack = new Stack();
for (int i = 0; i < k; i++) {
int tempNum = Integer.parseInt(br.readLine());
if (tempNum == 0) stack.pop();
else stack.push(tempNum);
}
int result = 0;
for (int tempNum : stack) {
result += tempNum;
}
System.out.println(result);
}
}
Stack을 사용했다.
k개의 정수만큼 반복문을 실행시킨다.
i 번째 입력된 값이 0 이면 stack에서 pop을 한다. => i 번째 입력된 값이 0 이 아니면 stack에 i 번째 값을 push 한다.
4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.
한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
만일X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
X와Y모두 올바른 괄호열이라면 이들을 결합한XY도 올바른 괄호열이 된다.
예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.
‘()’ 인 괄호열의 값은 2이다.
‘[]’ 인 괄호열의 값은 3이다.
‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
올바른 괄호열X와Y가 결합된XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.
예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.
여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.
# 입력
첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.
# 출력
첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.
# 제출한 소스코드
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 첫째 줄에 주어지는 문자열을 변수에 할당한다.
String inputStr = sc.nextLine();
// Stack을 사용하기 위해 객체를 생성한다.
Stack<Character> stack = new Stack();
// 결과를 출력하기 위한 int 변수
int result = 0;
// result에 계산값을 저장하기 전에 중간 처리를 진행할 정수형 변수
int tempNum = 1;
// 첫째 줄에 주어진 문자열의 문자수 만큼 실행되는 반복문
for (int i = 0; i < inputStr.length(); i++) {
// i번째 문자를 char 자료형 변수에 할당한다.
char tempChar = inputStr.charAt(i);
// stack이 비어있지 않으면 stack의 top에 있는 char 값을 top 변수에 할당
Character top = null;
if (!stack.empty()) {
top = stack.peek();
}
// i 번째 문자가 '(', '[', ')', ']' 이면 각 조건절 내부 로직을 실행
if (tempChar == '(') {
// tempNum의 값에 곱하기 2
tempNum *= 2;
// '(' 문자를 stack에 push
stack.push(tempChar);
} else if (tempChar == '[') {
// tempNum의 값에 곱하기 3
tempNum *= 3;
// '['의 문자 stack에 push
stack.push(tempChar);
} else if (tempChar == ')') {
// stack이 비어있거나 stack에 top의 값이 '['이면 result에 0을 할당하고 반복문 종료
if (stack.isEmpty() || top == '[') {
result = 0;
break;
}
// i - 1 번째 문자가 '('여서 한쌍의 괄호가 이뤄질 경우에만 값 저장
if (inputStr.charAt(i - 1 ) == '(') {
result += tempNum;
}
// '('에서 곱했던 값을 나누기 2를 해서 다시 되돌린다.
// 이 부분이 가장 중요한데 한 쌍이 안이뤄져도 i번째 문자가 ')'이면 나누기를 한다.
tempNum /= 2;
// stack의 top에 '('가 있는 상황이기 때문에 pop을 한다.
stack.pop();
} else if (tempChar == ']') {
// ')'와 동일한 구조
if (stack.isEmpty() || top == '(') {
result = 0;
break;
}
if (inputStr.charAt(i - 1 ) == '[') {
result += tempNum;
}
tempNum /= 3;
stack.pop();
}
}
// stack이 비어있지 않으면 result에 0의 값 할당
if(!stack.empty()) {
result = 0;
}
System.out.println(result);
}
}
Scanner를 사용해서 첫째 줄 문자열을 inputStr 변수에 할당한다.
Stack<Character> 객체를 한개 생성한다.
결과를 받을 정수형 변수 result를 초기화한다.
result 변수에 결과를 저장하기 전에 중간 연산을 진행할 tempNum 정수형 변수 할당. => 곱하기를 할 것이라서 1로 값을 할당해놨다.
문자의 개수만큼 반복문을 실행한다.
문자열의 i 번째 문자를 char 자료형인 tempChar 변수에 할당
stack이 비어있지 않다면 stack의 top에 있는 값을 peek해서 Character 자료형의 top 변수에 할당 => i번째 문자가 ')' 이거나 ']' 이면 top에 있는 문자와 한쌍을 이루는지 확인하기 위해 할당
tempChar == ')' - stack이 비어있거나 top의 문자가 '[' 이면 result에 0을 할당하고 반복문 종료 - 문자열의 i - 1 번째 문자가 '(' 이면 한쌍을 이루기 때문에 result에 tempNum을 값을 더한다. - i 번째 문자가 '(' 이면 값을 2로 계속 곱했기 때문에 다시 되돌리기 위해 나누기 2를 한다. - top의 값이 '(' 이기 때문에 stack에서 pop을 한다.
괄호 문자열(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 이하이다.
# 출력
출력은 표준 출력을 사용한다.
만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.
# 제출한 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 테스트 케이스 갯수가 적혀있는 라인을 읽고 int형으로 변환 및 변수에 할당한다.
int t = Integer.parseInt(br.readLine());
// 테스트 케이스 갯수 만큼 반복문을 돌리고 각 라인을 읽습니다.
for (int i = 0; i < t; i++) {
String tempStr = br.readLine();
// Stack<Character> 자료형 객체를 생성한다.
Stack<Character> stack = new Stack<>();
// 반복문이 끝났는지 확인하기 위해 사용하는 bool 자료형
boolean isFinish = false;
for (int j = 0; j < tempStr.length(); j++) {
// tempStr에 charAt(인덱스 넘버)를 사용해 글자를 가져왔습니다.
Character tempChar = tempStr.charAt(j);
// tempStr의 j번째 글자가 '(' 이면 push
if (tempChar.equals('(')) {
stack.push(tempChar);
// tempStr의 j번째 글자가 ')' 이면 pop
// pop 하기전에 stack이 비어있으면 "NO" 출력
// "NO" 출력 후 반복문 종료
} else if (tempChar.equals(')')) {
if (stack.empty()) {
System.out.println("NO");
break;
} else {
// stack이 비어있지 않으면 pop()
stack.pop();
}
}
// 반복문이 종료되었는지 확인하기 위한 로직
// (tempStr의 길이 - 1)와 반복문 횟수가 같으면 반복문이 종료된걸로 판단
// isFinish가 true라고 할당
if ((tempStr.length() - 1) == j) {
isFinish = true;
}
}
// stack이 비어있고 각 글자를 바탕으로 push & pop 하는 반복문이 끝나면 "YES" 출력
if (stack.empty() && isFinish) {
System.out.println("YES");
// stack이 비어있지 않은 경우 "NO"
} else if (isFinish) {
System.out.println("NO");
}
}
}
}
제출한 코드 1차 리팩터링
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
String tempStr = br.readLine();
System.out.println(stackMethod(tempStr));
}
}
private static String stackMethod(String tempStr) {
Stack<Character> stack = new Stack<>();
for (int j = 0; j < tempStr.length(); j++) {
Character tempChar = tempStr.charAt(j);
if (tempChar.equals('(')) {
stack.push(tempChar);
} else if (stack.empty()) {
return "NO";
} else {
stack.pop();
}
}
if (stack.empty()) {
return "YES";
} else {
return "NO";
}
}
}
블로그 Stranger's LAB에 있는 코드를 참고해서 위와 같이 코드를 작성했습니다.
제출한 코드 2차 리팩터링
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
String tempStr = br.readLine();
System.out.println(stackMethod(tempStr));
}
}
private static String stackMethod(String tempStr) {
Stack<Character> stack = new Stack<>();
for (int j = 0; j < tempStr.length(); j++) {
Character tempChar = tempStr.charAt(j);
if (tempChar.equals('(')) {
stack.push(tempChar);
} else if (stack.empty()) {
return "NO";
} else {
stack.pop();
}
}
return stack.empty() ? "YES" : "NO";
}
}
지민이는 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보다 작거나 같은 자연수이다.
# 출력
첫째 줄에 문제의 정답을 출력한다.
# 제출한 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.stream.Stream;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 큐의 크기를 n에 담는다.
int n = Integer.parseInt(st.nextToken());
// 뽑아내려는 수의 개수를 m에 담는다.
int m = Integer.parseInt(st.nextToken());
// stream을 사용해서 뽑아내려는 수의 위치가 담긴 것을 int 배열에 담습니다.
int[] numArr = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// deque 구현체로 LinkedList를 사용합니다.
LinkedList<Integer> deque = new LinkedList<>();
// deque에 1 ~ n까지의 값을 집어넣습니다.
for (int i = 1 ; i < n + 1; i++) {
deque.add(i);
}
// 연산의 최솟값을 저장하는 count 변수 초기화
int count = 0;
// numArr 배열에 있는 숫자들을 각각 deque에서 찾기위해 반복문 실행
for (int num : numArr) {
// num을 찾을때까지 while 반복문을 돌립니다.
while (true) {
// deque에 첫번째 값을 firstNum 변수에 저장합니다.
int firstNum = deque.getFirst();
// firstNum과 num의 값이 같으면 첫번째 값을 deque에서 빼내고 while문을 종료합니다.
if (firstNum == num) {
deque.removeFirst();
break;
}
// 찾을려는 num이 deque의 몇번째 인덱스에 있는 찾습니다.
int numIndex = deque.indexOf(num);
// deque안의 숫자들의 수에 나누기 2를 해서 deque의 절반 길이를 저장합니다.
int dequeHalfSize = deque.size() / 2;
// deque의 절반 길이를 사용해서 deque의 첫번째부터 num 값을 찾을지,
// 아니면 마지막부터 값을 찾을지 확인합니다.
// - deque의 중간 길이보다 numIndex가 작으면 앞에서 부터 num 값을 찾기
// - deque의 중간 길이보다 numIndedex가 크면 뒤에서부터 num 값을 찾기
if (numIndex <= dequeHalfSize) {
deque.addLast(deque.removeFirst());
count++;
} else {
deque.addFirst(deque.removeLast());
count++;
}
}
}
System.out.println(count);
}
}
풀면서 느낀점
문제 자체를 이해하는데 시간이 꽤 걸렸습니다.
블로그에 정리되어있는 내용을 보고서야 이해를 하고 문제를 풀었습니다.
다행이 다른사람이 구현한 코드를 전부 다 보고서 풀지는 않았습니다. => while문 안에 있는 세부 구현 부분은 안보고 풀었습니다.
