i can do ik!

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 3015 오아시스 재결합

문제

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 

모든 사람의 키는 231 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

예제 입력 1

7
2
4
1
2
2
5
1

예제 출력 1

10

풀이

import sys

input = sys.stdin.readline
n = int(input())
stack = []
res = 0

for _ in range(n):
    now = int(input())
    cnt = 1

    while stack and stack[-1][0] <= now:
        height, cnt = stack.pop()
        if height == now:
            res += cnt
            cnt += 1
        elif height < now:
            res += cnt
            cnt = 1

    if stack:
        res += 1
    stack.append((now, cnt))

print(res)

BOJ 1725 히스토그램

문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 

위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 

아래 그림의 빗금 친 부분이 그 예이다.

이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

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

입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. 

N은 히스토그램의 가로 칸의 수이다. 

다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 

각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

예제 입력 1

7
2
1
4
5
1
3
3

예제 출력 1

8

풀이

import sys

input=sys.stdin.readline
n = int(input())
graph = []
res = 0
cursor = 0
a = 0

for _ in range(n):
  graph.append(int(input()))

graph.append(0)
stack = [(0, graph[0])]

for i in range(1,n+1):
  cursor = i
  while stack and stack[-1][1] > graph[i]:
      cursor, temp = stack.pop()
      res = max(res, temp*(i-cursor))
  stack.append((cursor, graph[i]))
  
print(res)

BOJ 17299 오등큰수

문제

크기가 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 이다.

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

예제 입력 1

7
1 1 2 3 4 2 1

예제 출력 1

-1 -1 1 2 2 1 -1

풀이

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    arr = list(map(int, input().split()))
    cnt = [0] * 1000001

    for i in arr:
        cnt[i] += 1

    stack = []
    res = [-1] * n
    
    for i in range(n):
        while stack and cnt[arr[stack[-1]]] < cnt[arr[i]]:
            res[stack.pop()] = arr[i]
        stack.append(i)

    print(' '.join(map(str, res)))

main()

BOJ 9935 문자열 폭발

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다.

폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

1.문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 
남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
2.새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
3.폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 

남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

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

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

예제 입력 1

mirkovC4nizCC44
C4

예제 출력 1

mirkovniz

예제 입력 2

12ab112ab2ab
12ab

예제 출력 2

FRULA

풀이

texts = input()
bomb = list(input())
stack = list()

for i in texts:
    stack.append(i)
    if stack[-len(bomb):] == bomb:
        for _ in range(len(bomb)):
            stack.pop()

if not stack:
    print('FRULA')
else:
    print(''.join(stack))

BOJ 2812 크게 만들기

문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

예제 입력 1

4 2
1924

예제 출력 1

94

예제 입력 2

7 3
1231234

예제 출력 2

3234

예제 입력 3

10 4
4177252841

예제 출력 3

775841

풀이

n, k = map(int, input().split())
num = list(input())
cnt = k
stack = []

for i in range(n):
    while cnt and stack:
        if stack[-1] < num[i]:
            stack.pop()
            cnt -= 1
        else:
            break
    stack.append(num[i])

print(''.join(stack[:n-k]))

BOJ 17608 막대기

문제

아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 

각 막대기의 높이는 그림에서 보인 것처럼 순서대로 6, 9, 7, 6, 4, 6 이다. 

일렬로 세워진 막대기를 오른쪽에서 보면 보이는 막대기가 있고 보이지 않는 막대기가 있다. 

즉, 지금 보이는 막대기보다 뒤에 있고 높이가 높은 것이 보이게 된다. 

예를 들어, 그림과 같은 경우엔 3개(6번, 3번, 2번)의 막대기가 보인다.

N개의 막대기에 대한 높이 정보가 주어질 때, 오른쪽에서 보아서 몇 개가 보이는지를 알아내는 프로그램을 작성하려고 한다.

입력

첫 번째 줄에는 막대기의 개수를 나타내는 정수 N (2 ≤ N ≤ 100,000)이 주어지고 

이어지는 N줄 각각에는 막대기의 높이를 나타내는 정수 h(1 ≤ h ≤ 100,000)가 주어진다.

출력

오른쪽에서 N개의 막대기를 보았을 때, 보이는 막대기의 개수를 출력한다.

예제 입력 1

6
6
9
7
6
4
6

예제 출력 1

3

예제 입력 2

5
5
4
3
2
1

예제 출력 2

5

풀이

import sys

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

for _ in range(n):
    stack.append(int(input()))

last = stack[-1]
cnt = 1

for i in reversed(range(n)):
    if stack[i] > last:
        cnt += 1
        last = stack[i]

print(cnt)

BOJ 3986 좋은 단어

문제

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 

보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 

안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 

그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 

만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 

그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

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

입력

첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 

단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

출력

첫째 줄에 좋은 단어의 수를 출력한다.

예제 입력 1

3
ABAB
AABB
ABBA

예제 출력 1

2

예제 입력 2

3
AAA
AA
AB

예제 출력 2

1

예제 입력 3

1
ABBABB

예제 출력 3

1

풀이

import sys

input = sys.stdin.readline
n = int(input())
words = [list(input().rstrip()) for _ in range(n)]
cnt = 0
for i in words:
    stack = []
    while i:
        word = i.pop()
        if not stack:
            stack.append(word)
        else:
            if stack[-1] == word:
                stack.pop()
            else:
                stack.append(word)
                
    if not stack:
        cnt += 1
print(cnt)