🍋 프로그래머스 76502. 괄호 회전하기

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

(), [], {} 는 모두 올바른 괄호 문자열입니다.
만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

s의 길이는 1 이상 1,000 이하입니다.

입출력 예

s result
"{}" 3
"}]()[{" 2
"[)(]" 0
"}}}" 0

입출력 예 설명

입출력 예 #1

다음 표는 "{}" 를 회전시킨 모습을 나타낸 것입니다.
x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?
0 "{}" O
1 "](){}[" X
2 "(){}[]" O
3 "){}[](" X
4 "{}" O
5 "}{" X
올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

입출력 예 #2

다음 표는 "}](){" 를 회전시킨 모습을 나타낸 것입니다.
x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?
0 "}{" X
1 "{}" X
2 "()[{}]" O
3 ")[{}](" X
4 "[{}]()" O
5 "{}[" X
올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.
입출력 예 #4

s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

코드

from collections import deque

def solution(s):
    rotate = len(s) # 문자열 총 길이
    queue = deque(s) # 큐 선언
    answer = 0
    
    for i in range(rotate): # 문자열 탐색
        if i != 0: 
            sym = queue.popleft() # 맨 앞 문자열
            queue.append(sym) # 맨 뒤로 이동
            
        stack = []
        for q in queue:
            if stack: # 괄호의 짝이 맞으면 스택에서 해당 괄호를 제거하고
                if stack[-1] == '[' and q == ']': 
                    stack.pop()
                elif stack[-1] == '{' and q == '}':
                    stack.pop()
                elif stack[-1] == '(' and q == ')':
                    stack.pop()
                else:
                    stack.append(q)
            else: # 짝이 맞지 않으면 스택에 추가한다.
                stack.append(q)

        if len(stack) == 0: # 스택이 다 비워지면 x 카운팅
            answer += 1
            
    return answer

🍋 백준 1900. 레슬러

문제

옛날에 레슬링을 무척 좋아하는 동호라는 국왕이 살았다. 그 당시 레슬링 선수들은 초자연적인 힘을 가졌다. 경기에 이기기 위해서 레슬링 선수는 자신의 힘뿐만 아니라 경기할 때 착용하는 마술 링에도 의존한다. 마술 링은 레슬링 선수로 하여금 상대 선수의 힘에 비례하는 힘을 추가로 얻을 수 있게 해준다.

레슬링 선수의 힘과 마술 링의 힘은 모두 양의 정수이다. 선수 A가 선수 B와 경기할 때, A의 ‘경기력’은 ‘A의 힘’ + ‘B의 힘’ * ‘A가 착용하고 있는 마술 링의 힘’이다. 경기에서는 경기력이 높은 선수가 이긴다.

예를 들어, 선수 A의 힘이 10이고 착용하고 있는 마술 링의 힘은 3이라고 하고, 선수 B의 힘은 18이고 착용하고 있는 마술 링의 힘은 4라고 하자. 이 두 선수가 경기를 가지면, A가 이긴다. 왜냐하면, A의 경기력은 10+318=64이지만 B의 경기력은 18+410=58이기 때문이다. 만약 A가 힘이 15이고 마술의 힘이 5인 링을 착용한 선수 C를 만났다면, C가 이긴다. 이 경기에서 A의 경기력은 10+315=55이고 C의 경기력은 15+510=65이다. 마찬가지로 B와 C의 경기에서는 C가 이긴다.

동호는 매년 레슬링 축제를 연다. 축제 기간에 각 레슬링 선수는 다른 모든 선수들과 한번씩 경기를 가진다. 이 축제의 마지막에 동호는 레슬링 선수를 보두 초대하여 축하하고 금화를 수여한다.

레슬링 선수들이 동호를 만나는 줄(순서)를 정하는 것은 희현이 할 일이다. 이 일은 매우 중요하다. 왜냐하면, 동호가 수여하는 금화의 수는 그가 이긴 경기수와 그가 선수들의 줄 어느 위치에 서 있느냐로 결정한다고 선언하였기 때문이다. 한 선수가 받는 금화의 수는 그가 이긴 경기 수 + 선수들의 줄에서 자기보다 앞에 있는데 자기가 이긴 선수의 수이다.

예를 들어 위의 세 선수 A, B, C에게 A, B, C의 순서로 동호를 만나면, A는 금화 1개, B는 0개, C는 4개를 받게 된다. C는 2 경기를 이겨서 2개에 자기가 이긴 A, B가 자기보다 줄에서 앞에 있으므로 각각 하나씩 2개를 합하여 4개를 받는다. 만약 C, A, B 순서라면 C는 2개, A는 1개, B는 0개를 받게 된다.

희현이는 나라의 재정을 고려하여 수여하는 금화의 수를 최소화하고자 한다. 당신이 할 일은 재무장관을 도와 수여하는 금화의 수를 최소화하도록 동호를 만나는 순서를 결정하는 것이다. 모든 선수들의 힘과 가진 마술 링의 힘이 주어진다. 경기에서 비기는 경우를 발생시키지 않는다고 가정한다.

입력

첫째 줄에 선수들의 수 N이 주어진다. 선수들은 1부터 N까지 번호가 붙어 있다. 다음 N개의 줄에는 한 줄에 한 선수의 힘과 그가 가진 마술 링의 힘이 주어진다. 선수 k의 정보는 k+1번째 줄에 주어진다. N은 10000 이하이고, 선수의 힘과 마술 링의 힘은 모두 1 이상 1000 이하라고 가정하여도 좋다.

출력

동호를 만나는 순서대로 한 줄에 하나씩 선수의 번호를 출력한다.

예제 입력 1

3
10 3
18 4
15 5

예제 출력 1

3
1
2

알고리즘 분류

• 그리디 알고리즘
• 정렬

코드 - python3 시간초과 / pypy 성공

import sys
input = sys.stdin.readline

N = int(input()) # 선수 명 수
player = list() # 힘 / 마술 링
win = dict() # 승리 횟수

for i in range(N):
    player.append(list(map(int, input().split())))
    win[i] = 0 # 각 선수에게 번호 부여

for i in range(N - 1):
    for j in range(i, N): # 경기력 구하기
        a = player[i][0] + player[j][0] * player[i][1]
        b = player[j][0] + player[i][0] * player[j][1]

        if a > b: # 승리횟수 카운팅
            win[i] += 1
        elif a < b:
            win[j] += 1

win = sorted(win.items(), key=(lambda x: x[1]), reverse=True) # 승리횟수에 따라 내림차순 정렬
for i in range(len(win)): # 정렬 순서에 따라 선수 번호 출력
    print(win[i][0] + 1)

🍋 15724. 주지수

문제

네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자료로 쓰고 싶어한다.

진경대왕은 굉장히 근엄한 왕이기 때문에 당신에게 4개의 숫자로 직사각형 범위를 알려줄 것이다.

예를 들어, 위와 같이 사람이 살고 있다고 가정할 때 <그림 1>의 직사각형 범위의 사람 수를 알고 싶다면 진경대왕은 네 개의 정수 1 1 3 2를 부를 것이다. 마찬가지로 <그림 2>는 1 1 1 4, <그림 3>은 1 1 4 4가 될 것이다.

진경대왕을 위하여 이 참고 자료를 만들어내는 프로그램을 작성해보자.

입력

첫째 줄에 영토의 크기 N, M(1 ≤ N, M ≤ 1,024)이 주어진다.

다음 N개의 줄에는 M개의 정수로 단위 구역 내에 살고 있는 사람 수가 주어진다. 각 단위 구역 내에 살고 있는 사람 수는 100명 이하이며, 각 단위 구역 별 최소 1명의 사람은 살고 있다.

그 다음 줄에는 진경대왕이 인구 수를 궁금해하는 직사각형 범위의 개수 K(1 ≤ K ≤ 100,000)가 주어진다.

다음 K개의 줄에는 네 개의 정수로 직사각형 범위 x1, y1, x2, y2가 주어진다(x1 ≤ x2, y1 ≤ y2).

출력

K개의 줄에 순서대로 주어진 직사각형 범위 내에 살고 있는 사람 수의 합을 출력한다.

예제 입력 1

4 4
9 14 29 7
1 31 6 13
21 26 40 16
8 38 11 23
3
1 1 3 2
1 1 1 4
1 1 4 4

예제 출력 1

102
59
293

알고리즘 분류

• 다이나믹 프로그래밍
• 누적 합

코드 - python3 성공

import sys
input = sys.stdin.readline

n,m = map(int,input().split()) # 영토 크기
area = [list(map(int,input().split())) for _ in range(n)] # 구역별 인구수

dp = [[0]*(m+1) for _ in range(n+1)] # 영토 크기만큼 dp 생성
# 일정 좌표까지의 총 인구수 구하기
for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j] = area[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

# 직사각형 범위 인구수 구하기
for _ in range(int(input())):
    x,y,i,j = map(int,input().split())
    print(dp[i][j] - dp[x-1][j] - dp[i][y-1] + dp[x-1][y-1])

🍋 11497. 통나무 건너뛰기

문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

입력

입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.

이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)

출력

각 테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력하시오.

예제 입력 1

3
7
13 10 12 11 10 11 12
5
2 4 5 7 9
8
6 6 6 6 6 6 6 6

예제 출력 1

1
4
0

알고리즘 분류

• 그리디 알고리즘
• 정렬

풀이

• 가장 큰 값을 가운데에 놓고 왼쪽 오른쪽 번갈아 가면서 놓는다.
• 서로 인접한 높이 차이가 정렬했을 때 한 개나 두 개 정도 차이난다.
• 최대 높이 차이는 정렬했을 때의 인덱스 두 개 정도 차이난다.

코드 - python 3 성공

import sys
input = sys.stdin.readline

t = int(input()) # 테스트 케이스

for i in range(t):
    n = int(input()) # 통나무 개수
    a = list(map(int,input().split())) # 통나무 높이
    a.sort() # 정렬
    result = 0

    # 오른쪽 왼쪽 번갈아 놓으면 최대 높이 차이 인덱스 두 개 정도 차이난다.
    for j in range(2,n):
        c = a[j] - a[j - 2]
        result = max(c, result) # 차이의 최댓값
    print(result)

🍋 15922. 아우으 우아으이야!!

문제

아우으 우아으이야!! 으어아아아아아아아ㅏㅏㅏ아아앙ㅇ아아ㅏ
수직선 위에 선분을 여러 개 그릴 거 야아아앙ㅇ아아아ㅏㅏ아아ㅏㅏ!!
선분을 겹치게 그리는 것도 가능하다아어으우어우으아아아아아아아아아이야!!!!1
선분을 모두 그렸을 때, 수직선 위에 그려진 선분 길이의 총합은 얼마아아으으우어으이으야이야!!!!

입력

첫째 줄에 수직선 위에 그릴 선분의 개수 N이 주어진다아우으 우아으이야!!. (1 ≤ N ≤ 100,000)

둘째 줄 부터 N개의 줄에 좌표를 나타내는 정수쌍 (x, y)가 주어진다으어아아아아아아아ㅏㅏㅏ아아앙ㅇ아아.

이는 [x, y] 구간 (x와 y를 포함하는 구간)에 선분을 그린다는 의미이다유아아우응아이양.

좌표는 x가 증가하는 순으로, x가 같다면 y가 증가하는 순으로 주어진다으우오아앙아ㅓㅇ아ㅡㅇ. (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)

출력

N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다아아어으잉에애야우아으아이아야아아아아아아이야!!!

예제 입력 1

5
-5 -2
-3 0
2 5
6 10
8 12

예제 출력 1

14

예제 입력 2

2
-1000000000 1000000000
-1 1

예제 출력 2

2000000000

알고리즘 분류

• 스위핑

코드 - python 3 성공

import sys
input = sys.stdin.readline

n = int(input()) # 선분 갯수
x, y = map(int, input().split()) # 기준 좌표값
result = 0

for _ in range(n - 1):
    temp_x, temp_y = map(int, input().split())

    if x <= temp_y <= y:  # 포함관계
        continue
    elif x <= temp_x <= y and not x <= temp_y <= y:  # y 연장
        y = temp_y
    else:  # 새로운 선분
        result += y - x
        x, y = temp_x, temp_y

print(result + (y - x))