i can do ik!

BOJ 16120 PPAP

문제

bryan은 PPAP를 좋아한다.

bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다.

PPAP 문자열은 문자열 P에서 시작하여, 문자열 내의 P를 PPAP로 바꾸는 과정을 반복하여 만들 수 있는 문자열로 정의된다. 

정확하게는 다음과 같이 정의된다.

P는 PPAP 문자열이다.
PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열이다.

예를 들어 PPAP는 PPAP 문자열이다. 

또한, PPAP의 두 번째 P를 PPAP로 바꾼 PPPAPAP 역시 PPAP 문자열이다.

문자열이 주어졌을 때, 이 문자열이 PPAP 문자열인지 아닌지를 알려주는 프로그램을 작성하여라.

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

입력

첫 번째 줄에 문자열이 주어진다. 

문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.

출력

첫 번째 줄에 주어진 문자열이 PPAP 문자열이면 PPAP를, 아닌 경우 NP를 출력한다.

예제 입력 1

PPPAPAP

예제 출력 1

PPAP

예제 입력 2

PPAPAPP

예제 출력 2

NP

풀이

# boj 16120 PPAP

s = input()
stack = []
ppap = ["P", "P", "A", "P"]

for i in range(len(s)):
    stack.append(s[i])
    if stack[-4:] == ppap:
        for _ in range(4):
            stack.pop()
        stack.append("P")
if stack == ppap or stack == ["P"]:
    print("PPAP")
else:
    print("NP")

BOJ 1662 압축

문제

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다.

K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 

이 Q라는 문자열이 K번 반복된다는 뜻이다.

압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

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

입력

첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다.

문자열은 (, ), 0-9사이의 숫자로만 들어온다.

출력

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 2,147,473,647 보다 작거나 같다.

예제 입력 1

33(562(71(9)))

예제 출력 1

19

예제 입력 2

123

예제 출력 2

3

예제 입력 3

10342(76)

예제 출력 3

8

예제 입력 4

0(0)

예제 출력 4

0

예제 입력 5

1(1(1(1(1(1(1(0(1234567890))))))))

예제 출력 5

0

예제 입력 6

1()66(5)

예제 출력 6

7

풀이

# boj 1662 압축

s = str(input())
tmp = ''
stack = []
l = 0
for i in s :
    if ord(i) >= 48 and ord(i) <= 57: 
        tmp, l = i, l+1
    elif i == '(' : 
        stack.append([tmp, l-1])
        l = 0
    elif i == ')' : 
        n, p = stack.pop() 
        l = int(n)*l+p 
print(l)

BOJ 2841 외계인의 기타 연주

문제

상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 

어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 

이제 이 기타를 치려고 한다.

보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 

프렛의 번호도 1번부터 P번까지 나누어져 있다.

멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 

예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 

만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.

예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 

이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 

여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.

이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 

어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000)

다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 

첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 

입력으로 주어진 음의 순서대로 기타를 연주해야 한다.

출력

첫째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.

예제 입력 1

5 15
2 8
2 10
2 12
2 10
2 5

예제 출력 1

7

예제 입력 2

7 15
1 5
2 3
2 5
2 7
2 4
1 5
1 3

예제 출력 2

9

풀이

import sys

input = sys.stdin.readline
n, m = map(int,input().split())
res = 0
stack = [[] for _ in range(7)]

for _ in range(n):
  flag = True
  a, p = map(int, input().split())
  while stack[a] and stack[a][-1] >= p:
    if stack[a][-1] == p:
      flag = False
      break
    stack[a].pop()
    res += 1
  if flag == False:
    continue
  stack[a].append(p)
  res += 1
  
print(res)

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)