4949번: 균형잡힌 세상
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에
www.acmicpc.net
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
- 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
- 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
- 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
- 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
- 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.
package fifthday;
import java.io.*;
import java.util.Stack;
// fifthday.P4949
public class P4949 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String S;
while(true){
S = br.readLine();
String answer = "yes";
char[] arr = S.toCharArray();
Stack<Integer> stack = new Stack<Integer>();
if(arr[0]=='.' && arr.length == 1){
break;
}
for(int i = 0; i<S.length();i++) {
if(answer.equals("no")){
break;
}
switch (arr[i]){
case '(':
stack.push(1);
break;
case ')':
if(stack.empty()){
answer="no";
break;
}else if(stack.peek() !=1){
answer = "no";
break;
}else {
stack.pop();
break;
}
case '[':
stack.push(2); break;
case ']':
if(stack.empty()){
answer="no";
break;
}else if(stack.peek() != 2){
answer = "no";
break;
}else stack.pop(); break;
default: break;
}
}
if(!(stack.empty())){
answer = "no";
}
System.out.println(answer);
}
}
}
해당 문제는 처음에는 어제 했던 문제처럼 count를 활용해서 하려고 했으나 그럴 경우에 잘못된 출력값이 나오는 케이스가 있어서 Stack 데이터 구조를 활용해 구현하였다.
11279번: 최대 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
- 배열에 자연수 x를 넣는다.
- 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.
package fifthday;
import java.io.*;
import java.util.*;
// fifthday.P4949
public class P11279 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
StringBuilder sb = new StringBuilder();
for(int i =0;i<N;i++){
int x = Integer.parseInt(br.readLine());
if(x==0){
sb.append(pq.isEmpty() ? 0 : pq.poll()).append("\n");
}else {
pq.offer(x);
}
}
System.out.println(sb);
}
}11866번: 요세푸스 문제 0
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
www.acmicpc.net
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
package fifthday;
import java.io.*;
import java.util.*;
public class P11866 {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
StringBuilder sb = new StringBuilder();
Queue<Integer> Que = new LinkedList<Integer>();
for(int y=0;y<N;y++){
Que.offer(y+1);
}
sb.append("<");
for(int i=0;i<N-1;i++){
for(int j = 0;j<K-1;j++){
Que.offer(Que.poll());
}
sb.append(Que.poll()).append(", ");
}
sb.append(Que.poll());
sb.append(">");
System.out.println(sb);
}
}
해당 문제는 Queue를 활용하여 원하는 순서의 숫자가 나올 때까지 제일 앞에 있는 숫자를 뽑아내어 제일 뒤에 붙이는 방식으로 구현을 했다.
11050번: 이항 계수 1
첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\))
www.acmicpc.net
package fifthday;
import java.io.*;
import java.util.*;
public class P11050 {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
System.out.println(BC(N,K));
}
static int BC(int N, int K ) {
if(N==K || K==0){
return 1;
}
return BC(N-1, K-1) + BC(N-1, K);
}
}1541번: 잃어버린 괄호
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다
www.acmicpc.net
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
package sixthday;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class P1541 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String S = br.readLine();
String[] mid = S.split("-"); // - 기준으로 split
int retVal = 0;
String[] C = mid[0].split("\\+");
for(int j =0;j<C.length;j++) retVal += Integer.parseInt(C[j]);
int result = retVal;
for(int i=1;i<mid.length;i++){
retVal = 0;
C = mid[i].split("\\+");
for(int j =0;j<C.length;j++) retVal += Integer.parseInt(C[j]);
result -= retVal;
}
System.out.println(result);
}
}
괄호를 잘 사용해서 제일 작은 수를 만들려고 하면 - 뒤에 있는 숫자들끼리 합쳐서 -에 붙는 숫자를 최대한 늘리면 제일 작은 숫자를 얻을 수 있다. 그래서 split을 활용해 - 기준으로 split을 하고 split 된 결과끼리 계산해서 계산을 진행하면 제일 작은 값을 얻을 수 있다.
