goodseog   4년 전

1. 만약 input 이 그룹단어가 아니라면, 무조건 gg이다.

2. greedy 하게 붙일 수 있는 경우 효율적으로 붙인다.
2-1 char c 로 시작하는 단어의 집합 Cfirst, 오로지 c로 이루어진 Call, c로 끝나는 단어의 집합 Clast 수집.
       기존의 word 집합에서 원소를 제거함. ( 어떤 단어가 시작과 끝 alphabet이 같으면서, group word 
      라면 그 단어는 하나의 alphabet으로만 이루어져있다.)
2-2 만약 모두 다 비어있을 경우, 다음 c에 대해서 조사를 한다.
2-3 만약 Cfirst 혹은 Clast가 여러개 존재할 경우, group word 를 만드는 것이 불가능하다. gg
2-4 newWord = [ Clast, Call ........  , Cfirst ] 로 새롭게 생성하여, 만약 이것이 group word 라면
       리스트에 추가를 한다. group word가 아니라면 gg

3. 모든 alphabet에 대해서 2의 과정을 거친 후 words 가 여러개 존재한다면 -_-을 출력,
    1개만 존재한다면 words[0] 를 출력한다.

다음과 같은 알고리즘으로 문제를 해결해보았는데, 71%에서 오답 처리가 됩니다.
혹시 잘못된 과정이나, 좋은 예시 소개해주시면 감사드리겠습니다!!

isGroupWord(str) 함수는 1316 그룹 단어 체커 문제에서 정답 처리를 받았습니다.

goodseog   4년 전

자문자답!

3 과정 전에 마지막으로 모든 단어를 합쳤을 때  group word인지 확인하여야 합니다.

그룹 단어가 불가능한 경우(gg)인데 -_- 를 출력하는 케이스가 존재합니다.

댓글을 작성하려면 로그인해야 합니다.