[1148] 단어 만들기

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

1148번: 단어 만들기

문자열, 구현 문제이다. 딕셔너리 자료형을 사용했으나 시간 초과를 받았다. 아마도 알파벳순으로 정렬하는 과정에서 오래 걸린 듯싶다. 이후 크기 26인 배열을 생성하여 각 알파벳 순서대로 만들기 위한 개수와 사용 횟수를 담아 처리하였다.

 

풀이

퍼즐의 가운데 글자가 반드시 포함되어야 하는 것이 조건이다. 즉 해당 퍼즐을 통해 만들 수 있는 단어의 개수가 최저, 최고인 글자를 판별하는 문제다.

 

입력되는 단어들은 크기 26의 배열로 변환한다. 배열의 각 원소는 해당 알파벳의 개수를 담는 배열이다. 이후 해당 배열을 담는 2차원 배열 dictionary를 만든다.

 

퍼즐을 입력받을 때에는 마찬가지로 각 알파벳이 몇 개 있는지 나타내는 크기 26의 배열과 이후 dictionary를 탐색하면서 만들 수 있는 단어라 판단되면 해당 단어를 만들기 위해 사용된 알파벳의 횟수를 담는 배열 cnt: Array(repeating: -1, count:26)를 생성한다. 중요한 점은 해당 원소의 알파벳이 사용되었는지 사용되지 않았는지를 판별하기 위해 모든 크기 26짜리 배열은 -1로 초기화 한상태로 시작해야 한다. 코드로 보면 이해하기 쉬울 것이다.

 

마지막으로 cnt를 탐색하면서 최저 횟수와 최고 횟수를 찾아낸 뒤 해당 알파벳들을 출력해주면 된다.

 

정답 코드

 퍼즐의 입력 횟수가 문제에 적혀있지 않아, 처음 시간 초과를 받았을 때는 print() 호출 횟수가 많아져 스위프트의 느린 print() 속도를 대처하기 위해 Rhyno님이 작성한 FileIO 클래스를 사용했었다. 하지만 결론적으로는 해당 사항은 원인이 아니었고 아마도 딕셔너리 구조의 sort() 메서드의 속도가 느린 것이 더 큰 요인이지 않았나 싶다.