(JAVA) 백준 1062번 : 가르침

https://www.acmicpc.net/problem/1062

1062번: 가르침

 

 

상당히 애먹었던 문제.

 

해결 후 굇수님들의 코드를 참고해서 

 

시간을 줄이긴 했지만

 

굇수님들보다는 시간이 조금 더 걸리긴 했다.

 

 

*** 제 주관적인 해결 방법에 대한 풀이입니다! 참고 바랍니다.

 

 

 

 

 

 

문제 일부 캡쳐 화면

문제에서 짚고 넘어갈 사항은

 

 

1) 입력받는 단어들은 anta + ~ + tica 로 이루어진 단어이기 때문에 (a : 3개, t : 2개, n : 1개, i : 1개, c : 1개)

K의 값을 보고 판단해서 5보다 작으면 아무 단어도 읽지 못하기 때문에 0을 출력하고 종료한다.

 

 

2) 만약 입력받은 K의 값(K : 가르칠 수 있는 알파벳 개수) 이 26이면 모든 알파벳을 가르치므로 

모든 단어를 읽을 수 있어 n을 출력하고 종료한다.

 

 

3) 1)과 마찬가지로, anta 와 tica 사이의 단어만 가지고 이후에 판단해도 되기 때문에

subString(4, 단어.length - 4) 로 잘라서 저장해둔다.

 

 

4) "읽는다" 라는 것은 "해당 단어에 들어가 있는 모든 글자를 가르쳐야 한다." 라는 뜻이다.

그렇기 때문에, 읽기 위한 글자들을 전부 찾은 다음, 그 글자들만 조합해서 단어의 개수를 파악해야 한다.

*** 저는 조합의 방법을 백트래킹으로 사용했습니다.

 

 

 

이렇게 보면

슬슬 알고리즘이 떠오르지 않는가?!

 

 

바로 내 매커니즘으로 넘어가겠다.

 

 

 

매커니즘

---

1) 입력 값들을 전부 저장한다.

 

 

2) 위 짚고 넘어갈 사항 중 1), 2)에 대한 예외 처리를 한다.

 

 

3) 단어 내 알파벳 사용 여부를 체크한다.

boolean 배열 하나를 사용하면 끝!

 

 

4) 3) 진행하면서 알파벳 사용 개수를 count한 후, K값과 비교한다.

만약 k가 count보다 같거나 크면 모든 단어를 읽을 수 있다.

 -> 가르칠 수 있는 문자 개수가 단어를 읽기 위해 필요한 문자 개수보다 같거나 많으면 다 읽을 수 있다.

 

 

5) 백트래킹을 통해 K 개 만큼 필요한 알파벳 들 중에서 선택한다.

** 이 때, anta + tica 에 들어가는 5개 숫자를 제외하고 선택한다!

 

 

6) 선택한 알파벳들로 이전에 저장한 문자들을 탐색하며 카운트한다.

 

 

7) 카운트한 값 중 최댓값을 출력한다.

 

 

 

 

*** 제가 해맸던 예외 케이스 중 하나입니다.

input :

1 7
antabctica

 

 

 

 

감사합니다.

 

소스코드

---