출처: [백준] 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("고무오리야 사랑해")

1. 20% 넘어선 국내 클라우드 이용률… 유료화·서비스 종료로 선택지는 줄어

20% 넘어선 국내 클라우드 이용률… 유료화·서비스 종료로 선택지는 줄어

개인용 클라우드 이용률은 높아졌지만 이용할 수 있는 클라우드 선택지는 줄어드는 모습이다. 구글이 최근 클라우드 서비스 유료화를 시작했고, 경쟁에서 밀려난 이통3사 등은 ‘변화된 시장 환경’을 이유로 클라우드 서비스를 종료하고 있다. LG유플러스는 올해 12월 개인 클라우드인 ‘U+박스’를 종료하고, SK텔레콤도 오는 9월27일 개인용 클라우드 서비스인 ‘클라우드 베리’를 종료하기로 했으며, 앞서 KT는 지난해 개인 클라우드 서비스를 종료했고 삼성전자도 갤럭시 스마트폰 이용자에게 제공하던 삼성 클라우드 서비스를 최근 종료하고, 마이크로소프트 원드라이브로 데이터를 이전하도록 했다.

2. “카카오택시에 상대도 안돼?”…‘우티’의 굴욕

“카카오택시에 상대도 안돼?”…‘우티’의 굴욕

SK텔레콤의 모빌리티 기업 ‘T맵 모빌리티’와 우버가 함께 만든 택시 호출 플랫폼 ‘우티’가 고전하고 있는데 출범 초기 이용자가 증가하며 순항하는 듯 했으나, 한 달만에 30만 명이 줄어들며 주춤하는 모양새다.

택시 호출 중개 시장은 ‘모빌리티’ 경쟁의 최전선이다. 대중화된 택시 호출 서비스에서 충분한 이용객을 확보해야 향후 대리 운전, 렌트카, 차량 공유, 전동 킥보드 등 개인형 이동수단(PM) 등 이동·운송 서비스 확장이 용이하기 때문이다.

3. 새 주인 찾는 인터파크, 누가 탐낼까?

새 주인 찾는 인터파크, 누가 탐낼까?

국내 1세대 이커머스 플랫폼인 인터파크가 매물로 나오면서 인수 후보에 관심이 쏠리고 있다. 시장에서는 항공과 티켓 판매 서비스를 제공 중인 네이버와 카카오도 인수 후보로 거론되고 있고 NHN티켓링크를 자회사로 두고 있는 NHN 또한 인터파크를 인수해 업계 1위로 올라설 수 있는 기회가 될 수 있다. NHN 자회사인 여행박사와 시너지를 낼 수 있는 기회이기도 하다.

4. 도쿄올림픽, 모바일은 어디서?…네이버·카카오 등 중계권 협상

도쿄올림픽, 모바일은 어디서?…네이버·카카오 등 중계권 협상

14일 업계에 따르면 네이버, 카카오, 웨이브, 아프리카TV, KT 시즌(Seezn) 등이 현재 지상파 3사와 도쿄올림픽 온라인 중계권 협상을 진행 중인 것으로 알려졌으며, 최근까지 쿠팡의 단독 중계권을 거의 확보한 듯한 형국이었으나, 협상 내용이 밝혀진 뒤 ‘보편적 시청권’ 논란이 일면서 쿠팡이 철회 의사를 밝힌 것으로 알려졌다.

하지만 코로나19 확산과 스타선수의 부재 등으로 도쿄올림픽에 대한 국민적 관심이 예년 같지 않아, 쿠팡이 올려놓은 중계권료를 지출하는 데 큰 부담을 느끼고 있는 것으로 전해졌다.

5. 5년전 美증시 입성한 라인의 ‘나비효과’…”카카오 안부럽다”

5년전 美증시 입성한 라인의 ‘나비효과’…”카카오 안부럽다”

5년 전 상장 당시 이해진 창업자(현 글로벌투자책임자)는 “라인이 이제는 도쿄와 뉴욕에 상장되며 글로벌 브랜드의 힘을 갖게 된 것이 너무 기쁘다”며 “조금 더 공격적으로 할 수 있는 자금이 확보되고, 성장할 수 있는 계기 마련됐다. 기술 쪽에 가장 많이 투자할 것”이라고 말하기도 했다.

이같은 네이버의 행보가 쿠팡의 뉴욕 상장 등 여타 IT 기업의 글로벌 진출에 긍정적 영향을 줬다는 분석도 나온다. 국내 스타트업 하이퍼커넥트 ‘아자르’가 중동에서 큰 성공을 거둔뒤, ‘틴더’를 운영하는 매치그룹에 약 2조원에 매각되는 등 국내에서의 성공만이 답이 아니라는 점을 알려줬다는 것이다.

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

1. [단독] “타도 오늘의집”…집꾸미기-하우저 전격합병

[단독] “타도 오늘의집”…집꾸미기-하우저 전격합병

연 42조원에 달하는 인테리어 시장은 코로나19 사태 이후 e커머스로 급격히 전환하면서 선두 다툼이 치열해지고 있으며, 업계 1위 오늘의집을 따라잡기 위해 2위인 집꾸미기와 3위 하우저가 전격 합병한다.

• 집꾸미기는 인테리어 콘텐츠 커뮤니티를 운영하며 이를 기반으로 커머스 영업을 하는 인테리어 거래 플랫폼
• 하우저는 빅데이터를 활용해 가구, 가전 물류를 효율화하는 인테리어 스마트 물류 플랫폼이다.

거래 플랫폼과 물류 플랫폼을 합쳐 시너지를 낸다는 방안으로 두 회사의 기업가치는 500억원 수준으로 알려졌지만, 벤처캐피털(VC) 업계 관계자는 두 회사의 시너지를 생각하면 훨씬 더 높은 가치를 받을 것”이라고 말했다.

2. 야놀자 “손정의 회장 1조 투자설? 확인해줄 수 없어”

야놀자 “손정의 회장 1조 투자설? 확인해줄 수 없어”

여가 플랫폼 야놀자 측이 최근 1조원에 이르는 손정의 일본 소프트뱅크그룹 회장의 대규모 투자설과 관련해 “확인해줄 수 없다”고 12일 입장을 밝혔다으며 앞서 투자유치설에 대해 ‘사실무근’이라고 했다가 ‘노코멘트’로 입장을 선회해 그 배경에 관심이 쏠린다.

야놀자는 올해 IPO는 물론 해외상장도 모색 중으로, 최근 장외거래시장에서 9~10조원 이상 가치로 거래되고 있는 유니콘(기업가치 1조원 이상 비상장기업)이다.

3. 무디스 “카뱅, 1년 후 대출시장 점유율 65%까지 확대”

무디스 “카뱅, 1년 후 대출시장 점유율 65%까지 확대”

신용평가회사 무디스는 카카오뱅크가 대출 시장에서 향후 큰 폭의 성장을 하고, 전통 은행들에 빅테크의 위협을 분명하게 보여주게 될 것이라고 분석했고, 최근 발표한 보고서에서 “카카오뱅크가 주택담보대출과 중소상공인 대출 상품을 출시할 경우 전체 원화대출 시장서 차지하는 비중이 향후 12~18개월간 현재의 14%에서 65%까지 확대될 것”이라고 예상했다.

또한 무디스는 올해 하반기 상장 후 카카오뱅크의 자본이 3월말 대비 약 76~90% 늘어날 것으로 예상했고 아울러 카카오뱅크가 첨단 기술을 활용하는 동시에 오프라인 점포 없이 운영해 다른 은행 대비 상대적으로 낮은 비용구조를 유지하고 있다는 점이 긍정적이라고 평가했다.

4. 셧다운제 폐지 법안 쏟아지는데…버티는 여가부

셧다운제 폐지 법안 쏟아지는데…버티는 여가부

심야시간대에 청소년들의 인터넷게임 접속을 제한하는 셧다운제 폐지 법안이 연이어 발의되면서 논의에 속도가 붙고 있으며, 셧다운제는 시행 후 약 10년 동안 실효성 논란에 휩싸여왔으며 사실상 실패한 법이라는 평가가 지배적이다.

최근 촉발된 마이크로소프트(MS)의 게임 ‘마인크래프트’ 사태는 다시 한 번 셧다운제 폐지 논의에 불을 지폈다. 마인크래프트는 교육용으로도 사용되는 청소년 인기 게임으로 알려져 있다.

한국행정학회가 2017년 한국콘텐츠진흥원에 제출한 ‘청소년 게임이용시간 제한제도 개선방안 연구’ 용역 과제 보고서에 따르면 게임이용시간 자체에 대한 통제의 정책적 효과가 예상보다 크지 않은 것으로 나타났다.

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