문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.
먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.
알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('<', '>')로만 이루어져 있다.
문자열의 시작과 끝은 공백이 아니다.
'<'와 '>'가 문자열에 있는 경우 번갈아가면서 등장하며, '<'이 먼저 등장한다. 또, 두 문자의 개수는 같다.
태그는 '<'로 시작해서 '>'로 끝나는 길이가 3 이상인 부분 문자열이고, '<'와 '>' 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.
첫째 줄에 문자열 S가 주어진다. S의 길이는 100,000 이하이다.
첫째 줄에 문자열 S의 단어를 뒤집어서 출력한다.
import java.util.Scanner;
import java.util.Stack;
public class B17413 {
static void print(Stack st) {
while (!st.empty()) {
System.out.print(st.peek());
st.pop();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Stack st = new Stack();
String s = sc.nextLine();
boolean check = false;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '<') {
print(st); // <를 만나면 여태껏 저장해둔 문자열 거꾸로 출력
check = true;
System.out.print(s.charAt(i));
} else if (s.charAt(i) == '>') {
check = false;
System.out.print(s.charAt(i));
} else if (check) {
System.out.print(s.charAt(i));
}
else {
if (s.charAt(i) == ' ') {
print(st);
System.out.print(s.charAt(i));
}
else {
st.push(s.charAt(i));
}
}
}
print(st);
}
}
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.
쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.
아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.
이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.
레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.
위 예의 괄호 표현은 그림 위에 주어져 있다.
쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.
한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.
잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.
import java.util.Scanner;
import java.util.Stack;
public class B_10799 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s = sc.nextLine();
Stack<Integer> st = new Stack<>();
int ans=0;
int index=1;
for(int i=0; i<s.length(); i++) {
if(s.charAt(i) == '(') {
st.push(index);
}
else { // ')'
if(index-st.peek()==1) {
st.pop();
ans+=st.size();
}
else {
st.pop();
ans+=1;
}
}
index++;
}
System.out.println(ans);
}
}
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class B17298 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[]num = new int[N];
Stack<Integer>S = new Stack<Integer>();
for(int i = 0;i<N;i++) {
num[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0;i<N;i++) {
while(!S.isEmpty()&&num[S.peek()]<num[i]) {
num[S.pop()] = num[i];
}
S.add(i);
}
while(!S.isEmpty()) {
num[S.pop()] = -1;
}
for(int i = 0;i<N;i++) {
sb.append(num[i]).append(" ");
}
System.out.println(sb);
}
}
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.
Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.
예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class B17299 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
Stack<Integer>S = new Stack<Integer>();
int N = Integer.parseInt(st.nextToken());
int[]num = new int[N];
int[]count = new int[1000001];
int[]ans = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0;i<N;i++) {
num[i] = Integer.parseInt(st.nextToken());
count[num[i]]++;
}
for(int i = 0;i<N;i++) {
while(!S.isEmpty() && count[num[i]] > count[num[S.peek()]]) {
ans[S.pop()] = num[i];
}
S.push(i);
}
while(!S.empty()) {
ans[S.pop()] = -1;
}
StringBuilder sb = new StringBuilder();
for(int i = 0;i<N;i++) {
sb.append(ans[i] + " ");
}
System.out.println(sb);
}
}