출처: [백준] 2257번 화학식량

문제

우리가 널리 사용하는 H2O(물), CH3COOH(아세트산)과 같은 화학식은 알파벳과 숫자, 그리고 괄호로 구성된다. 먼저 알파벳은 원자를 나타내는 것으로 H는 수소(Hydrogen), C는 탄소(Carbon), O는 산소(Oxygen) 원자를 뜻한다. 또한 원자를 나타내는 알파벳 뒤에 따르는 숫자는 그 원자가 몇 개 포함되어 있는지를 뜻한다. 따라서 COOHHH 분자는 CO2H3로 나타낼 수 있다. 이 문제에서, 숫자는 항상 2 이상 9 이하로만 입력으로 주어진다. 따라서 CO23과 같이 숫자가 두자리인 경우는 없다.

물의 화학식을 보고 물은 두 개의 수소 원자와 한 개의 산소 원자로 이루어졌음을 알 수 있다. 또한 아세트산의 화학식처럼 한 종류의 알파벳이 화학식에 여러 번 나타날 수도 있다. 실제 화학식 또한 이렇게 사용되는데, 이는 분자의 결합 구조를 나타내기 위함이다.

종종 화학식에는 괄호가 사용되기도 하는데 괄호로 묶인 원자들은 하나의 새로운 원자와 같은 작용을 한다. 따라서 CH(CO2H)(CO2H)(CO2H) 분자는 CH(CO2H)3와 같이 나타낼 수 있다. 괄호 안에 아무런 알파벳도 없는 경우도 있을 수 있는데, 이런 경우는 괄호가 없는 경우와 마찬가지라고 생각하면 된다.

이러한 화학식을 보고 우리는 화학식량을 계산할 수 있는데, 화학식량이란 그 화학식에 포함되어 있는 모든 원자들의 질량의 합을 말한다. 수소 원자 하나의 질량은 1, 탄소 원자 하나의 질량은 12, 산소 원자 하나의 질량은 16이다. 물은 두 개의 수소 원자와 한 개의 산소 원자로 이루어져 있으므로 물의 화학식량은 18이다.

화학식이 주어졌을 때, 이 화학식의 화학식량을 계산하는 프로그램을 작성하시오. 화학식은 수소, 탄소, 산소만을 포함하고 있는 것만이 입력으로 주어진다.

입력

첫째 줄에 화학식이 주어진다. 화학식은 H, C, O, (, ), 2, 3, 4, 5, 6, 7, 8, 9만으로 이루어진 문자열이며, 그 길이는 100을 넘지 않는다.

출력

첫째 줄에 화학식량을 출력한다. 분자량이 10,000이 넘는 고분자는 입력으로 주어지지 않는다.

예제 입력 1

1

(H)2(O)

예제 출력 1

1

18

출처

• ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2009 Arab Collegiate Programming Contest A번
  • 문제를 번역한 사람: baekjoon

알고리즘 분류

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

소스코드

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

import sys

input = sys.stdin.readline

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

values = {'H': 1, 'C': 12, 'O': 16}
stack = []
tmp = 0
for x in input_string:
    if x == '(':
        stack.append(x)
    elif x == ')':
        tmp = 0
        while stack[-1] != '(':
            num = stack.pop()
            tmp += num
        stack.pop()
        stack.append(tmp)
    elif x.isdigit():
        tmp = stack.pop()
        stack.append(tmp * int(x))
    else:
        stack.append(values[x])

print(sum(stack))

출처: [백준] 11899번 괄호 끼워넣기

문제

심심한 승현이는 너무 심심한 나머지 올바른 괄호열을 가지고 놀고 있었습니다.

1

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

그러다가 어쩌다 보니 괄호열을 부러뜨렸습니다.

1

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

크게 낙담한 승현이는 노력해 보았지만, 대부분이 부러져 버려 단 한 부분만 재사용할 수 있다는 것을 깨닫게 되었습니다.

1

)))()

승현이는 이 괄호열을 가지고 놀려고 했으나 올바른 괄호열이 아니기 때문에 행복하지 않았습니다. 이를 보던 지학이는 승현이에게 “그러면 앞과 뒤에 적절하게 괄호를 붙이면 올바른 괄호열이 되지 않을까?”라고 했고, 승현이는 조금 생각한 뒤 그렇게 하기로 했습니다. 예를 들어, 위의 올바르지 않은 괄호열의 경우 앞에 여는 괄호 3개를 붙이면 올바른 괄호열이 됩니다.

1

((()))()

그러나 괄호열을 사서 붙이는 데에는 돈이 들고 많이 붙일수록 놀기가 불편해지기 때문에, 승현이는 가능한 한 괄호열을 적게 추가하려고 합니다.

승현이가 망가뜨리고 사용 가능한 올바르지 않은 괄호열이 주어질 때, 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 구하는 프로그램을 작성하세요.

입력

첫 번째 줄에 올바르지 않은 괄호열 S가 주어집니다. S의 길이는 1 이상 50 이하입니다.

출력

첫 번째 줄에 S를 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 출력합니다. 불가능한 경우는 주어지지 않습니다.

예제 입력 1

1

)))()

예제 출력 1

1

3

예제 입력 2

1

)(()

예제 출력 2

1

2

예제 입력 3

1

))()((

예제 출력 3

1

4

예제 입력 4

1

)(()(()))

예제 출력 4

1

1

힌트

괄호열이란 여는 괄호 ‘(’와 닫는 괄호 ‘)’로만 구성된 문자열을 말합니다.

올바른 괄호열은 아래와 같이 정의할 수 있습니다.

• “()”는 올바른 괄호열입니다.
• A가 올바른 괄호열이라면 “(A)” 역시 올바른 괄호열입니다.
• A와 B가 모두 올바른 괄호열이라면 “AB” 역시 올바른 괄호열입니다.

출처

• Contest > GENIUSainta.com - oj.uz Contest > GA6 1번

알고리즘 분류

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

소스코드

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

import sys

input = sys.stdin.readline

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

left = []
right = []

for x in input_string:
    if x == '(':
        left.append(x)
    elif x == ')':
        if left:
            left.pop()
        else:
            right.append(x)

print(len(left) + len(right))

출처: [백준] 20001번 고무오리 디버깅

문제

백준 문제 풀이에 힘들어하는 수진이를 위해 민우는 문제해결에 도움이 되는 고무오리를 준비했다. 민우가 준비한 고무오리는 신비한 능력이 존재하는데, 최근에 풀던 백준 문제를 해결해주는 능력이다. 신비한 고무오리와 함께 수진이의 백준 풀이를 도와주자!

고무오리의 사용법은 다음과 같다.

• “고무오리 디버깅 시작” 이라고 외친다
• 문제들을 풀기 시작한다
• 고무오리를 받으면 최근 풀던 문제를 해결한다
• “고무오리 디버깅 끝” 이라고 외치면 문제풀이를 종료한다.

하지만 고무오리에는 치명적인 문제가 있는데, 풀 문제가 없는데 사용한다면 고무오리는 체벌로 두 문제를 추가한다는 점이다.

입력

첫 번째 줄에 “고무오리 디버깅 시작”이라고 주어진다. 두 번째 줄부터 “고무오리” 또는 “문제”가 주어진다. 이는 “고무오리 디버깅 끝”이 주어질 때까지 반복한다. 최대 102줄이 입력으로 주어진다.

출력

고무오리 디버깅이 끝날 때, 주어진 문제를 수진이가 해결하였는지 여부에 따라 남은 문제 없이 모든 문제를 해결하였으면 “고무오리야 사랑해”을 출력하고 하나라도 문제가 남았다면 “힝구”를 출력하라.

예제 입력 1

1
2
3
4
5
6
7
8

고무오리 디버깅 시작
문제
고무오리
문제
문제
고무오리
고무오리
고무오리 디버깅 끝

예제 출력 1

1

고무오리야 사랑해

예제 입력 2

1
2
3
4
5

고무오리 디버깅 시작
고무오리
고무오리
고무오리
고무오리 디버깅 끝

예제 출력 2

1

고무오리야 사랑해

예제 입력 3

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

고무오리 디버깅 시작
문제
문제
고무오리
고무오리
고무오리
문제
고무오리
문제
고무오리
고무오리
고무오리
고무오리 디버깅 끝

예제 출력 3

1

고무오리야 사랑해

예제 입력 4

1
2
3

고무오리 디버깅 시작
고무오리
고무오리 디버깅 끝

예제 출력 4

1

힝구

출처

• University > 충남대학교 > 제4회 생각하는 프로그래밍 대회 A번
  • 빠진 조건을 찾은 사람: jh05013
  • 문제를 만든 사람: siontama

알고리즘 분류

• 구현
• 자료 구조
• 스택

소스코드

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

start = input().rstrip()

question = []
while True:
    input_string = input().rstrip()
    if input_string == '고무오리 디버깅 끝':
        break
    else:
        if input_string == '문제':
            question.append(0)
        elif input_string == '고무오리':
            if question:
                question.pop()
            else:
                question.append(0)
                question.append(0)

if question:
    print("힝구")
else:
    print("고무오리야 사랑해")

출처: [백준] 12789번 도키도키 간식드리미

문제

인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다.

그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.

사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.

현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.

위 예제는 다음 그림과 같이 움직였을 때 모두가 순서대로 간식을 받을 수 있다..

입력

입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.

다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,…,N) 순서가 앞에서부터 뒤 순서로 주어진다.

출력

승환이가 무사히 간식을 받을 수 있으면 “Nice”(따옴표는 제외)를 출력하고 그렇지 않다면 “Sad”(따옴표는 제외)를 출력한다.

예제 입력 1

1
2

5
5 4 1 3 2

예제 출력 1

1

Nice

출처

• University > 인하대학교 > 2016 IUPC 인하대학교 프로그래밍 경진대회 L번
  • 문제의 오타를 찾은 사람: 10_J
  • 잘못된 데이터를 찾은 사람: tncks0121
  • 문제를 만든 사람: tndnjs2139

알고리즘 분류

• 자료 구조
• 스택

소스코드

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

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

init_line = deque(map(int, input().split()))
wait_line = deque()

pos = 1
while init_line:
    if init_line and init_line[0] == pos:
        init_line.popleft()
        pos += 1
    else:
        wait_line.append(init_line.popleft())

    while wait_line and wait_line[-1] == pos:
        wait_line.pop()
        pos += 1

if wait_line:
    print('Sad')
else:
    print("Nice")

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