Coding 공부

import sys


def input():
    return sys.stdin.readline().rstrip()


def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False


T = int(input())


for tc in range(1,T+1):
    N = int(input())
    make_set = [i for i in range(N)]
    ranks = [1 for _ in range(N)]

    for _ in range(int(input())):
        x,y = map(int,input().split())
        union(x,y)
    print(f'Scenario {tc}:')
    for _ in range(int(input())):
        x,y = map(int,input().split())
        if find_parents(x) != find_parents(y):
            print(0)
        else:
            print(1)

    if tc != T:
        print()

전형적인 분리집합 문제였다.

들어오는 입력대로 union을 해주었고, 서로의 부모가 다를시에는 0 같을 시에는 1이 출력되게 했다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()

def pop(queue,flag):
    if flag:
        return queue.pop()
    else:
        return queue.popleft()
T = int(input())

for _ in range(T):
    commands = list(input())
    N = int(input())
    if N:
        arr = deque(input().replace('[','').replace(']','').split(','))
    else:
        input()
        arr = deque()
    # 0 정방향 1 역방향
    flow = 0
    flag = True
    for command in commands:
        if command == 'R':
            flow = (flow+1)%2
        else:
            if arr:
                pop(arr,flow)
            else:
                flag = False
                break
    if flag:
        if flow:
            arr.reverse()
        print(f'[{",".join(arr)}]')
    else:
        print('error')

이 문제는 deque를 통해, 역방향인지 정방향인지에 따라 나눠서 결정을 지으면 되는 문제였다.

정방향인지 역방향인지에 따라 pop을 하는 위치를 바꿔주고, 최종 결과를 출력을 할때에도, 구분을 해줬다.

N = int(input())
arr = [int(input()) for _ in range(N)]
stack = []
result = []
idx = 0
for i in range(1,N+1):
    stack.append(i)
    result.append('+')
    while stack and stack[-1] == arr[idx]:
        stack.pop()
        result.append('-')
        idx += 1

if stack:
    print('NO')
else:
    for i in result:
        print(i)

문제에 주어진대로 1부터 차근차근 숫자가 들어온다. 그리고 문제에 주어진 수열을 만드는 것인데,

스택에 들어간 수 중의 끝부분이 주어진 수열과 동일하면 하나씩 pop을 하면서 수열을 맞춰준다.

이 작업을 전부 했는데도, stack에 수가 남아있는것은 주어진 수열을 못 만드는것이기 때문에,

NO를 출력하고,

stack이 다 비어있으면 만든것이기때문에 push pop을 출력해주면 된다.

1

import sys

input = sys.stdin.readline

def union(A,B):
    X = find_parent(A)
    Y = find_parent(B)
    if X != Y:
        if rank[X] < rank[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if rank[X] == rank[Y]:
            rank[X] += 1

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    else:
        make_set[ind] = find_parent(make_set[ind])
        return make_set[ind]


N,M = map(int,input().split())

make_set = [i for i in range(N+1)]
rank =  [1 for _ in range(N+1)]
for _ in range(M):
    command, A,B = map(int,input().split())

    if command:
        if find_parent(A) == find_parent(B):
            sys.stdout.write('YES\n')
        else:
            sys.stdout.write('NO\n')
    else:
        union(A,B)