[BOJ] 1062 가르침

1062번: 가르침

문제

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

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

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

3 6
antarctica
antahellotica
antacartica

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

2

---

삼성 SW 특강이 시작됐다. 오티하고 첫 수업을 했는데 내용은 비트마스크에 관한 내용이었다. 그런데 오늘 연구실 미팅이 있어서 실시간 강의를 듣진 못 했다.

 

사이트에 올라와있는 강의 정도만 봤는데 거의 아는 내용이었음에도 새로운 인사이트를 얻을 수 있었다. 정수의 각 비트를 집합의 원소가 부분 집합에 속하는지 나타낸다고 생각하면 모든 부분 집합의 경우의 수를 상당히 쉽게 얻을 수 있었다. 어려운 개념이나 적용이 아니고 심지어 이미 알고 있던 내용이지만 뭔가 새로 깨달은 느낌이었다.

 

사실 이전 글을 올리면서 비트를 다루는게 익숙해서 비트 마스크도 그렇게 어렵지 않다고 했는데 비트 마스크를 실제로 문제에 적용해서 푸는 것은 다른 내용인 것 같다. 다른 사람들이 비트 마스크 기법을 사용해서 푼 문제를 이해하는 것은 쉽게 할 수 있다. 하지만 잘 적용하기가 아직 익숙지 않다.

 

삼성에서 풀어보라고 제시한 문제를 다 풀고 좀 더 익숙해지기 위해서 백준에서도 비트마스크 문제를 골랐다. 아예 안 풀어본 문제 유형은 아니었지만 막상 비트 마스크를 사용하려니 역시 불편했다. 어떤 때에 어떤 연산을 사용해야 하는지 막 헷갈리고 0으로 set 하는 방법도 바로 떠오르지 않았다. 연습해서 cost가 적은 shift 연산을 더 능숙하게 사용할 수 있게 된다면 더 가볍게 코드를 짤 수 있을 것이다. 

 

이 문제는 아무 생각 없이 백트래킹으로 풀려고 했었다. 하지만 다른 사람들의 코드를 보니 최적화할 수 있는 부분이 아주 많았다. 첫번째로 모든 단어의 시작과 끝이 주어졌으므로 문자열의 앞뒤를 잘라도 무방하다. 또한 앞뒤에서 사용되는 문자의 bit를 미리 set 한다. 두 번째로는 문자열을 굳이 저장하고 있을 필요가 없다는 점이다. 미리 문자열에 등장하는 문자들에 대한 정보를 가지고 있으면 O(1)에 그 문자열을 읽을 수 있는지 없는지를 알아낼 수 있다. 어떤 사람이 이런 식으로 코드를 작성한 것을 보고 감탄했다. 문자열이 그리 길지 않아서 이렇게 작성하지 않아도 통과는 할 수 있지만 문자열이 긴 경우에는 아주 효율적일 것이다. 

 

그리고 이 문제를 분명 다 푼 것 같은데 예시조차도 출력이 제대로 나오지 않았다. 도대체 뭐가 문제인가 싶어서 비주얼 스튜디오에서 디버깅을 열심히 했다. learn 변수를 전역 변수로 사용했는데 함수가 호출되니까 갑자기 0이 되길래 이게 무슨 일인가 싶었다. 꽤나 시간을 써서 문제를 찾았다. 알고보니 main에서 같은 이름의 변수를 한번 더 선언하는 바람에 main의 learn과 전역 변수의 learn이 다른 변수가 되어버렸다. 이건 1학년때 배운 내용인데... 이런 실수는 눈에 잘 안 보여서 찾기가 너무 힘들다. 

 

후기)

비트 마스크랑 조금이나마 더 친해진 것 같다.

이제 매일할게 많아졌다.

1일 1커밋, 삼성 특강 진도, 스터디 진도

이렇게 살다보면 뭐라도 남는게 있겠지.