개요
어제 (03/29) 저녁 9시부터 10시 40분까지 진행된 Atcoder Beginner Contest 399 후기입니다.
총 7문제 중 4문제를 풀었습니다.
A번부터 D번까지 풀이하는데 19분을 소모했습니다. 이후 E번과 F번을 풀기 위해서 대회 종료시각까지 트라이를 했지만 풀이하지 못했습니다. rating이 떨어지나 걱정했지만, 다행히도 rating이 약간 올라서 안심했습니다.
풀이
해설은 꼭 문제를 한번 읽고 확인해주세요.
A - Hamming Distance
문제 내용
1
2
3
두 문자열이 주어진다.
두 문자열의 해밍 거리 (서로 다른 문자의 개수)를 구하면 된다.
풀이
문자열을 순회하면서 서로 다른 문자의 개수를 구하면 됩니다.
B - Ranking with Ties
문제 내용
1
2
3
N 개의 score가 주어집니다.
각 score마다 RANK() 를 구하면 됩니다. (sql의 RANK()와 같이)
풀이
정렬을 사용하거나, map을 사용하거나 기타 등등 RANK()를 구현하기만 하면 됩니다.
C - Make it Forest
문제 내용
1
2
3
무향 그래프 F가 주어집니다.
간선을 지워 cycle이 없는 그래프가 만드려고 합니다. 이때, 지워야 하는 간선의 최소 개수를 구해야 합니다.
풀이
처음에 이렇게 풀어도 되는건가? 좀 헷갈렸다. 몇 가지 그래프를 그리다보니 확신을 하게 되었고, 아래와 같이 구성을 했다.
1
2
3
4
1 ~ N 까지 정점을 탐색하는데, 각 정점이 방문되지 않은 경우 DFS 탐색을 한다.
그리고, 만약 이전에 방문했음에도 다시 방문하게 되면 카운팅한다.
단, 부모로 다시 탐색을 하러 돌아가는 경우는 배제해야 한다.
D - Bonfire
문제 내용
1
2
같은 숫자임에도 서로 인접하지 않은 두 숫자를 고른다.
두 숫자의 위치를 서로 바꾸어봤을 때, 각 숫자가 인접하게 된다면 카운팅한다.
풀이
솔직히 이 문제가 D번이 맞나? 싶었다. 생각보다 너무 쉽게 풀리는 문제였다.
그냥 각 숫자마다 위치 2개를 따로 hash 또는 배열에 저장해둔다.
그리고 앞에서부터 순회하면서 인접한 두 숫자에 대해서 저장해둔 위치로 조건을 판단해보면 된다.
E - Replace
문제 내용
1
2
3
4
5
6
7
문자열 S와 T가 주어진다.
문자열 S를 T로 바꾸길 원한다.
다만, 문자열 S에 존재하는 임의의 문자를 모두 하나의 문자로 바꾸는 연산만 가능한 상황이다.
이때, S를 T로 바꾸는 것이 가능한지, 가능하다면 최소 연산의 수가 어떻게 되는지 구해야 한다.
풀이
결국 풀이하지 못한 채로 대회가 종료되었다.
내 접근은 S->T로 가기 위한 과정을 유향 그래프화 시키는 것이었다. 만약 ab -> cb 라면 a -> c 라는 간선을 추가하는 것처럼 말이다.
이 과정에서 cycle이 없다면 간선의 수가 답이었고, cycle이 있다면 cycle로 변하는 과정에서 임의의 temp 문자로 변환되었다가 맨마지막에 변환되는 식이 되지 않을까 해서 간선의 수 + 1 을 더하는 방식이었다.
다만 이 과정을 구하는게 까다로웠고, 현재 temp 문자로 사용할 수 있는 문자가 있는지 등을 체크하기 위해 SCC와 위상정렬을 막 적용하다가 시간이 끝났다…
결론
7문제 중 4문제를 풀이하고 끝나서 굉장히 찝찝한 contest였다. 트리나 그래프 문제가 나오면 아직도 망설임이 좀 있는 것 같다. 관련 문제와 아이디어들을 좀 더 접할 필요가 있는 것 같다.