출처: [백준] 17952번 과제는 끝나지 않아!

문제

성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이다. 다행히 과제 제출 기한은 학기가 끝날 때까지이다. 너무나도 많은 과제를 하다가 미쳐버린 성애는 아래와 같은 규칙으로 과제를 해 나가고 있다.

1. 과제는 가장 최근에 나온 순서대로 한다. 또한 과제를 받으면 바로 시작한다.
2. 과제를 하던 도중 새로운 과제가 나온다면, 하던 과제를 중단하고 새로운 과제를 진행한다.
3. 새로운 과제가 끝났다면, 이전에 하던 과제를 이전에 하던 부분부터 이어서 한다. (성애는 기억력이 좋기 때문에 아무리 긴 시간이 지나도 본인이 하던 부분을 기억할 수 있다.)

성애는 과제를 받자마자 이 과제가 몇 분이 걸릴지 정확하게 알 수 있고, 성애가 제출한 과제는 무조건 만점을 받는다.

성애는 이번 학기에 자기가 받을 과제 점수를 예상해보고 싶다. 하지만 과제 점수를 예상하는 지금도 과제가 추가되고 있기에 여유를 부릴 수가 없다. 여러분이 성애가 받을 과제 점수를 구해주자!

입력

첫째 줄에 이번 학기가 몇 분인지를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

두번째 줄부터 N줄 동안은 학기가 시작하고 N분째에 주어진 과제의 정보가 아래의 두 경우 중 하나로 주어진다.

• 1 A T: 과제의 만점은 A점이고, 성애가 이 과제를 해결하는데 T분이 걸린다. A와 T는 모두 정수이다. (1 ≤ A ≤ 100, 1 ≤ T ≤ 1,000,000)
• 0: 해당 시점에는 과제가 주어지지 않았다.

출력

성애가 받을 과제 점수를 출력한다.

예제 입력 1

1
2
3
4

3
1 100 3
0
0

예제 출력 1

1

100

• 1분째: 100점짜리 과제 1이 주어지고 이 과제를 하는데 3분이 걸린다. 과제를 받자마자 시작했으므로 과제 1이 끝나는데는 이제 2분 남았다.
• 2분째: 새로운 과제가 주어지지 않았으므로 과제 1을 이어서 한다.
• 3분째: 새로운 과제가 주어지지 않았으므로 과제 1을 이어서 한다. 이 시점에 과제 1이 끝나서 100점을 획득한다.

예제 입력 2

1
2
3
4
5
6

5
1 10 3
0
1 100 2
1 20 1
0

예제 출력 2

1

120

• 1분째 : 과제 1이 나왔고, 받자마자 바로 시작했으므로 과제 1이 끝나기까지 2분 남았다.
• 2분째 : 새로운 과제가 나오지 않았으므로 과제 1을 이어서 한다.
• 3분째 : 과제 2가 나왔고, 받자마자 바로 시작했으므로, 과제 2가 끝나기까지 1분 남았다.
• 4분째 : 과제 3이 나왔고, 받자마자 바로 시작했으므로, 과제 3을 끝내서 20점을 얻는다.
• 5분째 : 새로운 과제가 나오지 않았으므로 이전에 하던 과제 2를 이어서 하고, 과제 2를 끝내서 100점을 얻는다.

출처

• University > 한양대학교 > 제6회 한양대학교 프로그래밍 경시대회 Beginner Division A번
• University > 한양대학교 > 제6회 한양대학교 프로그래밍 경시대회 Advanced Division A번
  • 데이터를 추가한 사람: hayman42
  • 문제를 만든 사람: pch6828

알고리즘 분류

• 구현
• 자료 구조
• 스택

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import sys

input = sys.stdin.readline

N = int(input())
# 1 A T: 과제O, 점수, 걸린 시간

work_list = []
score = 0
for _ in range(N):
    info = list(map(int, input().split()))
    if info[0] == 1:  # 과제를 받았으면
        if info[2] - 1 > 0:
            work_list.append((info[1], info[2] - 1))
        else:
            score += info[1]
    else:  # 과제가 없으면
        if work_list:
            work = work_list.pop()
            if work[1] - 1 > 0:
                work_list.append((work[0], work[1] - 1))
            else:
                score += work[0]

print(score)

출처: [백준] 1935번 후위 표기식2

문제

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

입력

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. (3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C …이 주어진다, 그리고 피연산자에 대응 하는 값은 정수이다)

출력

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

예제 입력 1

1
2
3
4
5
6
7

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

예제 출력 1

1

6.20

예제 입력 2

1
2
3

1
AA+A+
1

예제 출력 2

1

3.00

출처

• 데이터를 추가한 사람: arine
• 빠진 조건을 찾은 사람: ljk0411jg
• 문제의 오타를 찾은 사람: masioka, whtjddjs0723

알고리즘 분류

• 자료 구조
• 스택

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import sys

input = sys.stdin.readline

N = int(input())
postfix = input().rstrip()
num_list = [int(input()) for _ in range(N)]

stack = []
for element in postfix:
    if 'A' <= element <= 'Z':
        stack.append(num_list[ord(element) - ord('A')])
    else:
        num2, num1 = stack.pop(), stack.pop()

        if element == '+':
            stack.append(num1 + num2)
        elif element == '-':
            stack.append(num1 - num2)
        elif element == '*':
            stack.append(num1 * num2)
        elif element == '/':
            stack.append(num1 / num2)

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

출처: [백준] 2304번 창고 다각형

문제

N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.

1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
4. 지붕의 가장자리는 땅에 닿아야 한다.
5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

그림1 . 기둥과 지붕(굵은 선)의 예

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.

출력

첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8

7
2 4
11 4
15 8
4 6
5 3
8 10
13 6

예제 출력 1

1

98

출처

• Olympiad > 한국정보올림피아드 > KOI 2005 > 초등부 2번

알고리즘 분류

• 자료 구조
• 브루트포스 알고리즘
• 스택

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import sys

input = sys.stdin.readline

N = int(input())
pillars = []
for _ in range(N):
    idx, height = map(int, input().split())
    pillars.append((idx, height))

pillars.sort(key=lambda x: x[0])  # 정렬

max_pillar = max(pillars, key=lambda x: x[1])  # 가장 높은 기둥찾기

# 땅에 기둥세우기
area = [0] * (pillars[-1][0] + 1)
for idx, height in pillars:
    area[idx] = height
max_index = area.index(max_pillar[1])  # 높은 기둥의 인덱스찾기

temp = 0
total = 0
# 왼쪽부터 가장 높은 기둥까지
for i in range(max_index + 1):
    if area[i] > temp:
        temp = area[i]
    total += temp

temp = 0
# 오른쪽부터 가장높은 기둥까지
for i in range(pillars[-1][0], max_index, -1):
    if area[i] > temp:
        temp = area[i]
    total += temp

print(total)

출처: [백준] 12605번 단어순서 뒤집기

문제

스페이스로 띄어쓰기 된 단어들의 리스트가 주어질때, 단어들을 반대 순서로 뒤집어라. 각 라인은 w개의 영단어로 이루어져 있으며, 총 L개의 알파벳을 가진다. 각 행은 알파벳과 스페이스로만 이루어져 있다. 단어 사이에는 하나의 스페이스만 들어간다.

입력

첫 행은 N이며, 전체 케이스의 개수이다.

N개의 케이스들이 이어지는데, 각 케이스는 스페이스로 띄어진 단어들이다. 스페이스는 라인의 처음과 끝에는 나타나지 않는다. N과 L은 다음 범위를 가진다.

• N = 5
• 1 ≤ L ≤ 25

출력

각 케이스에 대해서, 케이스 번호가 x일때 “Case #x: “ 를 출력한 후 그 후에 이어서 단어들을 반대 순서로 출력한다.

예제 입력 1

1
2
3
4

3
this is a test
foobar
all your base

예제 출력 1

1
2
3

Case #1: test a is this
Case #2: foobar
Case #3: base your all

출처

• Contest > Google Code Jam > Google Code Jam Africa 2010 > Qualification Round B1번

알고리즘 분류

• 구현

• 자료 구조

• 문자열

• 스택

소스코드

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

import sys

input = sys.stdin.readline

N = int(input())

for i in range(N):
    sentence = list(input().rstrip().split())
    result = []
    while sentence:
        result.append(sentence.pop())
    print('Case #{0}: {1}'.format(i + 1, ' '.join(result)))

출처: [백준] 5397번 키로거

문제

창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다.

키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다.

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이스를 입력했다면, ‘-‘가 주어진다. 이때 커서의 바로 앞에 글자가 존재한다면, 그 글자를 지운다. 화살표의 입력은 ‘<’와 ‘>’로 주어진다. 이때는 커서의 위치를 움직일 수 있다면, 왼쪽 또는 오른쪽으로 1만큼 움직인다. 나머지 문자는 비밀번호의 일부이다. 물론, 나중에 백스페이스를 통해서 지울 수는 있다. 만약 커서의 위치가 줄의 마지막이 아니라면, 커서 및 커서 오른쪽에 있는 모든 문자는 오른쪽으로 한 칸 이동한다.

출력

각 테스트 케이스에 대해서, 강산이의 비밀번호를 출력한다. 비밀번호의 길이는 항상 0보다 크다.

예제 입력 1

1
2
3

2
<<BP<A>>Cd-
ThIsIsS3Cr3t

예제 출력 1

1
2

BAPC
ThIsIsS3Cr3t

출처

• ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2010 I번
  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: djm03178
  • 문제의 오타를 찾은 사람: eles320
  • 잘못된 번역을 찾은 사람: jh05013

알고리즘 분류

• 자료 구조
• 스택
• 연결 리스트

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    stack = list(input().rstrip())
    left, right = [], []

    for x in stack:
        if x == '<':
            if left:
                right.append(left.pop())
        elif x == '>':
            if right:
                left.append(right.pop())
        elif x == '-':
            if left:
                left.pop()
        else:
            left.append(x)

    if right:
        left.extend(reversed(right))

    print(''.join(left))

    
    
----------------시간초과-------------------
import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    stack = list(input().rstrip())
    password = []

    cur = 0
    while stack:
        temp = stack.pop()
        if temp == '-' and stack:
            stack.pop()
        elif temp == '>':
            cur -= 1
        elif temp == '<':
            cur += 1
        else:
            password.insert(cur, temp)
            cur = 0

    print(''.join(password))

출처: [백준] 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

1
2
3
4
5
6
7

6
6
9
7
6
4
6

예제 출력 1

1

3

예제 입력 2

1
2
3
4
5
6

5
5
4
3
2
1

예제 출력 2

1

5

출처

• Olympiad > 한국정보올림피아드 > KOI 2019 1차대회 > 초등부 1번

알고리즘 분류

• 구현
• 자료 구조
• 스택

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import sys

input = sys.stdin.readline

N = int(input())

stack = [int(input()) for _ in range(N)]

max_height = 0
cnt = 0
while stack:
    temp = stack.pop()
    if temp > max_height:
        max_height = temp
        cnt += 1

print(cnt)

출처: [백준] 3986번 좋은 단어

문제

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 ‘좋은 단어’나 세보기로 마음 먹었다.

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 ‘좋은 단어’이다. 평석이가 ‘좋은 단어’ 개수를 세는 것을 도와주자.

입력

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

다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

출력

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

예제 입력 1

1
2
3
4

3
ABAB
AABB
ABBA

예제 출력 1

1

2

예제 입력 2

1
2
3
4

3
AAA
AA
AB

예제 출력 2

1

1

예제 입력 3

1
2

1
ABBABB

예제 출력 3

1

1

출처

• Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #4 2번
  • 문제를 번역한 사람: baekjoon, csehydrogen

알고리즘 분류

• 자료 구조
• 문자열
• 스택

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import sys

input = sys.stdin.readline
N = int(input())
cnt = 0

for _ in range(N):
    stack = []
    word = list(input().rstrip())

    while word:
        temp = word.pop()
        if not stack:
            stack.append(temp)
        else:
            if stack[-1] == temp:
                stack.pop()
            else:
                stack.append(temp)
    if not stack:
        cnt += 1

print(cnt)

출처: [백준] 10799번 쇠막대기

문제

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.

1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.

위 예의 괄호 표현은 그림 위에 주어져 있다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

입력

한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.

출력

잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.

예제 입력 1

1

()(((()())(())()))(())

예제 출력 1

1

17

예제 입력 2

1

(((()(()()))(())()))(()())

예제 출력 2

1

24

출처

• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 중등부 2번
• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2015 > 초등부 3번
  • 데이터를 만든 사람: baekjoon
  • 데이터를 추가한 사람: djm03178

알고리즘 분류

• 자료 구조
• 스택

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import sys

input = sys.stdin.readline

razer = list(input().rstrip())
# print(razer)

answer = 0
stack = []

for i in range(len(razer)):
    if razer[i] == '(':
        stack.append('(')
    else:
        if razer[i - 1] == '(':  # )가 왔는데 이전이 바로 (일 경우
            stack.pop()
            answer += len(stack)
        else:
            stack.pop()
            answer += 1

print(answer)

출처: [백준] 1406번 에디터

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 ‘커서’라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

예제 입력 1

1
2
3
4
5

abcd
3
P x
L
P y

예제 출력 1

1

abcdyx

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11

abc
9
L
L
L
L
L
P x
L
B
P y

예제 출력 2

1

yxabc

예제 입력 3

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

dmih
11
B
B
P x
L
B
B
B
P y
D
D
P z

예제 출력 3

1

yxz

출처

• Olympiad > Croatian Highschool Competitions in Informatics > 2004 > National Competition #1 - Juniors 2번
  • 문제를 번역한 사람: author5
  • 데이터를 추가한 사람: djm03178
  • 메모리 제한을 수정한 사람: djm03178
  • 시간 제한을 수정한 사람: jh05013
  • 어색한 표현을 찾은 사람: naong606
  • 문제의 오타를 찾은 사람: wkd48632

알고리즘 분류

• 자료 구조
• 스택
• 연결 리스트

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

import sys

input = sys.stdin.readline

init_string = list(input().rstrip())
N = int(input())
string2 = []

for _ in range(N):
    comm = list(input().split())
    if comm[0] == 'P':
        init_string.append(comm[1])
    elif comm[0] == 'L':
        if init_string:
            string2.append(init_string.pop())
    elif comm[0] == 'D':
        if string2:
            init_string.append(string2.pop())
    elif comm[0] == 'B':
        if init_string:
            init_string.pop()
            
print(''.join(init_string + list(reversed(string2))))






----------시간초과1---------------------
import sys

input = sys.stdin.readline

init_string = input().rstrip()
N = int(input())
cursor = len(init_string)
for _ in range(N):
    comm = list(input().split())
    if comm[0] == 'P':
        init_string = init_string[0:cursor] + comm[1] + init_string[cursor:]
        cursor += 1
    elif comm[0] == 'L':
        if not cursor == 0:
            cursor -= 1
        else:
            continue
    elif comm[0] == 'D':
        if not cursor == len(init_string):
            cursor += 1
        else:
            continue

    elif comm[0] == 'B':
        if cursor == 0:
            continue
        else:
            init_string = init_string[0:cursor - 1] + init_string[cursor:]
            cursor -= 1
print(''.join(init_string))



-----------시간초과2---------------
import sys

input = sys.stdin.readline

init_string = list(input().rstrip())
N = int(input())
cursor = len(init_string)
for _ in range(N):
    comm = list(input().split())
    if comm[0] == 'P':
        init_string.insert(cursor, comm[1])
        cursor += 1
    elif comm[0] == 'L':
        cursor -= 1
        if cursor < 0:
            cursor = 0
    elif comm[0] == 'D':
        cursor += 1
    elif comm[0] == 'B':
        if cursor == 0:
            continue
        else:
            cursor -= 1
            init_string.pop(cursor)

print(''.join(init_string))

출처: [백준] 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) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

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

입력

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

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

예제 입력 1

1

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

예제 출력 1

1

28

출처

• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2008 > 초등부 4번
• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2008 > 중등부 2번
  • 데이터를 추가한 사람: 906bc, djm03178, eatgugbab, leedongbin, sang7, sankim90
  • 잘못된 데이터를 찾은 사람: djm03178

알고리즘 분류

• 구현
• 자료 구조
• 스택
• 재귀

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

import sys

input = sys.stdin.readline

input_string = list(input().rstrip())

stack = []


def solution(string):
    for bracket in string:

        if bracket == ')':
            tmp = 0
            while stack:
                top = stack.pop()
                if top == '(':
                    if tmp == 0:
                        stack.append(2)
                    else:
                        stack.append(tmp * 2)
                    break
                elif top == '[':
                    return 0
                else:
                    tmp += int(top)

        elif bracket == ']':
            tmp = 0
            while stack:
                top = stack.pop()
                if top == '[':
                    if tmp == 0:
                        stack.append(3)
                    else:
                        stack.append(tmp * 3)
                    break
                elif top == '(':
                    return 0
                else:
                    tmp += int(top)
        else:
            stack.append(bracket)
    return stack


if solution(input_string):
    print(0 if '(' in stack or '[' in stack else sum(stack))
else:
    print(0)