김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 6531 이런 문제는 유치원생도 해결할 수 있어 파이썬(Python)

문제 링크

유치원생도 해결할 수 있다 해놓고 플레 5인 문제.
집합을 파싱해서 유효한 집합인지 확인하면 되는데, 난점은 집합의 원소가 집합을 이루는 기호와 똑같으며, 집합 안에 집합이 있을 수 있다는 점이다.
즉, 같은 기호가 맥락에 따라서 집합의 원소로도 해석되고 집합기호로도 해석될 수 있다.
중요한 점은 원소들이 ,로 구분된다는 점인데, 따라서 ,를 기준으로 Elementlist(집합의 양 쪽 중괄호를 제외한 부분)를 분할해서 유효한 값인지 확인하면 된다.
이때, ,가 현재 집합의 원소를 구분하는 구분자인지({},}}와 같이), 아니면 현재 집합 안의 원소인 집합의 원소를 구분하는 구분자인지({{},}}}와 같이), 그것도 아니면 그냥 원소 ,인지 알 수가 없다.
좀 더 크게 얘기하자면, ,가 현재 집합의 구분자인지 아닌지를 알 수가 없다.
따라서, ,를 기준으로 나누는 경우와 그렇지 않은 경우 모두 확인해 보면 된다.
필연적으로 중복 계산이 많이 등장하므로 valid[][] DP 리스트를 만들어 메모이제이션을 하면 된다.

#!python

from sys import stdin
input = stdin.readline

# valid를 채워넣는 함수
# s, e : 시작 인덱스, 끝 인덱스 + 1
# 즉, exp[s:e]가 valid한지 체크하는 함수
# emptyok는 빈 문자열을 valid한 걸로 처리할지의 여부
# 예를 들어 '{}'[1:1]의 ''는 valid하지만 {,,}[1:1]의 ''는 invalid함
def check(s, e, emptyok):
    # 빈 문자열이면 emptyok 리턴
    if s == e:
        return emptyok
    # valid[s][e]가 이미 캐시되어 있으면 그대로 리턴
    if valid[s][e] is not None:
        return valid[s][e]
    # 만약 양 끝이 {}이면 괄호를 벗긴 문자열의 validity 확인
    if exp[s] == '{' and exp[e-1] == '}' and not valid[s][e]:
        valid[s][e] = check(s + 1, e - 1, True)
    # 이후 ,를 기준으로 나누어서 , 전과 , 후가 모두 valid한지 확인
    # valid한 경우가 하나라도 있으면 True
    for m in range(s + 1, e):
        if check(s, m, False) and exp[m] == ',' and check(m + 1, e, False):
            valid[s][e] = True
    # 위에서 한 번도 True가 나온 적이 없다면, 즉 valid한 경우가 없다면 False
    if valid[s][e] is None:
        valid[s][e] = False
    return valid[s][e]

n = int(input())
for t in range(1, n + 1):
    # 시작 {, 원소 리스트, 끝 }로 나누어 입력받음
    # 만약 ValueError가 뜬다면 '{' 같은 길이가 1인 문자열이 들어온 경우임
    try:
        s, *exp, e = input().rstrip()
    except ValueError:
        print(f'Word #{t}: No Set')
        continue
    
    # 양 끝이 {}가 아니면 No Set
    if s != '{' or e != '}':
        print(f'Word #{t}: No Set')
        continue
    # empty set도 set이므로 Set
    if not exp:
        print(f'Word #{t}: Set')
        continue

    l = len(exp)
    
    # valid[i][j]는 exp[i:j]가 가능한 집합의 원소 리스트인가
    valid = [[None for _ in range(l + 1)] for _ in range(l)]

    # 단일 원소는 항상 가능한 원소 리스트임(Base Case)
    for i in range(l):
        valid[i][i+1] = True
    
    # exp[0:l], 즉 exp[:]가 valid한지 확인
    check(0, l, True)
    
    print(f'Word #{t}:', 'Set' if valid[0][-1] else 'No Set')

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑