풀이 과정

1. 모든 직업군을 탐색하면서 주어진 언어별 선호도와 직업군 언어 점수의 곱셈의 합을 구한다.
   • 만약, 이 합계가 최대값인 경우 갱신 / 직업군 이름 저장
   • 이 과정에서, 직관적으로 계산하기 위해 파이썬 딕셔너리 활용
   • {직업군명 : 점수} 형식으로 저장
2. 계산시, 개발자가 선호하는 언어에는 있지만, 직업군에서 선호하는 언어에 없을수도 있음.
   • 딕셔너리의 get 메서드를 써서 있는지 확인해주어야 한다.
   • 없는 경우에는 계산 생략
3. 동점인 경우에는 사전순으로 앞서는걸 정답으로 해주어야 한다.

소스 코드

def solution(table, languages, preference):
    answer = ''

    score = {languages[i]: preference[i] for i in range(len(languages))}    
    max_score = 0
    for information in table:
        inf = information.split()
        # 언어별 점수 부여
        current_score = {inf[i]: 6-i for i in range(1, len(inf))}
        total_score = 0
        # 현재 직업에서의 점수 구함
        for lan in score.keys():
            if current_score.get(lan) != None:
                total_score += (current_score[lan] * score[lan])

        # 동점이면 사전순으로 앞서는걸 정답으로
        if total_score == max_score:
            if answer > inf[0]:
                answer = inf[0]

        # 최대 점수일때 갱신
        if total_score > max_score:
            max_score = total_score
            answer = inf[0]

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

풀이 과정

1. 높이가 1 이상 100 이하이므로 높이가 0일때부터 100일때까지 각각 안전한 영역의 개수를 구해보면 된다.
   • 두번의 BFS 과정을 거쳐야 한다.
   • 1. 높이 i일때 i 이하의 각각의 영역들을 잠기게 할때 진행
   • 2. 남아있는 영역들을 하나씩 잠기게 하면서 영역의 개수를 세준다.
2. 영역의 개수를 출력해주면 된다.

소스 코드

import sys
import copy
from collections import deque

input = sys.stdin.readline

N = int(input().rstrip())
matrix = [list(map(int, input().rstrip().split())) for _ in range(N)]

def bfs(matrix, point, target):
    queue = deque([[point[0], point[1]]])
    visit = int(10e9)
    length = len(matrix)
    matrix[point[0]][point[1]] = visit
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < length and 0 <= ny and ny < length:
                if matrix[nx][ny] != visit and matrix[nx][ny] <= target:
                    matrix[nx][ny] = visit
                    queue.append([nx, ny])

answer = 0
for i in range(0, 101):
    temp_matrix = copy.deepcopy(matrix)

    # 잠기는 모든 부분 잠기도록 처리
    for j in range(N):
        for k in range(N):
            if temp_matrix[j][k] <= i:
                bfs(temp_matrix, [j, k], i)

    # 안잠긴 부분들 한 영역씩 잠기게 하면서 영역의 수 계산
    area_count = 0
    for j in range(N):
        for k in range(N):
            if temp_matrix[j][k] != int(10e9): 
                # 안잠긴 부분이 있다면 해당 영역 잠기도록
                area_count += 1
                bfs(temp_matrix, [j, k], int(10e9))

    answer = max(area_count, answer)

print(answer)

문제

한글 프로그램의 메뉴에는 총 N개의 옵션이 있다. 각 옵션들은 한 개 또는 여러 개의 단어로 옵션의 기능을 설명하여 놓았다. 그리고 우리는 위에서부터 차례대로 각 옵션에 단축키를 의미하는 대표 알파벳을 지정하기로 하였다. 단축키를 지정하는 법은 아래의 순서를 따른다.

1. 먼저 하나의 옵션에 대해 왼쪽에서부터 오른쪽 순서로 단어의 첫 글자가 이미 단축키로 지정되었는지 살펴본다. 만약 단축키로 아직 지정이 안 되어있다면 그 알파벳을 단축키로 지정한다.
2. 만약 모든 단어의 첫 글자가 이미 지정이 되어있다면 왼쪽에서부터 차례대로 알파벳을 보면서 단축키로 지정 안 된 것이 있다면 단축키로 지정한다.
3. 어떠한 것도 단축키로 지정할 수 없다면 그냥 놔두며 대소문자를 구분치 않는다.
4. 위의 규칙을 첫 번째 옵션부터 N번째 옵션까지 차례대로 적용한다.

입력

첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하의 알파벳으로 표현된다. 단어는 공백 한 칸으로 구분되어져 있다.

출력

N개의 줄에 각 옵션을 출력하는데 단축키로 지정된 알파벳은 좌우에[]괄호를 씌워서 표현한다.

풀이 과정

1. 저장된 알파벳을 넣어둘 set을 하나 만들어 둔다.
2. 각 단어별로 첫글자가 set에 존재하는지 확인
   • 이 때, 대소문자 구분하지 않으므로, 대문자로 모두 치환하여 진행
   • 모든 단어의 첫글자가 set에 존재한다면, 다음 단계로 넘어감.
   • 왼쪽 단어에서부터 진행하면 첫글자가 set에 존재하지 않는다면, 해당 단어를 [첫글자]단어 형태로 바꾸어주고, 첫글자는 set에 저장해준 다음 종료
3. 단어 전체 글자를 왼쪽에서부터 오른쪽으로 진행하면서, set에 존재하는지 확인
   • set에 존재하지 않는다면, 해당 문자를 [문자] 형태로 바꾸어 주고 종료
     • 전체 글자 모두 set에 존재한다면, 그냥 종료

소스 코드

import sys

input = sys.stdin.readline

N = int(input().rstrip())

option_set = set()

for _ in range(N):
    options = input().rstrip('\n').split()

    end = False

    for i in range(len(options)):
        if options[i][0].upper() not in option_set:
            option_set.add(options[i][0].upper())
            options[i] = '[' + options[i][0] + ']' + options[i][1:]
            end = True
            break

    if not end:
        for i in range(len(options)):
            for j in range(len(options[i])):
                if options[i][j].upper() not in option_set:
                    option_set.add(options[i][j].upper())
                    options[i] = options[i][:j] + '[' + options[i][j] + ']' + options[i][j+1:]
                    end = True
                    break
            if end:
                break

    print(*options)

문제 설명

문제

Java 예찬론자 김동규와 C++ 옹호가 김동혁은 서로 어떤 프로그래밍 언어가 최고인지 몇 시간동안 토론을 하곤 했다. 동규는 Java가 명확하고 에러가 적은 프로그램을 만든다고 주장했고, 동혁이는 Java는 프로그램이 느리고, 긴 소스 코드를 갖는 점과 제네릭 배열의 인스턴스화의 무능력을 비웃었다.

또, 김동규와 김동혁은 변수 이름을 짓는 방식도 서로 달랐다. Java에서는 변수의 이름이 여러 단어로 이루어져있을 때, 다음과 같은 방법으로 변수명을 짓는다.

첫 단어는 소문자로 쓰고, 다음 단어부터는 첫 문자만 대문자로 쓴다. 또, 모든 단어는 붙여쓴다. 따라서 Java의 변수명은javaIdentifier,longAndMnemonicIdentifier,name,bAEKJOON과 같은 형태이다.

반면에 C++에서는 변수명에 소문자만 사용한다. 단어와 단어를 구분하기 위해서 밑줄('_')을 이용한다. C++ 변수명은c_identifier,long_and_mnemonic_identifier,name,b_a_e_k_j_o_o_n과 같은 형태이다.

이 둘의 싸움을 부질없다고 느낀 재원이는 C++형식의 변수명을 Java형식의 변수명으로, 또는 그 반대로 바꿔주는 프로그램을 만들려고 한다. 각 언어의 변수명 형식의 위의 설명을 따라야 한다.

재원이의 프로그램은 가장 먼저 변수명을 입력으로 받은 뒤, 이 변수명이 어떤 언어 형식인지를 알아내야 한다. 그 다음, C++형식이라면 Java형식으로, Java형식이라면 C++형식으로 바꾸면 된다. 만약 C++형식과 Java형식 둘 다 아니라면, 에러를 발생시킨다. 변수명을 변환할 때, 단어의 순서는 유지되어야 한다.

재원이는 프로그램을 만들려고 했으나, 너무 귀찮은 나머지 이를 문제를 읽는 사람의 몫으로 맡겨놨다.

재원이가 만들려고 한 프로그램을 대신 만들어보자.

입력

첫째 줄에 변수명이 주어진다. 영어 알파벳과 밑줄('_')로만 이루어져 있고, 길이는 100을 넘지 않는다.

출력

입력으로 주어진 변수명이 Java형식이면, C++형식으로 출력하고, C++형식이라면 Java형식으로 출력한다. 둘 다 아니라면 "Error!"를 출력한다.

풀이 과정

• 와.. 쉬운줄 알았는데 예외처리 할게 생각보다 너무 많아서 소스가 되게 길어짐..
• 예외 처리 많이 생각해보기. 많이 틀렸음..

1. 2가지 과정으로 진행한다.
   • 해당 문자열이 C++ 변수명인지 JAVA 변수명인지 ERROR인지 판별
   • C++이나 JAVA라면 각각 JAVA, C++ 변수명으로로 변환시켜 주기
2. C++/JAVA/ERROR 판별
   • 첫글자가 대문자이거나 _ 가 나오는 경우 에러(Ab , b_ )
   • 마지막 글자에 _ 가 나오는 경우 에러(ab_)
   • ' _ ' 가 중복되어 두번 나오면 에러(ab__cd)
   • 대문자와 _ 가 동시에 나오는 경우 에러
   • 이외의 경우에 대해서
     • _ 가 나온 경우 -> c++
     • 대문자가 나온 경우 -> java
3. 판별이 되었다면 문자열을 바꾸어 준다.
   • _ 의 경우는 해당 문자를 없애고 뒷 문자를 대문자로 (C++ -> Java)
   • 대문자의 경우는 _ 문자 + 소문자로 변환 (Java -> C++)

소스 코드

import sys

def mode_check(s):
    upp_count = 0
    underbar_count = 0
    dup = 0
    dup_flag = False

    if len(s) > 0 and s[0].isupper():
        return 'ERROR'


    if len(s) > 0 and s[0] == '_':
        return 'ERROR'

    if len(s) > 0 and s[-1] == '_':
        return 'ERROR'

    for c in s:
        if c.isupper():
            upp_count += 1
            dup = 0
        elif c == '_':
            underbar_count += 1
            dup += 1
            if dup == 2:
                return 'ERROR'
        else:
            dup = 0

    if upp_count != 0 and underbar_count != 0:
        return 'ERROR'

    if underbar_count > 0:
        return 'C'
    else:
        return 'JAVA'

def convert_java_to_cpp(s):
    cv = ''
    for c in s:
        if ord('A') <= ord(c) and ord(c) <= ord('Z'):
            cv += '_'
            cv += c.lower()
        else:
            cv += c

    return cv

def convert_cpp_to_java(s):
    cv = ''
    upper_flg = False
    for c in s:
        if c == '_':
            upper_flg = True
        else:
            if upper_flg:
                cv += c.upper()
                upper_flg = False
            else:
                cv += c

    return cv

variable_name = sys.stdin.readline().rstrip('\n')
mode = mode_check(variable_name)

if mode == 'JAVA':
    print(convert_java_to_cpp(variable_name))
elif mode == 'C':
    print(convert_cpp_to_java(variable_name))
else:
    print('Error!')

BOJ 4458, 첫 글자 대문자 만들기

바로가기

소스 코드

• 문자열의 길이가 0일 때 유의

import sys

input = sys.stdin.readline
n = int(input().rstrip())


for _ in range(n):
    k = input().rstrip('\n')
    if len(k) > 0:
        upper = k[0].upper()
        k = upper + k[1:]
        print(k)
    else:
        print('')

BOJ 1357, 뒤집힌 덧셈

바로가기

소스 코드

• rev 함수를 정의(자리수 역순으로 바꾸어주는 함수) ex) 123 -> 321
• 이후 두 입력값에 대해 rev 함수 적용 후 합계에 대해서도 rev 함수 적용

import sys

input = sys.stdin.readline

def rev(x):
    convert = ''
    while x > 0:
        convert += str(x % 10)
        x //= 10

    return int(convert)

X, Y = map(int, input().rstrip().split())
answer = rev(rev(X) + rev(Y))
print(answer)

문제 설명

문제

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

풀이 과정

• 다익스트라 알고리즘을 다르게 적용하여서 풀이함.
  • 최소 비용 -> 최대 비용

1. 기본적으로 다익스트라 알고리즘 사용

   • 연결된 노드들 중에서 중량이 최댓값인 노드 선택
   • 해당 노드에 연결된 인접 노드들의 중량 갱신 / 히프에 추가

2. 기존에는 그냥 deque를 사용하였으나.. 시간 초과 문제가 생김.

   • 최대 히프 사용하여 중량이 가장 큰 노드부터 방문
   • 이미 갱신된 경우, 생략하는 과정 추가

3. 목표 지점의 중량 출력

소스 코드

import sys
from collections import deque
import heapq

input = sys.stdin.readline
N, M = map(int, input().rstrip().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b, weight = map(int, input().rstrip().split())
    graph[a].append([b, weight])
    graph[b].append([a, weight])

start, end = map(int, input().rstrip().split())

INT_MAX = int(10e9)
distance = [0] * (N+1)
heap = [[-INT_MAX, start]]
distance[start] = INT_MAX

while heap:
    cost, node = heapq.heappop(heap)
    cost = -cost

    # 이미 갱신된 경우라면 생략
    if distance[node] > cost:
        continue

    for next_node, next_cost in graph[node]:
        new_cost = min(cost, next_cost)
        # 기존 무게보다 현재 거쳤을때의 무게가 더 크다면 갱신
        if distance[next_node] < new_cost:
            distance[next_node] = new_cost
            heapq.heappush(heap, [-new_cost, next_node])

print(distance[end])

문제 설명

You are given an array of k linked-listslists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input:

• lists = [[1,4,5],[1,3,4],[2,6]]

Output:

• [1,1,2,3,4,4,5,6]

Explanation:

• The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6

Example 2:

Input:

• lists = []

Output:

• []

Example 3:

Input:

• lists = [[]]

Output:

• []

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i]is sorted inascending order.
• The sum oflists[i].lengthwon't exceed10^4.

풀이 과정

• 문제는 k개의 linked-list가 주어질때, 모든 linked-list를 통합하여 하나의 리스트로 만듬(오름차순으로)

1. 리스트의 모든 요소들을 최소 히프에 넣는다
   • 히프의 특성에 의해 나중에 히프에서 빼줄때 정렬되어서 나올 예정
2. 히프에서 요소를 하나씩 꺼내서, 연결 그래프의 노드로 만들어준 다음 연결 그래프의 맨 마지막 노드의 링크에 넣어준다.
   • linked list 구성하기 위해 루트는 따로 저장해 두고, 맨 마지막을 가리키는 변수 따로 지정
3. 루트 노드를 리턴해주면 된다.

소스 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        answer = []

        for l in lists:
            temp = l
            while temp != None:
                heapq.heappush(heap, temp.val)
                temp = temp.next

        root = ListNode()
        prev = root

        while heap:
            t = heapq.heappop(heap)
            temp = ListNode(val=t, next=None)
            prev.next = temp
            prev = temp

        root = root.next

        return root

풀이 과정

1. 열별로 진행한다.
   • 최저점인 행, 최고점인 행, 최저점인 인원 수, 최고점인 인원 수를 구한다.
2. 평균 계산
   • 최저점이거나 최고점인 행이 현재 진행중인 열과 같고(자기 자신이 낸 점수)
   • 유일한 인원인지 검사 필요 !! ( 최고점/최저점 인원수가 1인지 )
   • 해당 점수는 빼주고, 인원수도 1 줄여준다.
   • 이후, 평균을 계산하고 평균에 따라 학점을 매겨주면 된다.

• 구현 문제는 너무 복잡한거 같다..

소스 코드

def solution(scores):
    answer = ''
    for j in range(len(scores[0])):
        min_idx = 0
        max_idx = 0
        min_count = 1
        max_count = 1
        score_sum = scores[0][j]
        for i in range(1, len(scores)):
            # 최저점인지 검사
            if scores[i][j] <= scores[min_idx][j]:
                # 최저점이면서 동일한 점수가 있다면 인원수 증가
                if scores[i][j] == scores[min_idx][j]:
                    min_idx = i if i == j else min_idx
                    min_count += 1
                else:
                    min_idx = i
                    min_count = 1

            # 최고점인지 검사
            if scores[i][j] >= scores[max_idx][j]:
                # 최고점이면서 동일한 점수가 있다면 인원수 증가
                if scores[i][j] == scores[max_idx][j]:
                    max_idx = i if i == j else max_idx
                    max_count += 1
                else:
                    max_idx = i
                    max_count = 1

            score_sum += scores[i][j]

        # 점수 계산 파트( 자기가 낸 점수가 유일한 최고점, 최저점이라면 빼고 계산 )
        total_student = len(scores)
        if (min_idx == j and min_count == 1) or (max_idx == j and max_count == 1):
            p = min_idx if min_idx == j else max_idx
            total_student -= 1
            score_sum -= scores[p][j]

        avg = score_sum / total_student

        if avg >= 90: answer += 'A'
        elif avg >= 80: answer += 'B'
        elif avg >= 70: answer += 'C'
        elif avg >= 50: answer += 'D'
        else: answer += 'F'

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

• 문자열의 길이가 최대 50글자까지밖에 되지 않으므로..
  • zero ~ nine까지 모든 문자열이 전체 문자열 s에 있는지 검사
  • 있다면, 해당 문자열을 replace 해주면 된다.

소스 코드

def solution(s):
    string_dict = {'zero': 0, 'one': 1, 'two': 2, 'three': 3,
                  'four': 4, 'five': 5, 'six': 6, 'seven': 7,
                  'eight': 8, 'nine': 9}    
    answer = 0
    for string in string_dict.keys():
        if string in s:
            s = s.replace(string, str(string_dict[string]))
    answer = int(s)
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

풀이 과정

1. 이전에 나타나지 않은 인원의 경우 딕셔너리에 넣어준다.
   • 딕셔너리에 넣어주면서 parent 설정, 인원수 1명(자기 자신) 설정
2. 입력받은 두명의 그룹을 합친다.
   • 이 때, 두명이 속한 그룹의 인원수도 같이 합쳐주어야 함.
   • 인원수를 따로 구하려고 하면 시간 초과가 나온다.
3. 매 과정마다 그룹 내의 인원수를 출력해준다.

• 처음에는 인원수를 따로 for문으로 구하려고 했는데 시간초과가 나옴..
• 처음 시간초과가 났을 때는 차라리 set을 사용해서 구현하는 것이 더 편할거 같았으나..
  Union-Find로 통과받아보고 싶어서 매달림,,

소스 코드

import sys
input = sys.stdin.readline

total_case = int(input().rstrip())

def find(parent, group, a):
    if parent[a] != a:
        parent[a] = find(parent, group, parent[a])
        group[a] = group[parent[a]]
    return parent[a]

def union(parent, group, a, b):
    p1 = find(parent, group, a)
    p2 = find(parent, group, b)
    if p1 < p2:
        parent[p2] = p1
    else:
        parent[p1] = p2

for i in range(total_case):
    F = int(input().rstrip())
    member = dict()
    count = 0
    parent = [-1] * 200001
    group = [0] * 200001
    for _ in range(F):
        person1, person2 = input().rstrip().split()

        # 새로운 멤버 추가
        if member.get(person1) == None:
            parent[count] = count
            member[person1] = count
            group[count] = 1
            count += 1
        if member.get(person2) == None:
            parent[count] = count
            member[person2] = count
            group[count] = 1
            count += 1

        # 두 그룹 합침
        par1 = find(parent, group, member[person1])
        par2 = find(parent, group, member[person2])
        if par1 != par2:
            union(parent, group, par1, par2)
            # 그룹 인원수 합침
            temp = group[par1] + group[par2]
            group[par1] = temp
            group[par2] = temp

        # 위 과정에서는 부모의 그룹 인원수만 바뀌므로   
        # find 한번 더 호출해서 자식들의 그룹 멤버 수가 부모의 그룹 인원수가 되도록 조정
        find(parent, group, member[person1])
        find(parent, group, member[person2])

        group_count = group[member[person1]]
        print(group_count)