Coding 공부

이 문제는 데이터 수정이 있기 전까지 안 풀기 를 권장합니다.

이 문제를 푸실분들은 https://www.acmicpc.net/board/view/69371 이 글을 참조하거나

밑의 input을 받는 방식으로 받기를 권장합니다.

import sys
from itertools import product
def input():
    return sys.stdin.readline().rstrip()

def dfs(first_num,idx,total):
    global result
    if idx == line_cnt[1]:
        str_total = str(total)
        str_set = set(str_total)
        if len(str_total) == line_cnt[idx+2] and not (str_set-total_num):
            result += 1
    else:
        for k in int_total_num:
            temp = k*first_num
            str_temp = str(temp)
            str_set = set(str_temp)
            if len(str_temp) == line_cnt[idx+2] and not (str_set-total_num):
                number_of_digit = 10**idx
                temp_num = temp * number_of_digit
                dfs(first_num,idx+1,total+temp_num)


N = int(input())
list_ = input().split()

K = input()
list__ = input().split()

if len(K) == 0:
    K = int(list_[N])
    list__ = list_[N + 1 : ]
    list_  = list_[ : N]
else:
    K = int(K)
line_cnt = list(map(int,list_))
number_list = list__[:]
total_num = set(number_list)
int_total_num = set(map(int,number_list))
result = 0
for num_line1 in product(number_list,repeat=line_cnt[0]):
    first_line_num = int(''.join(num_line1))
    dfs(first_line_num,0,0)


print(result)

이 문제의 아이디어 자체는 그리 어렵지 않다.

모든 것을 다 구해보면 된다.

하다가, 안되는 경우가 발생하면 되돌아가서 새로운 걸 하면 된다.

저같은 경우엔 첫줄의 숫자는 product를 이용해 구했다.

그리고 두번째 숫자부터는 직접 중복순열을 해주면서, 중간에 모든 조건을 만족해야지만, 그 다음 조건으로 갈 수 있게 해주었다.

그리고 주어진 숫자가 있는지 없는지는 차집합을 통해 길이가 0이면 전부 있는것이므로, 길이가 0인경우에만 통과시켜줬다.

import sys


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

def choose_1(idx,val):
    global K
    if idx == line_cnt[0]:
        choose_2(0,0,val)
        return
    else:
        for i in range(K):
            choose_1(idx+1,val*10+number_list[i])
def check_length(val):
    val = str(val)
    return len(val)
def check_number(val):
    while val:
        if not number_visit[val%10]:
            return False
        val = val//10
    return True

def choose_2(idx,val,first_num):
    global K,result
    if idx == line_cnt[1]:
        last_num = first_num * val
        if check_length(last_num) == line_cnt[-1] and check_number(last_num):
            result += 1
        return
    else:
        for i in range(K):
            if check_length(first_num*number_list[i]) == line_cnt[idx+2] and check_number(first_num*number_list[i]):
                choose_2(idx+1,val*10+number_list[i],first_num)

N = int(input())
list_ = input().split()

K = input()
list__ = input().split()

if len(K) == 0:
    K = int(list_[N])
    list__ = list_[N + 1 : ]
    list_  = list_[ : N]
else:
    K = int(K)
result = 0
line_cnt = list(map(int,list_))
number_list = list(map(int,list__))
number_visit = [False for _ in range(10)]

for num in number_list:
    number_visit[num] = True


choose_1(0,0)

print(result)

이 방식은 좀 더 깔끔한 방식인것같다.

여기는 나머지를 이용해서 각 자리수를 구하고, 그때 숫자가 있는지 없는지는 리스트의 방문표시로 해주었다.

길이는 문자열로 바꾼뒤 그 길이를 구해주었다.

이 방식이 좀 더 깔끔한 코드라 생각한다.

import sys
from collections import deque,defaultdict
input = sys.stdin.readline
# 강의 근원 노드의 순서는 1이다.

T = int(input())

for _ in range(T):
    K,M,P = map(int,input().split())
    # K case의 번호
    # M은 노드의 수
    # P는 간선의 수

    strahelr_dict = [defaultdict(int) for _ in range(M+1)]
    strahelr_list = [-1 for _ in range(M+1)]
    graph = [[] for _ in range(M+1)]
    indegree_list = [0 for _ in range(M+1)]
    for _ in range(P):
        x,y = map(int,input().split())
        graph[x].append(y)
        indegree_list[y] += 1
    stack = deque()
    for i in range(1,M+1):
        if not indegree_list[i]:
            stack.append(i)
            strahelr_list[i] = 1
    
    while stack:

        node = stack.popleft()
        cur_strahler = strahelr_list[node]
        for next_node in graph[node]:
            indegree_list[next_node] -= 1
            strahelr_dict[next_node][cur_strahler] += 1
            if not indegree_list[next_node]:
                stack.append(next_node)
                next_strahelr = max(strahelr_dict[next_node].keys())
                if strahelr_dict[next_node][next_strahelr] > 1:
                    strahelr_list[next_node] = next_strahelr + 1
                else:
                    strahelr_list[next_node] = next_strahelr



    print(K,strahelr_list[M])

 이 문제에서 주의해야할 점은,  마지막에 출력해야할 TEST CASE의 값이 T가 아니라, K인걸 주의해야한다.

처음은 위상정렬을 해주는 것과 동일하게 indegree와 graph를 그려준다.

가장 처음에 출발하는 node들의 strahler의 값을 1로 초기화를 해준다.

위상정렬을 해주면서, 방문하는 노드들에 해당 cur_strahler의 개수를 세줍니다.

그러면서 indegree가 0이 되었을때, 최대값을 찾고, 그 개수가 2개 이상이면, 최대값보다 1을 더해서 저장시켜줬습니다.

위와 같이 한뒤에 나머지는 일반적인 위상정렬을 구하면 되는 문제였습니다.

# 42_jakang님 풀이
import sys
input = sys.stdin.readline


def tree_dp(cur_node):

    if not len(graph[cur_node]):
        strahler_list[cur_node] = 1
        return
    else:
        max_st_cnt = 0
        for parent_node in graph[cur_node]:
            tree_dp(parent_node)

            if strahler_list[cur_node] < strahler_list[parent_node]:
                strahler_list[cur_node] = strahler_list[parent_node]
                max_st_cnt = 1
            elif strahler_list[cur_node] == strahler_list[parent_node]:
                max_st_cnt += 1
        if max_st_cnt > 1:
            strahler_list[cur_node] += 1
T = int(input())

for _ in range(T):
    K,M,P = map(int,input().split())
    strahler_list = [0 for _ in range(M+1)]
    graph = [[] for _ in range(M+1)]

    for _ in range(P):
        x,y = map(int,input().split())
        graph[y].append(x)

    

    tree_dp(M)
    print(K,strahler_list[M])
    

 이 풀이는 42_jakang님의 풀이를 공부하면서 한것이었고, 이 풀이 방식은 다음과 같습니다.

어차피 가장 끝노드 M은 고정되어있으므로, 가장 끝 노드에서부터 하나하나씩 부모를 찾아 들어가봅니다.

그리고 부모노드의 strahler_list가 현재노드보다 크면 갱신을 해주고, 그 큰값들의 개수를 세줍니다.

만약에 그 개수가 2개 이상이면, 현재노드의 shrahler의 값을 키워줍니다.

이런 방식을 이용해서도 문제를 풀 수 있습니다.

import sys

input = sys.stdin.readline


while True:
    N,*arr = list(map(int,input().split()))

    if N == 0:
        break

    stack = [0]
    arr = [0] + arr[:] +[0]
    result = 0
    for ind in range(1,len(arr)):
        while stack and arr[ind] < arr[stack[-1]]:
            height = arr[stack[-1]]
            stack.pop()
            width = ind - stack[-1]-1
            result = max(result,height*width)
        stack.append(ind)

    print(result)

 이 문제는 boj.kr/11873 의 하위호환이다.

11873의 문제를 푼것과 같이 stack에 현재위 index 즉 가로길이를 넣어주는 걸 한다.

그리고 이걸 좀 더 쉽게 구하기 위해, 양 끝에 [0]을 추가를 해준다.

그러면 스택에서 마지막 값에 위치한 높이보다 작은 높이가 들어오면,

그때 스택에서 값을 추출해서, 지금까지의 거리를 측정을 해준다.

측정 방식은 현재 index에서 stack의 마지막값을 빼준 값에 -1을 해준것이다.

이렇게 2개의 값을 곱한뒤 최대값을 저장해주면 된다. 

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())


for tc in range(T):
    N = int(input())
    graph = [[0 for _ in range(N+1)] for _ in range(N+1)]
    # 전년도 1등부터 ~ N등까지 팀 순서
    prev_order_team = list(map(int,input().split()))
    indegree = [0]*(N+1)
    indegree[0] = float('inf')
    for rank,team_num in enumerate(prev_order_team):
        indegree[team_num] = rank
        for low_team_num in prev_order_team[rank+1:]:
            graph[team_num][low_team_num] = 1

    M = int(input())
    new_indegree = indegree[:]
    for _ in range(M):
        a_team,b_team = map(int,input().split())
        if indegree[a_team] > indegree[b_team]:
            a_team,b_team = b_team,a_team

        # a_team이 상위권 b_team이 하위권 원래는
        graph[b_team][a_team] = 1
        graph[a_team][b_team] = 0
        new_indegree[a_team] += 1
        new_indegree[b_team] -= 1
    indegree = new_indegree[:]
    stack = deque()

    for team_num in range(1,N+1):
        if not indegree[team_num]:
            stack.append(team_num)
    result = []
    if len(stack) == 1:
        cnt = 0
        while cnt<N:
            if not len(stack):
                result = 'IMPOSSIBLE'
                break
            elif len(stack) > 1:
                result = '?'
                break

            cur_node = stack.popleft()
            result.append(cur_node)
            for next_node in range(1,N+1):
                if graph[cur_node][next_node]:
                    indegree[next_node] -= 1
                    if not indegree[next_node]:
                        stack.append(next_node)
            cnt += 1
    elif len(stack) == 0:
        result = 'IMPOSSIBLE'
    else:
        result = '?'
    if type(result) == list:
        print(*result)
    else:
        print(result)

이 문제는 최근에 풀었던 문제 중에서 문제를 이해하는데 가장 힘들었던 문제였다. 문제를 이해하고 보면,

쉽게 이해가 가능한 문제이다.

문제에 주어진 N개의 숫자는

앞에서부터 1등부터 N등까지를 표현한 것이다.

그리고 그 각 자리에 있는것이 1등을 한 팀 N_1  2등을 한 팀 N_2 이런식인것이다.

그러면 문제에 첫 예제로 주어진

5 4 3 2 1

1등은 5팀

2등은 4팀

3등은 3팀

4등은 2팀

5등은 1팀

이 된것이다. 그렇다는 것은 이걸 그래프적으로 표현을 하면 다음과 같다.

 다음 과 같이 표현을 할 수 있을 것이다.

5팀이 가장 루트 노드이고, 이 5팀을 지나가고 난뒤에 4팀 3팀 2팀 1팀을 순서적으로 할 수 있는것이다.

그러면 여기서 상대적인 등수가 바뀌었다는 것은

저 그래프에서의 순서가 뒤바뀐다는 것을 의미하게 된다.

그러면 첫번째 예제에선

2 4

3 4 라는 입력이 주어졌다.

그러면

빨갛게 동그라미 모양이 된 화살표가 반대로 가게 되는것이다.

즉 녹색화살표 처럼 반대로 표시가 바뀌게 된것이다.

그러면 이때의 순위는

5 -> 3->2->4->1 순서가 되는 것을 알 수 있다.

그래서 이 문제에서 중요한 것은

처음 입력이 주어졌을때 자기 등수보다 이하의 등수들에게 부모 자식 관계를 나타내느 그래프 간선을 그려준다.

그리고 난뒤에 m개의 상대적인 순위가 바뀌었다는 입력이 들어오면

서로원래의 rank를 확인해서

높은 랭크 -> 낮은 랭크로 연결되어있던 간선을 반대로 바꾸어주고,

우리가 간선을 들어온 개수를 세어놓은 indegree 수치를

낮은 순위는 1개를 줄여주고, 높은 순위는 1개를 높여주면 된다.

그리고 여기서 주의해야할 것은 바로 값을 바꾸면 바뀐 순위를 참조가 가능하므로,

복사된 배열에서 값을 변경시키고 나중에 옮겨줘야한다.

그리고 정상적인 위상정렬을 시행해주면 된다.

만약에 스택이 비게되면 사이클이 발생한 것이므로,  impossible을

스택에 길이가 2개이상이 된다는것은 같은 rank에 2개가 있게 되는 것이므로, ?를 출력하게 해주면 된다.

import sys

input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())

    prev_rank = [0]*(N+1)
    current_rank = [0]*(N+1)
    arr = list(map(int,input().split()))
    for i in range(N):
        prev_rank[arr[i]] = i +1
        current_rank[arr[i]] = i + 1

    M = int(input())

    for _ in range(M):
        a_team,b_team = map(int,input().split())

        if prev_rank[a_team] > prev_rank[b_team]:
            current_rank[a_team] -= 1
            current_rank[b_team] += 1
        else:
            current_rank[a_team] += 1
            current_rank[b_team] -= 1

    result = [0]*(N+1)
    flag= False
    for team_num in range(1,N+1):
        if result[current_rank[team_num]]:
            flag = True
            break
        else:
            result[current_rank[team_num]] = team_num

    if flag:
        print('IMPOSSIBLE')
    else:
        print(*result[1:])

 이건 좀 더 간단한 풀이이다.

 하지만 이 풀이는 ?인 경우가 없다고 가정하고 푼 것이다.

N,K = map(int,input().split())
N += 1
N_list = list(str(N))
cur_idx = -1
max_idx = len(N_list)
while True:
    if N_list.count('5') >= K:
        break
    while N_list[cur_idx] == '5' and abs(cur_idx) < max_idx:
        cur_idx -= 1
    
    cur_value = int(''.join(N_list))
    cur_value = cur_value + 10**(abs(cur_idx)-1)
    N_list = list(str(cur_value))
    max_idx = len(N_list)



print(''.join(N_list))

이 문제는 간단하다. 가장 뒤에서부터 5를 만들어주면 되는것이다. 

여기서 주의해야할 점은 다음과 같은 경우이다. K가 1이고, 주어진 N이 48이였을때

우리는 49부터 탐색을 시작하게 되는데, 그때 50이 되면 K를 만족하는 수가 된다.

그러므로 우리는 5가 아닌 자리수부터 1씩 늘려가면서, 가장 오른쪽 자리부터 5를 만들어줘야한다.

그래서 나는 cur_idx 라는것을 뒤에서부터 접근하기 위해 -1로 해주었고, 

abs(cur_idx) - 1을 해주면 해당 자릿수를 구할 수 있다. 즉 첫번째 자리는 1이 더해지게, 오른쪽에서 두번째자리는 10,

세번째 자리는 100이 더해지게 만들어주는 것이다.

이럴때 주의해야할 점은 999일때이다. 999에서 1을 더해주면 1000이된다. 그러면 우리의 idx가 넘어가게 되므로,

max_idx를 새로 계속 갱신을 해주었다.

그리고 555 이고, 구하는 K가 4일때를 대비해서 while문에 abs(cur_idx)<max_idx 를 넘어갈때를 escape 해주었다.

이런식으로 오른쪽 자리수부터 1씩 더해가면서 5를 만들어주고, 그리고 count를 해서 넘어가면

반복문을 빠져 나올 수 있게 해주었다.

여담으로 문제 제목이 직관적이고, 가장 짧은 문제였던 것 같다.

import sys
from collections import deque

input = sys.stdin.readline


N,M = map(int,input().split())
graph = [set() for _ in range(N+1)]
degree = [0 for _ in range(N+1)]
for _ in range(M):
    pdN,*arr = list(map(int,input().split()))

    for i in range(pdN-1):
        x,y = arr[i],arr[i+1]
        if y not in graph[x]:
            graph[x].add(y)
            degree[y] += 1

stack = deque()
cnt = 0
result = []
flag = True

for i in range(1,N+1):
    if degree[i]==0:
        stack.append(i)
while cnt<N:
    if not stack:
        flag = False
        break
    node = stack.popleft()
    result.append(str(node))
    for next_node in graph[node]:
        degree[next_node] -= 1

        if degree[next_node] == 0:
            stack.append(next_node)
    cnt += 1

if flag:
    print('\n'.join(result))
else:
    print(0)

이 문제와 같은 경우 평범한 위상정렬이다.

여러명의 PD를 통해 앞에서부터, 하나씩 그래프에 SET으로 넣어주었다.

그리고 degree가 0인것들은 최초의 stack에 넣어주고 난뒤에 위상정렬을 구해주면서,

사이클이 발생할 시, 음악프로그램을 구할 수 없는 것이므로, 그때 flag로 분기 처리를 해주었다.

그리고 stack에 나온순서대로 result에 넣어주고 출력을 해주었다.

A,B = map(int,input().split())


if A>B:
    A,B = B,A

X,Y = map(int,input().split())
result = []
flag = True
if Y>=abs(X) or Y<0:
    flag = False
if flag:
    X = abs(X)
    value = X*(A//X)+Y
    while value<=B:
        if A<=value<=B:
            if result:
                flag = False
                break
            result.append(value)
        value += X
if flag and result:
    print(*result)
else:
    print('Unknwon Number')

  이 문제에서 주의해야할 점은 Y가 X보다 큰게 들어올수도 있으며, 0 미만일수도 있다.

그럴 경우엔 False를 해주고, A,B가 서로 반대로 들어올 수 있는것만 조심해주면 된다.

A~B 사이에서 생길수 있는 최소의 X,Y로 만들수 있는 수를 찾는다.

그리고 난뒤에 X를 늘려가면서, 2개이상의 수가 있을때에는 flag로 Unkwon Number를 출력해주면 된다.

A,B = map(int,input().split())


if A>B:
    A,B = B,A

X,Y = map(int,input().split())

X = abs(X)
left_div = A//X
right_div = (B+X)//X
result = []
flag = True
if Y>=abs(X) or Y<0:
    flag = False
if flag:
    for div in range(left_div,right_div+1):
        temp = div*X+Y
        if A<=temp<=B:
            if result:
                flag = False
                break
            else:
                result.append(temp)


if flag and result:
    print(*result)
else:
    print('Unknwon Number')

이건 반복문을 통해서 구현한 것이다.

 클래스 5 문제들을 풀어서 클래스 점수로 플레4에 도달하긴했다..

플레4는 6월1일에 찍었다.

찾아보니 3월9일에 골드1 달성

4월 29일에 플레5달성

6월 1일에 플레4를 달성했다.

느리지만 천천히 꾸준히 문제를 푼것같다.

1월부터 하루 1일 1알고를 한번도 빼먹은적이 없다보니, 푼 문제수가, 직선그래프처럼 그려지긴했다.

플레 3은 갈 가능성은 적지만, 세그먼트 트리나 트리쪽을 더 공부해서 도전은 해보고 싶긴하다.

근데 사실 아직 이분탐색과, 두포인터, 위상정렬 관련된 문제가 나오면 죽쓰는것보면 기초에 대해서 더 열심히 공부해야할 것 같다.