코딩묻은 디자이너

https://www.acmicpc.net/problem/3003

문제

동혁이는 오래된 창고를 뒤지다가 낡은 체스판과 피스를 발견했다.

체스판의 먼지를 털어내고 걸레로 닦으니 그럭저럭 쓸만한 체스판이 되었다. 하지만, 검정색 피스는 모두 있었으나, 흰색 피스는 개수가 올바르지 않았다.

체스는 총 16개의 피스를 사용하며, 킹 1개, 퀸 1개, 룩 2개, 비숍 2개, 나이트 2개, 폰 8개로 구성되어 있다.

동혁이가 발견한 흰색 피스의 개수가 주어졌을 때, 몇 개를 더하거나 빼야 올바른 세트가 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 동혁이가 찾은 흰색 킹, 퀸, 룩, 비숍, 나이트, 폰의 개수가 주어진다. 이 값은 0보다 크거나 같고 10보다 작거나 같은 정수이다.

출력

첫째 줄에 입력에서 주어진 순서대로 몇 개의 피스를 더하거나 빼야 되는지를 출력한다. 만약 수가 양수라면 동혁이는 그 개수 만큼 피스를 더해야 하는 것이고, 음수라면 제거해야 하는 것이다.

풀이

자신감 키우는 날~!

list로 받아서 인덱스 순서대로 접근했다.

개수가 정해져 있기 때문에 그 갯수에서 인덱스에 해당하는 것을 뺐다!

python코드

#3003 킹, 퀸, 룩, 비숍, 나이트, 폰

chess = list(map(int,input().split()))

print(1-chess[0], 1-chess[1], 2-chess[2], 2-chess[3], 2-chess[4], 8-chess[5])

https://www.acmicpc.net/problem/11722

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

풀이

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4

동적 계획법으로 풀어내는 문제

python 코드

#11722 가장 긴 감소하는 부분 수열

N = int(input())
arr = list(map(int,input().split()))

dp = [1] * N

for i in range(1,N):
    for j in range(0,i):
        if arr[i] < arr[j]:
            dp[i] = max(dp[i], dp[j]+1)
ans = max(dp)
print(ans)

https://www.acmicpc.net/problem/1991

문제

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

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

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

가 된다.

입력

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

출력

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

풀이

트리 문제를 풀 때 가장 고민이 저것을 어떻게 코드로 표현하느냐 인데

노드의 연결상태를 이런식으로 생각하니깐 쉬웠다!

형태는

[A,B,C]

[B,D,.]

.

.

.

이런 식으로 표현해서 0번 인덱스 1번 인덱스, 2번 인덱스로 접근했다

전위 순회 규칙을 찾아내면 중위와 후위는 비슷하게 풀이할 수 있다

python 코드

# 1991 트리 순회
def preorder(n):
    print(arr[n][0],end='')
    if arr[n][1] != '.':
        for i in range(len(arr)):
            if arr[i][0] == arr[n][1]:
                preorder(i)
    if arr[n][2] != '.':
        for i in range(len(arr)):
            if arr[i][0] == arr[n][2]:
                preorder(i)
def inorder(n):
    if arr[n][1] != '.':
        for i in range(len(arr)):
            if arr[i][0] == arr[n][1]:
                inorder(i)
    print(arr[n][0],end='')
    if arr[n][2] != '.':
        for i in range(len(arr)):
            if(arr[i][0]) == arr[n][2]:
                inorder(i)
def postorder(n):
    if arr[n][1] != '.':
        for i in range(len(arr)):
            if arr[i][0] == arr[n][1]:
                postorder(i)
    if arr[n][2] != '.':
        for i in range(len(arr)):
            if(arr[i][0]) == arr[n][2]:
                postorder(i)
    print(arr[n][0],end='')

N = int(input())
arr = []

for t in range(N):
    arr.append(list(map(str,input().split())))

preorder(0)
print()
inorder(0)
print()
postorder(0)

오류상황

eslint를 사용할 때 나타는 오류로

eslint 상에서는 이렇게 빈 div를 사용할 수 없다

해결방법

<div /> 로 닫는 /를 넣어주었다! 생각보다 간단하게 해결;;;

https://www.acmicpc.net/problem/11724

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

풀이

연결요소를 구해야 하는 문제인데 처음에는 연결요소가 뭘 출력하라는건지 헷갈렸는데

뭉쳐진 덩어리의 갯수를 구하는 문제였다.

더이상 연결된 요소가 없을 때 까지 탐색해야 하므로 dfs 깊이 탐색을 사용했다.

연결관계를 나타낼 리스트 arr과 방문 여부를 체크할 visited 리스트를 만들었다

입력을 받을 때 방향이 없는 그래프라서

arr[u].append(v)
arr[v].append(u)

양방향으로 입력했다.

재귀를 돌면서 만약 방문 했을 경우 visited에 1을 입력하고, 방문하지 않은 경로만 이동한다

dfs를 완료한것은 더이상 탐색할 노드가 없다는 뜻이니 ans += 1을 했다

python코드

# 11724 연결 요소의 개수
import sys
sys.setrecursionlimit(10**6)

def dfs(n):
    for i in range(len(arr[n])):
        if visited[arr[n][i]] == 0:
            visited[arr[n][i]] = 1
            dfs(arr[n][i])

N, M = map(int,input().split())
arr = [[] * (N+1) for _ in range(N+1)]
visited = [0] * (N+1)
ans = 0
for m in range(M):
    u,v = map(int,sys.stdin.readline().rstrip().split())
    arr[u].append(v)
    arr[v].append(u)

for i in range(1, N+1):
    if visited[i] == 0:
        visited[i] = 1
        dfs(i)
        ans += 1
print(ans)

https://www.acmicpc.net/problem/11656

문제

접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.

baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.

문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다.

출력

첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

풀이

처음에는 재귀를 통해 풀었는데 RecursionError가 나와서 그냥 단순 for문을 통해 풀이하도록 바꿨다

슬라이싱을 통해 문자열값의 범위를 지정해서 받아와 배열에 저장한 후 sort로 정렬하였다

python코드

# 11656 점미사 배열

text = input()
arr = []

for i in range(len(text)):
    arr.append(text[i:len(text)])

arr.sort()
for i in arr:
    print(i)

python 재귀 제한 해제

import sys
sys.setrecursionlimit(10**6)

https://www.acmicpc.net/problem/19583

문제

보영이는 알고리즘 동아리 HI-ARC를 운영하고 있다.

보영이와 운영진 일동은 20년도에 입학하는 신입생들을 맞이하기 위해 열심히 준비를 해왔으나, 전염병의 유행이 악화된 나머지 정부에서는 “사회적 거리두기”를 선언했고 그에 따라 학교에서는 교내 모든 동아리에 오프라인 모임을 자제하라는 공지를 하기에 이르렀다. 오프라인에서 모임을 자제하라는 권고가 나온 어려운 상황에도 불구하고, 보영이는 기지를 발휘하여 개강총회를 미튜브 스트리밍으로 대체하는 결정을 하게 된다.

하지만, 미튜브 스트리밍으로 개강총회를 하게 될 경우, 아래와 같은 문제가 있었다.

1. 누가 개강총회에 왔는지 알 수 없다.
2. 누가 개강총회 자리에 끝까지 남아있었는지 알 수 없다.
3. 어떤 사람이 개강총회 스트리밍을 단순히 틀어놓기만 했는지 알 수 없다.

이런 문제를 해결하기 위해서, 다음과 같이 출석부를 관리하기로 결심했다.

1. 개강총회를 시작하기 전에, 학회원의 입장 확인 여부를 확인한다. 학회원의 입장 여부는 개강총회가 시작한 시간 이전에 대화를 한 적이 있는 학회원의 닉네임을 보고 체크한다. 개강총회를 시작하자마자 채팅 기록을 남긴 학회원도 제 시간에 입장이 확인된 것으로 간주한다.
2. 개강총회를 끝내고 나서, 스트리밍을 끝낼 때까지 학회원의 퇴장 확인 여부를 확인한다. 학회원의 퇴장 여부는 개강총회가 끝나고 스트리밍이 끝날 때까지 대화를 한 적이 있는 학회원의 닉네임을 보고 체크한다. 개강총회가 끝나자마자 채팅 기록을 남겼거나, 개강총회 스트리밍이 끝나자마자 채팅 기록을 남긴 학회원도 제 시간에 퇴장이 확인된 것으로 간주한다.  

단, 00:00부터는 개강총회를 시작하기 전의 대기 시간이며, 개강총회 스트리밍 끝난 시간 이후로 남겨져 있는 채팅 기록은 다른 스트리밍 영상의 채팅 기록으로 간주한다.

이 때, 입장부터 퇴장까지 모두 확인된 학회원은 전부 몇 명인가?

입력

첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤ 23:59)
각 시간은 HH:MM의 형식으로 주어진다.

두번째 줄부터는 HI-ARC에서 방송하는 스트리밍 영상의 채팅 기록들이 시간순으로 주어지는데, (시간) (학회원 닉네임)의 형태로 주어진다. 학회원의 닉네임은 알파벳 대소문자와 숫자, 그리고 특수 기호(., _, -)로만 구성된 문자열이며 최대 20글자이다.

모든 채팅 기록은 개강총회가 일어난 날에 발생한 채팅 기록이다. 즉 00:00~23:59의 시간만 주어진다. 채팅 기록은 10만 줄을 넘지 않는다.

출력

출석이 확인된 학회원의 인원 수를 출력한다.

풀이

입력의 길이가 정해지지 않아서 처음에는

if not 입력 을 사용해서 풀이하려고 했는데 값을 2개 받는거다보니 map 에서 인자가 두개가 아니라고 오류를 내보냈다.

오류가 입력을 받기도 전에 나버려서 그냥 try except문을 사용해서 오류가 나면 except문에서 break를 하도록 만들었다!

python코드

# 19583 싸이버개강총회
import sys
S,E,Q = map(str,sys.stdin.readline().rstrip().split())
s = {}
q = {}
attend = {}
cnt = 0

while True:
    try:
        talk, nickname = map(str, sys.stdin.readline().rstrip().split())
        if talk <= S:
            s[nickname] = '1'
        elif talk >= E and talk <= Q:
            q[nickname] = '1'
    except:
        break

for i in q:
    if i in s:
        cnt += 1
# print(s,q)
print(cnt)

https://www.acmicpc.net/problem/16165

문제

정우는 소문난 걸그룹 덕후이다. 정우의 친구 준석이도 걸그룹을 좋아하지만 이름을 잘 외우지 못한다는 문제가 있었다. 정우는 친구를 위해 걸그룹 개인과 팀의 이름을 검색하여 외우게 하는 퀴즈 프로그램을 만들고자 한다.

입력

첫 번째 줄에는 총 입력 받을 걸그룹의 수 N(0 < N < 100)과 맞혀야 할 문제의 수 M(0 < M < 100)을 입력받는다.

두 번째 줄부터는 각 걸그룹마다 팀의 이름, 걸그룹의 인원 수, 멤버의 이름을 한 줄씩 차례대로 입력받는다. 팀과 멤버의 이름은 최대 100글자이며, 모든 글자는 알파벳 소문자이다. 하나의 걸그룹이나 서로 다른 두 걸그룹에 이름이 같은 두 멤버가 있는 경우는 없다.

그 다음 줄부터는 M개의 퀴즈를 입력받는다. 각각의 퀴즈는 두 줄로 이루어져 있으며, 팀의 이름이나 멤버의 이름이 첫 줄에 주어지고 퀴즈의 종류를 나타내는 0 또는 1이 두 번째 줄에 주어진다. 퀴즈의 종류가 0일 경우 팀의 이름이 주어지며, 1일 경우 멤버의 이름이 주어진다.

출력

첫 번째 줄부터 차례대로 퀴즈에 대한 답을 출력한다. 퀴즈의 종류가 0일 경우 해당 팀에 속한 멤버의 이름을 사전순으로 한 줄에 한 명씩 출력한다. 퀴즈의 종류가 1일 경우 해당 멤버가 속한 팀의 이름을 출력한다.

풀이

그룹명으로 멤버 '리스트'를 구하는 딕셔너리 하나, 멤버 이름으로 그룹명을 구하는 딕셔너리 하나 총 두개의 딕셔너리를 만들었다.

걸그룹명으로 멤버 리스트르 구하는 딕셔너리에서는 그룹명을 받은 후 멤버는 리스트로 받아왔다

python코드

# 16165 걸그룹 마스터 준석이
import sys

N, M = map(int,sys.stdin.readline().rstrip().split())
g_m={}
m_g={}
for n in range(N):
    group = input()
    num = int(input())
    g_m[group] = []
    for i in range(num):
        member = input()
        g_m[group].append(member)
        m_g[member] = group

for m in range(M):
    text = sys.stdin.readline().rstrip()
    game = int(sys.stdin.readline().rstrip())
    if game == 1:
        print(m_g[text])
    else:
        g_m[text].sort()
        for i in g_m[text]:
            print(i)

https://www.acmicpc.net/problem/2002

문제

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

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

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

입력

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

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

출력

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

풀이

해시(딕셔너리)를 통해 풀었다

처음에는 하나하나 돌아가면서 현제 인덱스를 비교하고 만약 인덱스 값이 다르다면 인덱스에서 하나 뺀 값을 계산하여(?) 풀려고 하였으나 아예 근본부터 틀린 로직이라는걸 파악하고(여기까지 한시간)

그냥 간단하게 딕셔너리 가장 앞에 있는 값과 현재 값이 다르다면 추월한 차 이므로 ans에 1추가하는 간단한 방법을 사용했다.

딕셔너리의 가장 앞에 있는 값을 찾기 위해

next(iter(dict))를 사용하였다

python코드

# 2002 추월
import sys

n = int(sys.stdin.readline().rstrip())
ans = 0
arr = {}
for i in range(n):
    arr[sys.stdin.readline().rstrip()] = i
for i in range(n):
    car = input()
    if next(iter(arr)) != car:
        ans += 1
    arr.pop(car)
print(ans)