백준 1062번 가르침 :: 마이구미

이번 글은 백준 알고리즘 문제 1062번 "가르침" 을 다뤄본다.

백트래킹을 활용하는 문제로써, 20% 대의 정답 비율을 가졌다.

이전에 다룬 6603번 로또와 유사한 문제지만 문제를 잘 이해하지 않는다면, 시간 초과를 경험하게 된다. 

백트래킹 관련은 6603번 로또 문제 풀이를 통해 참고하길 바란다. 참고 링크

DFS, BFS - http://mygumi.tistory.com/102
Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc

2019.06.11 재채점 결과 메모리 초과 발생으로 코드 추가

 

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

 

모든 K개의 글자에 대해 입력된 단어들의 개수를 체크하면 된다.

 

1. 읽을 수 있는 K개 글자 고르기
2. 고른 글자들을 통해 읽을 수 있는 단어 개수 구하기
   

 

본인은 백트래킹을 활용했지만, 시간 초과를 경험했다.

그 이유는 모든 경우를 고려했다는 점이었다.

문제에서 빨간색으로 나타냈듯이, "a, c, i, n , t" 는 고정적으로 포함되어 있는 알파벳이다.

그렇기에, 위 5개의 알파벳은 거를 필요가 있다.

이 문제의 실패 이유는 이 부분이 크지 않을까? 생각한다.

 

---

 

최근 재채점으로 인해 메모리 초과를 경험했다. (솔직히 잘 모르겠다, 똑같은 로직으로 다른 언어는 잘 동작하는 것 같다.)

기존 코드는 탐색에 있어서만, 고정적인 알파벳을 거르는 작업을 했다.

그래서 처음부터 입력 문자열에서 고정적으로 포함되는 알파벳을 걸러버리는 것을 추가했다.

 

for (int i = 0; i < n; i++) {
    String input = sc.readLine();
    input = input.replaceAll("[antic]", "");
    list.add(input);
}

 

위 코드는 처음부터 입력 문자열에서 고정적으로 포함되는 알파벳을 걸러버린다.

더 나아가서, antic 를 뺀 문자열을 가지고 후보자들을 추려낼 수 있다.

 

antabtica
antaccetica

 

위와 같이 주어진다면, 후보자는 b, e 가 되는 것이다.

고정적으로 포함되는 a, c, n, i, t 을 제외한 알파벳을 탐색할 수도 있지만,

위처럼 주어지는 입력값을 토대로 b, e 같은 후보자만을 추려내서 훨씬 적은 비용으로 탐색할 수도 있다.

 

고정적으로 포함되는 a, c, i, n, t 를 최대한 활용하는 것이 핵심인 것 같다.

최종 코드에는 위와 같은 후보자들을 사용하지는 않았다.

충분히 최종 코드에서도 DFS 를 간추려진 후보자로만 돌린다면, 더 시간을 줄일 수 있다.

 

전체 코드를 통해 이해하길 바란다.

Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/1062.java