코딩묻은 디자이너

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)

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)

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

문제

생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다.

입력

프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어진다.

출력

주어진 각 종의 이름을 사전순으로 출력하고, 그 종이 차지하는 비율을 백분율로 소수점 4째자리까지 반올림해 함께 출력한다.

풀이

입력 값의 범위가 정해져있지 않기 때문에 while문을 사용해서 계속해서 값을 받고 값이 없을 경우 while문에서 빠져나오도록 하였다.

각 종의 이름을 사전순으로 출력하기 위해 lambda식을 사용하여 정렬하였고,

소수점 4째 자리까지 반올림하기 위해서

print('{:.4f}'.format())형식을 사용했다

python코드

# 생태학
import sys

tree = ''
arr = {}
total = 0

while True:
    tree = sys.stdin.readline().rstrip()
    if not tree:
        break
    if tree in arr:
        arr[tree] += 1
    else:
        arr[tree] = 1
    total += 1
sorted_arr = sorted(arr.items(), key=lambda x:x[0])
for i in range(len(arr)):
    print('{} {:.4f}' .format(sorted_arr[i][0], (sorted_arr[i][1]/total)*100))

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

문제

대열이는 욱제의 친구다.

• “야 백대열을 약분하면 뭔지 알아?”
• “??”
• “십대일이야~ 하하!”

n:m이 주어진다. 욱제를 도와주자. (...)

입력

n과 m이 :을 사이에 두고 주어진다. (1 ≤ n, m ≤ 100,000,000)

출력

두 수를 최대한으로 약분하여 출력한다.

풀이

유클리드 호제법을 사용해서 풀이!

유클리드 호제법:

if a > b:
	while b > 0:
    	a, b = b, a % b

python코드

# 14490 백대열

n, m = map(int,input().split(':'))
a, b = n, m
if n > m:
    while m > 0:
        n, m = m, n % m
    print(a // n, end='')
    print(':', end='')
    print(b // n)
else:
    while n > 0:
        n, m = m % n, n
    print(a//m,end='')
    print(':',end='')
    print(b//m)

똑같은 코드를 두번 반복;;;

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

문제

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.

예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때,  A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.

입력

첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.

출력

첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.

풀이

딕셔너리로 풀었다

일단 리스트 형식으로 받은 후 돌면서 딕셔너리로 변환하였고,

차집합의 갯수만 구하면 되기 때문에 not in으로 만약 다른 집합에 속하지 않는 경우에 cnt를 += 1해서 갯수를 구했다

python 코드

#1269 대칭 차집합

A, B = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
aList = {}
bList = {}
aCnt = 0
bCnt = 0

for i in a:
    aList[i] = '0'
for i in b:
    bList[i] = '0'
for i in a:
    if i not in bList:
        aCnt += 1
for i in b:
    if i not in aList:
        bCnt += 1
print(aCnt + bCnt)

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

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에  ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

출력

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.

풀이

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

1번 수첩 딕셔너리를 만들어두고, 수첩 2 리스트를 받은 후 수첩 1번의 딕셔너리에 있는지 확인해주었다.

python 코드

# 2776 암기왕

T = int(input())
for tc in range(T):
    N = int(input())
    note1 = list(map(int,input().split()))
    note_one = {}
    for i in note1:
        note_one[i] = '1'
    M = int(input())
    note2 = list(map(int,input().split()))
    for i in note2:
        if i in note_one:
            print(1)
        else:
            print(0)

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

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

dfs로 탐색하며 풀이했다.

python코드

# 15651 N과 M (3)
def dfs(n):
    if len(arr) == M:
        print(*arr)
        return
    else:
        for i in range(1,N+1):
            arr.append(i)
            dfs(i)
            arr.pop()
N, M = map(int,input().split())
arr = []
dfs(1)