개요

어제 (2/22) 저녁 9시부터 10시 40분까지 진행된 Atcoder Beginner Contest 394 후기입니다.

총 7문제 중 5문제를 풀었습니다. A ~ D까지 4문제는 대회 시작후 13분 안에 풀이했지만 E번 정확한 풀이를 생각해내는데 60분을 썼고, F번 문제를 읽고 끝났습니다.

풀이

단순히 주어지는 숫자 문자열에서 2의 개수만큼 다시 2를 출력하는 문제입니다. 빠르게 구현하면 됩니다.

주어지는 문자열을 문자열의 길이를 기준으로 정렬 후 차례대로 붙여 출력하는 문제입니다. 빠르게 구현하면 됩니다.

주어지는 문자열에서 WA 라는 문자열을 AC 라는 문자열로 계속해서 대체할 때, 최종 문자열을 구하는 문제입니다.

예를 들어, WWA 라는 문자열이 있으면 WWA → WAC → ACC 로 변합니다.

저는 단순히 처음에는 스택을 활용할까 생각했지만, 문자가 변하는 양상을 보니 W*X개+A*1개 의 형태를 갖춰야만 바뀐다는 걸 캐치하고, W의 개수를 세다가 A 문자가 등장하면 대체하는 식으로 코드를 구성했습니다.

전형적인 안정적인 괄호 문자열 문제입니다. 다만, 괄호의 종류를 (), <>, [] 로 해두었습니다. 따라서, 관련 처리를 하면서 스택으로 해결하면 됩니다.

그래프가 주어집니다. 단, 정점이 아닌 “간선”마다 문자가 기록되어 있는 그래프입니다. 이때 모든 정점 사이의 페어마다, 간선의 문자열을 나열해서 팰린드롬이 되도록 하는 경로의 최소 길이를 구해야 합니다.

처음에 저는 BFS로 정점마다 출발하여 팰린드롬인지 파악하는 완전탐색으로도 1억 내외로 연산 수가 떨어지면 시간안에 들지 않을까라는 생각으로 트라이했습니다. 하지만 TLE가 나왔고, 다른 방법을 생각해야 했습니다.

이때 굳이 간선의 정보가 주어지고 있는데, 정점 기준으로 탐색할 필요가 있을까 생각이 들었습니다. 그래서 모든 간선은 일단 문자가 1개로 구성된 팰린드롬이고, 양 옆에 같은 문자를 이어 붙이면 팰린드롬이 되지 않을까 라는 생각으로 알고리즘을 구성했습니다.

먼저 정방향 간선 정보와 역방향 간선 정보를 저장한다.
모든 간선을 큐에 넣는다. (해당 간선은 길이가 1인 팰린드롬이기 때문에, { 시작점, 끝점, 길이=1 }) 와 같이 넣는다.
아래에서 설명 추가 과정 필요
큐의 맨 앞에 있는 간선에서 정방향 간선 정보와 역방향 간선 정보를 참조해, 앞 뒤로 같은 문자을 붙일 수 있느지, 붙일 수 있다면 그것이 현재 최소 길이인지 확인해서 갱신 후 큐에 다시 넣는다.
갱신된 모든 길이를 출력한다.

이 방법의 이점은 일단 간선의 정보만 다룬다는 것이고, 만들어진 문자열들이 팰린드롬인지를 체크할 필요가 없다는 것입니다.

그리고 이 방식은 홀수 길이인 경우만 알아낼 수 있는데 따라서 3번 과정에서 모든 i에 대해 i → i 로 가는 가상의 경로에 현재까지의 팰린드롬 길이가 0이다를 집어넣어놓으면 됩니다. { 출발점=i, 끝점=i, 길이=0} 과 같이 말입니다.

그래프 정보가 주어집니다. 이때 아래 조건을 만족하는 부분 그래프의 최대 크기를 구합니다.

딱히 떠오르는 해답이 없었습니다…

문제조차 읽지 못했습니다.

7문제 중 5문제를 풀이하면서 점차 예전의 실력을 되찾아가는 느낌이 들었습니다. 언젠가 모든 문제를 막힘없이 자연스럽게 다 푸는 실력까지 도달하고 싶습니다.