N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
출력
첫째 줄에 남게 되는 카드의 번호를 출력한다.
예제 입력 1
6
예제 출력 1
4
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
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());
Queue<Integer> que = new ArrayDeque<>();
for(int i = 1; i <= n; i++) {
que.add(i);
}
while(que.size() != 1) {
que.poll();
que.add(que.poll());
}
System.out.println(que.poll());
}
}
수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.
이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.
중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.
예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.
다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.
이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오
입력
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.
출력
첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오
예제 입력 1
A*(B+C)
예제 출력 1
ABC+*
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static int getPriority(char ch) {
switch(ch) {
case '*' :
case '/' :
return 2;
case '+' :
case '-' :
return 1;
default :
return 0;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String str = br.readLine();
Stack<Character> stk = new Stack<>();
int len = str.length();
for(int i = 0; i < len; i++) { // 괄호를 먼저 없앤다
char ch = str.charAt(i);
int priority = getPriority(ch);
switch(ch) {
case '+' :
case '-' :
case '*' :
case '/' :
while(!stk.isEmpty() && getPriority(stk.peek()) >= priority) {
sb.append(stk.pop());
}
stk.push(ch);
break;
case '(' :
stk.push(ch);
break;
case ')' :
while(!stk.isEmpty() && stk.peek() != '(') {
sb.append(stk.pop());
}
stk.pop(); // '(' 제거
break;
default : // operand
sb.append(ch);
}
}
while(!stk.isEmpty()) {
sb.append(stk.pop());
}
System.out.println(sb.toString());
}
}
예제 입력에만 맞춰서 코드를 짰다가 21% 틀렸습니다를 맞았다.
괄호가 없이도 연산자 우선순위를 고려하여 후위표기식을 만들어낼 수 있어야 했는데 도저히 혼자서 떠올릴 수 없었고 아래 블로그를 참고했다.
즉, 여러 개의 연산자가 연속적으로 쓰일 때는 항상 +, - 보다 *, / 가 먼저 나와야 한다.
여기에서 착안점을 얻어야 했다.
getPriority()를 사용해 연산자별로 우선순위를 정해준다.
연산자들을 스택에 저장하되, peek보다 낮은 연산자는 스택에 들어올 수 없다.
나중에 스택에서 하나씩 빼면서 연산자를 이어붙여야 하는데 *, / 위에 +, - 가 들어오면 우선순위를 위배한 조합이 되기 때문.
즉, +, - 가 들어올 때는 스택에 저장하기 전에 *, / 을 모두 빼서 결과에 붙여줘야 한다.
이때 *, / 외에도 나보다 먼저 들어와있던 +, - 도 모두 빼줘야 하는데, 같은 우선순위 내에서는 먼저 들어온 연산자가 우선시 때문이다.
같은 논리로 *, / 가 들어왔을때도 스택에 먼저 들어온 *, / 를 먼저 빼주고 나를 스택에 넣어야 한다.
괄호 내부의 연산들은 먼저 처리해줘야 하므로 괄호가 닫히는 순간 스택에 저장한 모든 연산자를 빼서 붙여준다. 괄호 밖의 *, / 보다도 괄호 안의 +, - 가 우선권을 가져야 하는데, 스택 안에서 '('가 0의 priority를 가지고 괄호가 열리기 전에 먼저 들어온 *, / 를 막아주기 때문에 정상적으로 출력된다.
KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.
탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.
입력
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.
출력
첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.
예제 입력 1
5 69574
예제 출력 1
00224
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
class Pair {
int num, height;
Pair(int num, int height) {
this.num = num;
this.height = height;
}
}
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());
StringBuilder sb = new StringBuilder();
Stack<Pair> stk = new Stack<>();
int n = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for(int i = 1; i <= n; i++) {
int height = Integer.parseInt(st.nextToken());
while(!stk.isEmpty()) {
if(stk.peek().height > height) {
sb.append(stk.peek().num + " ");
break;
}
stk.pop();
}
if(stk.isEmpty()) {
sb.append("0 ");
}
stk.push(new Pair(i, height));
}
System.out.println(sb.toString());
}
}
어떤 탑의 왼쪽에 있는 탑들은 해당 탑보다 높이가 낮다면 전부 버려도 무방하다.
(어차피 레이저는 오른쪽에서 오고 해당 탑에서 막히거나 쭉 지나가거나 둘 중 하나일 테니까)
후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.
입력
첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. (3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 정수이다)
출력
계산 결과를 소숫점 둘째 자리까지 출력한다.
예제 입력 1
5
ABC*+DE/-
1 2 3 4 5
예제 출력 1
6.20
예제 입력 2
1
AA+A+
1
예제 출력 2
3.00
풀이 .
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());
String prefix = br.readLine();
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Stack<Double> operand = new Stack<>();
int len = prefix.length();
for(int i = 0; i < len; i++) {
char ch = prefix.charAt(i);
if('A' <= ch && ch <= 'Z') { // operand
double d = arr[ch - 'A'];
operand.push(d);
}else { // operator
double d1 = operand.pop();
double d2 = operand.pop();
double d3 = 0.0;
switch(ch) {
case '+' :
d3 = d2 + d1;
break;
case '-' :
d3 = d2 - d1;
break;
case '*' :
d3 = d2 * d1;
break;
case '/' :
d3 = d2 / d1;
break;
}
operand.push(d3);
}
}
System.out.printf("%.2f", operand.pop());
}
}
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231보다 크거나 같고 231보다 작다.
출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
예제 입력 1
5
41523
5
13795
예제 출력 1
1
1
0
0
1
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static boolean bSearch(int[] arr, int target) {
int min = 0;
int max = arr.length - 1;
while(min <= max) {
int mid = (min + max) / 2;
if(arr[mid] == target) {
return true;
}else if(arr[mid] > target) {
max = mid - 1;
}else if(arr[mid] < target) {
min = mid + 1;
}
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int m = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < m; i++) {
int target = Integer.parseInt(st.nextToken());
if(bSearch(arr, target)) {
sb.append("1\n");
}else {
sb.append("0\n");
}
}
System.out.println(sb.toString());
}
}
