i can do ik!

BOJ 5397 키로거

문제

창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 

며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다.

키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 

따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 

강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오.

강산이는 키보드로 입력한 키는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표이다.

시간 제한 : 1 초
메모리 제한 : 256 MB

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 

각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. 

(1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입력했다면, '-'가 주어진다. 

이때 커서의 바로 앞에 글자가 존재한다면, 그 글자를 지운다. 

화살표의 입력은 '<'와 '>'로 주어진다. 

이때는 커서의 위치를 움직일 수 있다면, 왼쪽 또는 오른쪽으로 1만큼 움직인다. 

나머지 문자는 비밀번호의 일부이다. 

물론, 나중에 백스페이스를 통해서 지울 수는 있다. 

만약 커서의 위치가 줄의 마지막이 아니라면, 커서 및 커서 오른쪽에 있는 모든 문자는 오른쪽으로 한 칸 이동한다.

출력

각 테스트 케이스에 대해서, 강산이의 비밀번호를 출력한다. 

비밀번호의 길이는 항상 0보다 크다.

예제 입력 1

2
<<BP<A>>Cd-
ThIsIsS3Cr3t

예제 출력 1

BAPC
ThIsIsS3Cr3t

풀이

import sys

input = sys.stdin.readline
n = int(input())

for i in range(n):
    password = list(input().strip())
    l_stack = []
    r_stack = []

    for j in password:
        if j == '<':
            if l_stack:  
                r_stack.append(l_stack.pop())
        elif j == '>':
            if r_stack:  
                l_stack.append(r_stack.pop())
        elif j == '-':
            if l_stack:  
                l_stack.pop()
        else:
            l_stack.append(j)

    l_stack.extend(reversed(r_stack))

    print(''.join(l_stack))

BOJ 2504 괄호의 값

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다.

우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.

올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. 

‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 

그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

시간 제한 : 1 초
메모리 제한 : 128 MB

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 

만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

예제 입력 1

(()[[]])([])

예제 출력 1

28

예제 입력 2

[][]((])

예제 출력 2

0

풀이

arr = list(input())
stack = []
tmp = 1
res = 0

for i in range(len(arr)) : 
  if arr[i] == '(' :
    tmp *= 2
    stack.append(arr[i])
  if arr[i] == '[' :
    tmp *= 3
    stack.append(arr[i])
  
  if arr[i] == ')' :
    if not stack or stack[-1] == '[' :
      res = 0
      break
    elif arr[i-1] == '(' :
      res += tmp
    tmp //= 2
    stack.pop()

  if arr[i] == ']' :
    if not stack or stack[-1] == '(' :
      res = 0
      break
    elif arr[i-1] == '[' :
      res += tmp
    tmp //= 3
    stack.pop()
    
if stack : 
  res = 0
  
print(res)

BOJ 4889 안정적인 문자열

문제

여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 

여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 

안정적인 문자열의 정의란 다음과 같다.

1. 빈 문자열은 안정적이다.
2. S가 안정적이라면, {S}도 안정적인 문자열이다.
3. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.

{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.

문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.

시간 제한 : 1 초
메모리 제한 : 128 MB

입력

입력은 여러 개의 데이터 세트로 이루어져 있다. 

각 데이터 세트는 한 줄로 이루어져 있다.

줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 

문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.

입력의 마지막 줄은 '-'가 한 개 이상 주어진다.

출력

각 테스트 케이스에 대해서, 

테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.

예제 입력 1

}{
{}{}{}
{{{}
---

예제 출력 1

1. 2
2. 0
3. 1

풀이

import sys

input = sys.stdin.readline
n = 0
while True:
    stack = []
    k = 0
    n += 1
    s = input()

    if '-' in s:
        break
    for i in s:
        if i == '{':
            stack.append(i)
        elif i == '}' and stack:
            stack.pop()
        elif i == '}' and not stack:
            stack.append('{')
            k += 1
    if len(stack) != 0:
        k += len(stack)//2

    print(f"{n}. {k}")

BOJ 1935 후위 표기식2

문제

후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다.

그리고 둘째 줄에는 후위 표기식이 주어진다. 

(여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 

그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다.

3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 

그리고 피연산자에 대응 하는 값은 100보다 작거나 같은 자연수이다.

후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.

출력

계산 결과를 소숫점 둘째 자리까지 출력한다.

예제 입력 1

5
ABC*+DE/-
1
2
3
4
5

예제 출력 1

6.20

예제 출력 2

1
AA+A+
1

예제 출력 2

3.00

풀이

import sys

input = sys.stdin.readline
n = int(input())
ex = input().rstrip()
stack = []
nums = []

for i in range(n):
    nums.append(input().rstrip())

for s in ex:
    if s not in ['+','-','*','/']:
        stack.append(nums[ord(s)-ord('A')])
    else:
        a2 = stack.pop()
        a1 = stack.pop()
        stack.append(str(eval(a1 + s + a2)))

print('%.2f' %(float(stack[0])))

BOJ 1918 후위 표기식

문제

수식은 일반적으로 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를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에 중위 표기식이 주어진다.

단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 

그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 

표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.

출력

첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

예제 입력 1

A*(B+C)

예제 출력 1

ABC+*

예제 입력 2

A+B

예제 출력 2

AB+

예제 입력 3

A+B*C

예제 출력 3

ABC*+

예제 입력 4

A+B*C-D/E

예제 출력 4

ABC*+DE/-

풀이

import sys

input = sys.stdin.readline
ex = list(input())
stack = []
res = ''

for s in ex:
    if s.isalpha():
        res += s
    else:
        if s == '(':
            stack.append(s)
        elif s == '*' or s == '/':
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                res += stack.pop()
            stack.append(s)
        elif s == '+' or s == '-':
            while stack and (stack[-1] != '('):
                res += stack.pop()
            stack.append(s)
        elif s == ')':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.pop()
while stack:
    res += stack.pop()

print(res)

BOJ 17413 단어 뒤집기 2

문제

문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.

먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.

1. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('<', '>')로만 이루어져 있다.
2. 문자열의 시작과 끝은 공백이 아니다.
3. '<'와 '>'가 문자열에 있는 경우 번갈아가면서 등장하며, '<'이 먼저 등장한다. 또, 두 문자의 개수는 같다.

태그는 '<'로 시작해서 '>'로 끝나는 길이가 3 이상인 부분 문자열이고, '<'와 '>' 사이에는 알파벳 소문자와 공백만 있다. 

단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 

태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.

시간 제한 : 1 초 
메모리 제한 : 512 MB

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100,000 이하이다.

출력

첫째 줄에 문자열 S의 단어를 뒤집어서 출력한다.

예제 입력 1

baekjoon online judge

예제 출력 1

noojkeab enilno egduj

예제 입력 2

<open>tag<close>

예제 출력 2

<open>gat<close>

예제 입력 3

<ab cd>ef gh<ij kl>

예제 출력 3

<ab cd>fe hg<ij kl>

예제 입력 4

one1 two2 three3 4fourr 5five 6six

예제 출력 4

1eno 2owt 3eerht rruof4 evif5 xis6

예제 입력 5

<int><max>2147483647<long long><max>9223372036854775807

예제 출력 5

<int><max>7463847412<long long><max>7085774586302733229

예제 입력 6

<problem>17413<is hardest>problem ever<end>

예제 출력 6

<problem>31471<is hardest>melborp reve<end>

예제 입력 7

<   space   >space space space<    spa   c e>

예제 출력 7

<   space   >ecaps ecaps ecaps<    spa   c e>

풀이

import sys

input = sys.stdin.readline
word = list(input().rstrip())
i = 0
start = 0

while i < len(word):
    if word[i] == "<":
        i += 1
        while word[i] != ">":
            i += 1
        i += 1
    elif word[i].isalnum():
        start = i
        while i < len(word) and word[i].isalnum():
            i+=1
        tmp = word[start:i]
        tmp.reverse()
        word[start:i] = tmp
    else:
        i += 1

print("".join(word))

BOJ 24511 queuestack

문제

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 

그 자료구조의 이름은 queuestack이다.

queuestack의 구조는 다음과 같다. 1번, 2번, ... , N번의 자료구조(queue 혹은 stack)가 나열되어있으며, 

각각의 자료구조에는 한 개의 원소가 들어있다.

queuestack의 작동은 다음과 같다.

도현이는 길이 M의 수열 C를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다.

이전에 삽입한 결과는 남아 있다. (예제 1 참고)

queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해보자.

시간 제한 : 1 초 (추가 시간 없음)
메모리 제한 : 1024 MB (추가 메모리 없음)

입력

출력

수열 C의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.

예제 입력 1

4
0 1 1 0
1 2 3 4
3
2 4 7

각 상태에 대한 큐스택 내부를 표현하면 다음과 같다.

• 초기 상태 : [1, 2, 3, 4]
• 첫 번째 원소 삽입 : [2, 2, 3, 1]
• 두 번째 원소 삽입 : [4, 2, 3, 2]
• 세 번째 원소 삽입 : [7, 2, 3, 4]

예제 출력 1

4 1 2

예제 입력 2

5
1 1 1 1 1
1 2 3 4 5
3
1 3 5

예제 입력 2

1 3 5

풀이

import sys
from collections import deque

input = sys.stdin.readline
queue = deque()
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

for i in range(n):
	if a[i] == 0:
		queue.appendleft(b[i])
m = int(input())
arr = list(map(int, input().split()))

for i in arr:
	queue.append(i)
	print(queue.popleft(), end=" ")

BOJ 12873 기념품

문제

백준이는 BOJ 알고리즘 캠프 참가자 중 한 명에게 기념품을 주려고 한다.

하지만, 많은 참가자 중에서 어떤 사람을 뽑아서 기념품을 줘야하는지 고민이 되기 시작했다.

따라서, 백준이는 게임을 통해서 기념품을 받을 사람을 정하기로 결정했다.

게임이 시작하기 전에 모든 참가자 N명은 원을 이루어서 앉아있다.

다음, 1부터 N까지 번호가 적혀있는 티셔츠를 시계방향으로 입는다.

이 티셔츠는 게임에 사용되지 않으며, 게임을 쉽게 하기 위해서 입는 티셔츠이다.

게임은 단계로 이루어져 있으며, 첫 단계는 1단계이다. 

각 단계가 시작될 때, 백준이는 어떤 참가자의 앞에 서있다. 

그 다음, "하나"를 외친다. 그 다음, 시계 방향으로 다음 사람에게 이동하며 "둘"을 외친다. 

이 과정은 t단계인 경우에 t3을 외칠 때 까지 진행한다. 

예를 들어, 1단계에서는 1까지 외치며, 2단계에서는 8까지, 3단계에서는 27까지 외친다.

각 단계가 끝난 경우에, 백준이가 앞에 서 있는 사람은 게임에서 제외된다.(t단계인 경우에 t3을 외칠 때 앞에 있던 사람)

사람이 제거된 후에는 백준이는 시계 방향으로 다음 사람에게 이동한다.

1단계에서 백준이는 티셔츠 1번을 입고 있는 사람의 앞에 있다.

게임은 원에 한 명이 남을 때 까지 진행되며, 마지막 남은 사람이 기념품을 가져가게 된다.

참가자의 수 N이 주어졌을 때, 어떤 티셔츠를 입고 있는 사람이 기념품을 받는지 구하는 프로그램을 작성하시오.

시간 제한 : 2 초
메모리 제한 : 512 MB

입력

첫째 줄에 BOJ 캠프 참가자의 수 N (1 ≤ N ≤ 5,000)이 주어진다.

출력

첫째 줄에 기념품을 받는 사람이 입고 있는 티셔츠의 번호를 출력한다.

예제 입력 1

3

예제 출력 1

2

예제 입력 2

6

예제 출력 2

6

예제 입력 3

10

예제 출력 3

8

풀이

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
queue = deque([i for i in range(1, n+1) ])
t =1

for i in range(n-1):
    num = (t**3) % len(queue)
    if num == 1:
        queue.popleft()
    else:    
        queue.rotate(-(num-1))            
        queue.popleft()
    t += 1

print(*queue)