Atcoder Beginner Contest 268 후기

A. Five Integers

 숫자 5개가 주어지고, 중복을 제거했을 때 남는 숫자의 갯수를 구하는 문제이다

import sys

arr = list(map(int, sys.stdin.readline().split()))
print(len(set(arr)))

B. Prefix?

 문자열 2개가 주어진 후, 첫번째로 주어진 문자열이 두번째로 주어진 문자열의 접두사가 되는지 여부를 출력하는 문제이다. 단, 두 문자열이 일치하는 경우에도 접두사로 판정됨을 주의해야 한다

import sys

a = sys.stdin.readline().rstrip()
b = sys.stdin.readline().rstrip()
print('Yes' if b.startswith(a) else 'No')

C. Chinese Restaurant

 n명이 원형으로 된 탁자에서 반시계 방향으로 회전하는 행위를 0번 이상 시행할 때, 특정 조건을 만족하는 사람 수를 최대로 할 때, 몇 명이 조건을 만족하는 지 구하는 문제이다. 약간의 사고를 요하는 브루트포스이다. 각 사람이 조건을 만족하는 경우일 때 몇 번의 회전을 하는지를 각각 계산하는 것이다. 예를 들어, n이 3명이라고 하자. 이 때 1번 사람은 회전을 1번 하거나, 2번 할 때 조건을 만족한다고 하자. 마찬가지로 2번 사람은 아예 회전을 하지 않는 것이 조건을 만족한다고 하자. 마지막으로 3번 사람은 회전을 2번 할 때 조건을 만족한다고 하면 결국 공통적으로 나온 회전 수 중 가장 많은 회전 수인 2회가 정답이 된다. n 제한이 $10^5$이고 조건이 3가지 밖에 없기 때문에 시간복잡도는 $O(N)$이다

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

# cache : 회전횟수를 key, 조건을 만족하는 사람들의 set을 value로 갖는 dictionary
cache = dict()
for i in range(n):
    for j in [(arr[i] - 1) % n, arr[i], (arr[i] + 1) % n]:
        # 현재 위치에서 위치 j까지 반시계 방향과 시계 방향 중 더 가까운 쪽으로 회전
        if j >= i:
            res = abs(j - i)
        else:
            res = abs(n - i) + j
            
        # 회전 후 조건을 만족하는 사람 추가
        if res not in cache:
            cache[res] = set()
        cache[res].add(arr[i])
        
# 회전 횟수 별 조건을 만족하는 사람 수 중 최대값 출력
ans = 0
for i in cache:
    ans = max(ans, len(cache[i]))
print(ans)

D. Unique Username

 n개의 문자열이 주어지고, 1개 이상 n개 이하의 문자열을 선택하여 새로운 문자열을 생성한다. 또한 m개의 문자열이 주어진다. 이 때, k개를 문자열을 골랐을 때 총 k-1개의 언더바(_)를 문자열의 사이사이에 붙여준다. 단, 언더바의 갯수는 1개 이상이어야 하며, 언더바를 포함하여 최종적으로 생성된 문자열의 길이는 16을 넘을 수 없다. 또한, 최종적으로 생성된 문자열이 m개의 문자열 중 어떠한 것과 같아서는 안된다. 이 때, 조건을 만족하는 문자열을 하나라도 만들 수 있는지 구하는 문제이다

 우선 n이 8로서 매우 작다는 점에 유의하면 간단하게 순열과 백트래킹, 즉 브루트 포스로 풀 수 있음을 알 수 있다. 왜냐하면 실제로 문자열을 만들기 위해서는 가능한 모든 순열을 조사해야 하는데, $8! = 40320$이기 때문이다. 이후 필요한 과정 역시 전체 문자열의 길이가 16이하여야 하기 때문에 전체적인 복잡도는 $O(N!N * size \ of \ concated  \ String) = O(N!N * 16)  \approx 5 * 10 ^ 6$이며, 시간안에 정답을 구할 수 있다. 

import sys, itertools

# go : 현재 temp의 순열 중 idx번째 문자열을 concat한 결과가 res이고 가능한 언더바의 갯수가 total일 때
#      조건을 만족하는 문자열이 있는지 확인하는 함수
def go(idx, res, temp, total):
    # Base Case : 순열로 뽑은 문자열을 다 소진한 경우
    if idx == len(temp):
        # 이미 있는 문자열들과 겹치지 않고 길이 조건을 만족하는 경우
        if res not in cache and 3 <= len(res) <= 16:
            print(res)
            sys.exit(0)
        else:
            return
    # Recursive Case : 언더바의 갯수를 가능한 수 만큼 추가
    for i in range(1, total + 1):
        if total - i >= 0:
            go(idx + 1, res + '_' * i + temp[idx], temp, total - i)

# 입력부
n, m = map(int, sys.stdin.readline().split())
# arr : 순열에 이용할 문자열들의 리스트
arr = []
for _ in range(n):
    s = sys.stdin.readline().rstrip()
    arr.append(s)
# cache : 겹쳐서 안되는 문자열들의 set
cache = set()
for _ in range(m):
    s = sys.stdin.readline().rstrip()
    cache.add(s)
    
# 순열을 뽑은 후, concatination
for i in itertools.permutations(arr, n):
    left = 16 - len(''.join(i))
    if left >= 0:
        go(1, i[0], i, left)
        
# 위에서 조건을 만족하는 문자열을 찾지 못한 경우 -1 출력
print(-1)

후기 : 약 2달만의 포스팅이다. 그동안 우아한테크코스 과정을 마무리하는 시기에 있어서 포스팅을 늦게 나마 작성하게 되어 기쁘다. 대회 자체는 9월에 unrated로 참여하였다. 기억을 되살려보자면 C번의 문제 이해를 좀 늦게 했고 아이디어마저 쉽게 떠오르지 않아 D번 먼저 풀었던 기억이 있다. 냉정히 난이도는 D번까지 쉬운 편이었으며 E번부터 난이도 급격히 상승해서 4솔로 마감했다. 업솔빙을 시도하였으나, atcoder problems의 난이도 배정이 블루...여서 다음에 풀기로 하였다. 여유가 나는대로 다시 앳코더를 응시해야겠다!