1. 라인, 글로벌 CBDC 정조준…블록체인 플랫폼 공개

라인, 글로벌 CBDC 정조준…블록체인 플랫폼 공개

라인플러스는 이번에 오픈한 라인 파이낸셜 블록체인 홈페이지를 통해 CBDC를 위한 블록체인 시스템, 전 세계 각국의 CBDC 발행 현황 및 CBDC 에 대한 개념도 소개해 누구나 쉽게 볼 수 있도록 하고 있다.

라인 파이낸셜 블록체인은 금융 플랫폼에 최적화된 블록체인 플랫폼으로 CBDC 사업이 요구하는 결제 완결성을 보장하고, 빠른 속도와 많은 결제량을 처리할 수 있는 확장성을 제공하며 특히 라인이 글로벌 서비스를 운영한 기술력을 바탕으로 결제 정보에 대한 기밀성을 보장한다.

• 중앙은행 발행 디지털화폐(CBDC)

2. 스포츠에 집중하는 카카오게임즈…코로나 타격에도 베팅 ‘턱턱’, 왜?

스포츠에 집중하는 카카오게임즈…코로나 타격에도 베팅 ‘턱턱’, 왜?

9일 관련 업계에 따르면 카카오게임즈는 글로벌 레저·스포츠 커뮤니케이션 전문 기업 세나테크놀로지와 손잡고, 스포츠 커뮤니케이션 플랫폼 영역을 개척하기 위해 카카오게임즈는 약 1000억을 들여 해당 기업을 계열사로 편입시켰고, 카카오 VX가 전개하는 스포츠 및 헬스케어 등 서비스와의 연계를 통한 스포츠 사업으로 확장해나간다는 계획이다.

KB금융지주가 지난달 발표한 ‘코로나19가 갈라놓은 골프연습장과 스크린골프장의 차별화’ 보고서에 따르면, 지난해 골프 인구는 515만명으로 전년 대비 46만명가량 증가했다. 그간 골프 시장을 눈여겨봐왔던 카카오는 자회사 카카오게임즈 산하에 2012년 설립됐던 옛 마음골프를 인수한 뒤 이름을 카카오 VX로 바꿨다.

카카오 VX는 성장력과 인지도를 동시에 키우는 데 무서운 속도를 내고 있으며, 이를 뒷받침하는 건, 게임기업으로 성장했던 경험을 바탕으로 LBS(위치기반), VR(가상현실), AI(인공지능) 등 첨단 기술을 융합해 대중을 대상으로 하는 신사업 영역을 펼쳐나가고 있었던 카카오게임즈의 전략적 투자다.

3. 티빙, 독일 분데스리가 독점 중계 “유로2020 열기 이어간다”

티빙, 독일 분데스리가 독점 중계 “유로2020 열기 이어간다”

티빙은 2021-22시즌 독일 분데스리가 경기 국내 독점 중계권을 확보하고, 다음달부터 티빙과 채널 tvN, XtvN을 통해 생중계한다. 총 150경기를 생중계하며, 이 중 65경기는 티빙에서만 단독 중계된다.

티빙 콘텐츠사업국 황혜정 국장은 “유로 2020에 보여주신 뜨거운 열기에 보답하고자 유럽 빅리그 중 하나인 분데스리가 생중계를 확정했다”며 “앞으로도 스포츠 생중계와 같이 다양한 장르의 독점 수급 라이브러리를 확대하며 콘텐츠 경쟁력을 강화할 계획”이라고 말했다.

4. “코로나19 퍼지면 안돼”…다시 전면 재택근무 돌입하는 게임사들

“코로나19 퍼지면 안돼”…다시 전면 재택근무 돌입하는 게임사들

9일 게임업계에 따르면 크래프톤, 넥슨, 넷마블, 엔씨소프트 등 주요 게임사들은 코로나19 확산을 막기 위해 오는 12일부터 전면 재택근무에 돌입한다.

5. “별점테러 그만”…네이버, 맛집 ‘키워드 리뷰’ 연내 도입(종합)

“별점테러 그만”…네이버, 맛집 ‘키워드 리뷰’ 연내 도입(종합)

네이버가 최근 사회적 문제가 되는 ‘별점 테러’, ‘리뷰 갑질’ 등을 막기 위해 매장 후기 시스템을 키워드 중심으로 전환하며, 당장은 리뷰 결과가 사용자에게 공개되지 않지만, 축적한 데이터를 3분기 중 가게의 ‘플레이스 페이지’에 반영할 예정이라고 네이버는 설명했다.

네이버는 8천명이 넘는 사용자와 약 1천명의 사업자 의견을 반영해 후기를 남길 수 있는 키워드를 선정했고, 선정된 키워드에는 부정적인 내용이 포함되지 않았기에 비판적인 피드백은 기존의 ‘텍스트 리뷰’를 활용해 남겨야 한다. 앞으로는 사장님에게만 전하는 비공개 리뷰 기능도 추가될 예정이다.

6. 핀테크 준비부족…마이데이터 본격 시행, 연말로 연기 가닥

핀테크 준비부족…마이데이터 본격 시행, 연말로 연기 가닥

당초 금융당국은 8월 초 시행을 목표로 준비했지만 신종 코로나바이러스 감염증(코로나19) 사태로 준비가 부족했다는 핀테크 업체들의 요청을 수용해 연기를 결정했다.

핀테크 업체들은 코로나19 여파로 비대면 IT(정보기술) 개발 수요가 커지면서 개발인력이 부족해졌고, 다양한 통합인증수단을 제공하기로 하면서 마이데이터 시스템 구축에도 추가로 시간이 필요하다고 주장했다.

기본 셋팅

프로그램

Windows 10
-----------------
IntelliJ : 코드작성

Docker - MySQL

MySQL Workbench

Postman

의존성 추가

springboot devtools

lombok

spring data JPA

mysql driver

spring security

spring web

​ OAuth2 client는 직접구현해보기

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

implementation 'org.springframework.boot:spring-boot-starter-data-jpa'
implementation 'org.springframework.boot:spring-boot-starter-security'
implementation 'org.springframework.boot:spring-boot-starter-web'
compileOnly 'org.projectlombok:lombok'
developmentOnly 'org.springframework.boot:spring-boot-devtools'
runtimeOnly 'mysql:mysql-connector-java'
annotationProcessor 'org.projectlombok:lombok'
testImplementation 'org.springframework.boot:spring-boot-starter-test'
testImplementation 'org.springframework.security:spring-security-test'

/** 추가 라이브러리 **/
implementation "org.springframework.security:spring-security-taglibs" // 시큐리티 태그 라이브러리
implementation "org.apache.tomcat.embed:tomcat-embed-jasper" // JSP 템플릿 엔진
implementation 'javax.servlet:jstl' // JSTL

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

1. 올해 상반기 네이버페이 결제금액 17.7조원

올해 상반기 네이버페이 결제금액 17.7조원

모바일 앱 시장 분석 서비스 업체 와이즈앱은 올해 상반기 ‘네이버페이’로 결제된 쇼핑, 콘텐츠 금액이 작년 같은 기간 대비 41% 증가한 액수로 약 17조7000억원이라고 7일 추정해 발표했다.

네이버페이 사용자 수는 지난 6월 한 달 동안 1711만명으로 이들은 월 평균 18만1680원을 결제했으며, 6월 기준 연령별 결제금액 분포는 20대가 17.4%, 30대가 37.5%, 40대가 26.0%였다. 50대 이상은 19.4%였다.

2. ‘초대형IB’ 꿈꾸는 카카오페이…’1조+@’ 쏟아 증권·보험 등 전방위 확장

‘초대형IB’ 꿈꾸는 카카오페이…’1조+@’ 쏟아 증권·보험 등 전방위 확장

7일 금융감독원 전자공시시스템에 따르면 카카오페이는 증권신고서에 “이번 공모자금을 활용해서 자회사 카카오페이증권의 리테일사업 확장을 위한 자본 확충을 가속화할 계획”이라며 “중장기적으로는 프라임 브로커리지 등 IB사업 진출도 목표로 하고 있다”고 밝혔다.

카카오페이는 지난달 금융위원회로부터 디지털 손해보험사 설립 예비허가를 받았고, 이를 기반으로 내년 1분 기중 공식 론칭을 계획하고 있고 현재 기존 보험업계에 몸담고 있는 전문가들을 영입하는 작업이 한창이다.

3. 마블 코믹스 ‘블랙 위도우’ 네이버웹툰으로 나온다

마블 코믹스 ‘블랙 위도우’ 네이버웹툰으로 나온다

이번 작품은 네이버웹툰을 통해 선보이는 ‘마블 웹툰 프로젝트’ 첫번째 시리즈로 마블 코믹스의 원작은 웹툰 형태에 맞게 재창조한 세계 최초의 타이틀이다.

네이버웹툰은 ‘블랙 위도우’를 시작으로 어벤저스, 스파이더맨, 헐크 등 대작들을 9월부터 네이버웹툰과 네이버 시리즈에서 감상할 수 있다.

출처: [백준] 1991번 트리 순회

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

예제 입력 1

1
2
3
4
5
6
7
8

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

예제 출력 1

1
2
3

ABDCEFG
DBAECFG
DBEGFCA

출처

-

알고리즘 분류

• 트리
• 재귀

소스코드

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

import sys

input = sys.stdin.readline

N = int(input())

tree = {}
for _ in range(N):
    root, left, right = input().rstrip().split()
    tree[root] = [left, right]


def preorder(root):
    if root != '.':
        print(root, end='')
        preorder(tree[root][0])
        preorder(tree[root][1])


def inorder(root):
    if root != '.':
        inorder(tree[root][0])
        print(root, end='')
        inorder(tree[root][1])


def postorder(root):
    if root != '.':
        postorder(tree[root][0])
        postorder(tree[root][1])
        print(root, end='')


preorder('A')
print()
inorder('A')
print()
postorder('A')

출처: [Summer/Winter Coding 2018] 스킬트리

문제

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

제한

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 “CBD”로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력

입출력 예 1

• “BACDE”: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
• “CBADF”: 가능한 스킬트리입니다.
• “AECB”: 가능한 스킬트리입니다.
• “BDA”: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

풀이

-

소스코드

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

def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill)

        for s in skills:
            if s in skill:
                if s != skill_list.pop(0):
                    break
        else:
            answer += 1

    return answer

출처: [백준] 2002번 추월

문제

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.

소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.

입력

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이가 적은 차량 번호 목록이 주어진다. 각 차량 번호는 6글자 이상 8글자 이하의 문자열로, 영어 대문자(‘A’-‘Z’)와 숫자(‘0’-‘9’)로만 이루어져 있다.

같은 차량 번호가 두 번 이상 주어지는 경우는 없다.

출력

첫째 줄에 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차가 몇 대인지 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9

4
ZG431SN
ZG5080K
ST123D
ZG206A
ZG206A
ZG431SN
ZG5080K
ST123D

예제 출력 1

1

1

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11

5
ZG508OK
PU305A
RI604B
ZG206A
ZG232ZF
PU305A
ZG232ZF
ZG206A
ZG508OK
RI604B

예제 출력 2

1

3

예제 입력 3

1
2
3
4
5
6
7
8
9
10
11

5
ZG206A
PU234Q
OS945CK
ZG431SN
ZG5962J
ZG5962J
OS945CK
ZG206A
PU234Q
ZG431SN

예제 출력 3

1

2

출처

• Olympiad > Croatian Highschool Competitions in Informatics > 2002 > National Competition #1 - Seniors 1번
  • 빠진 조건을 찾은 사람: kipa00
  • 문제의 오타를 찾은 사람: pppqqqpq

알고리즘 분류

• 구현
• 자료 구조
• 문자열
• 브루트포스 알고리즘
• 해시를 사용한 집합과 맵

소스코드

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())

count = 0
input_car = {}
output_car = []

for i in range(N):
    input_car[input().rstrip()] = i

for i in range(N):
    output_car.append(input().rstrip())

for i in range(N - 1):
    for j in range(i + 1, N):
        if input_car[output_car[i]] > input_car[output_car[j]]:
            count += 1
            break

print(count)