i can do ik!

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 1966 프린터 큐

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 

여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 

하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1.현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2.나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 
그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 

예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

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

입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 

몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 

이때 맨 왼쪽은 0번째라고 하자. 

두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 

중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

예제 입력 1

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

예제 출력 1

1
2
5

풀이

from collections import deque
import sys

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

for i in range(t):
    n, m = map(int, input().split())
    queue = deque(list(map(int, input().split())))
    cnt = 0

    while queue:
        best = max(queue)
        front = queue.popleft() 
        m -= 1 

        if best == front: 
            cnt += 1 
            if m < 0: 
                print(cnt)
                break

        else:   
            queue.append(front) 
            if m < 0 : 
                m = len(queue) - 1

BOJ 2805 나무 자르기

문제

상근이는 나무 M미터가 필요하다. 

근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 

정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 

상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 

먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 

높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다.

그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 

따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 

예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 

상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. 

(총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 

이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 

나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다.

높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

예제 입력 1

4 7
20 15 10 17

예제 출력 1

15

예제 입력 2

5 20
4 42 40 26 46

예제 출력 2

36

풀이

import sys

input = sys.stdin.readline
n , m = map(int, input().split())
tree = list(map(int, input().split()))

def cut_tree(arr, start, end):
    res = 0
    while start <= end:
        mid = (start + end) // 2
        total = 0
        
        for x in arr:
            if x > mid:
                total += x - mid
            
        if total < m:
            end = mid - 1
        else:
            res = mid
            start = mid + 1

    return res

print(cut_tree(tree, 0, max(tree)))

BOJ 16212 정열적인 정렬

문제

형준이는 수열을 하나 가지고 있다. 

형준이는 수열을 정열적으로 정렬해보려 한다. 과연, 정렬할 수 있을까?

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

입력

첫째 줄에는 수열의 길이 N (1 ≤ N ≤ 500,000)이 주어진다.

둘째 줄에는 수열의 각 원소 ai가 공백을 사이에 두고 차례대로 주어진다.

ai의 절댓값은 200만 이하이다.

출력

수열 a를 오름차순으로 정렬해서, 공백을 사이에 두고 하나씩 차곡차곡 출력하자.

서브태스크 1 (10점)

정렬하려 하는 배열의 길이 N이 N ≤ 1,000을 만족한다.

서브태스크 2 (15점)

문제에 제시된 조건 이외의 다른 제약은 없다.

예제 입력 1

6
14 5 8 7 1 10

예제 출력 1

1 5 7 8 10 14

힌트

언어별로 정렬 함수를 구글에 검색해보자~~

예를 들면 C++에서는 sort(arr, arr+n);와 같이, Python에서는 arr.sort() 와 같이 배열 arr을 정렬할 수 있다.

풀이

import sys

input = sys.stdin.readline
n = int(input())
a = list(map(int, input().strip().split()))
a.sort()

for i in a:
    print(i, end=' ')

BOJ 11536 줄 세우기

문제

악독한 코치 주혁은 선수들을 이름 순으로 세우는 것을 좋아한다.

더 악독한 것은 어떤 순서로 서야할지도 알려주지 않았다! 

선수들의 이름이 주어질 때 어떤 순서로 이루어져있는지 확인해보자.

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

입력

첫째 줄에 N개의 이름이 주어진다. (2 ≤ N ≤ 20)

다음 N개의 줄에는 각 선수들의 이름이 주어진다.

이름은 2 이상 12 이하의 대문자로만 이루어져있다. 

선수의 이름은 중복되지 않는다.

출력

이름이 증가하는 순으로 나타나면 INCREASING, 감소하는 순이면 DECREASING을 한 줄에 출력한다. 

만약 위의 두 경우가 아니라면 NEITHER를 출력한다.

예제 입력 1

5
JOE
BOB
ANDY
AL
ADAM

예제 출력 1

DECREASING

예제 입력 2

11
HOPE
ALI
BECKY
JULIE
MEGHAN
LAUREN
MORGAN
CARLI
MEGAN
ALEX
TOBIN

예제 출력 2

NEITHER

예제 입력 3

4
GEORGE
JOHN
PAUL
RINGO

예제 출력 3

INCREASING

풀이

n = int(input())
name = []

for i in range(n):
    name.append(str(input()))
    
if name==sorted(name, reverse=True):
    print('DECREASING')
elif name==sorted(name):
    print('INCREASING')
else:
    print('NEITHER')