사용한 자료구조 : Set

---

📌Set 을 사용해 중복 확인

• Set 자료구조는 중복을 허용하지 않는다.

  HashSet 은 요소의 순서를 보장하지 않기때문에 빠르게 요소에 접근이 가능하다 O(1)

  ---

  LinkedHashSet 은 삽입 순서를 보장하고, HashSet과 비교해서 속도면에서 동일한 성능을 보이지만, 이중연결 리스트를 추가로 유지하고있기 때문에 더 큰 메모리를 가져간다. O(1)

  ---

  TreeSet 은 요소의 정렬기준으로 순서를 보장하기 때문에(a, b, c 또는 1, 2, 3 등등) 속도는 비교적 느릴수 있다. O(log n)

✏️현재 코드에서는 효율적인 HashSet이 더 낫다고 생각해 HashSet을 사용하여 문제에 접근했다.

• 가장 먼저 시작하는 단어를 set에 넣어준다
  다음 단어와 비교하기 위해서

Set<String> set = new HashSet<>();
        set.add(words[0]);

---

📌반복문을 사용하여 현재단어와 다음 단어를 초기화

• i는 1부터 시작했기 때문에, 현재단어는 i-1 인덱스
  다음 단어는 i 인덱스로 정해주었다.

for (int i = 1; i < words.length; i++) {
            String cur = words[i - 1];
            String next = words[i];

---

📌반복문 탈출조건

1. set에 있는 현재 단어들과, 다음 단어를 비교해서 true 또는 false를 반환받고, 현재 단어의 마지막 글자와 다음 단어의 첫 글자를 비교한다.
2. 위 조건에 부합하지 않으면 set에 다음 단어를 넣는다.
3. 위 조건이 true가 되면 탈락자 번호와 몇번째에 탈락했는지 리턴값에 넣는다.

if (set.contains(next) || cur.charAt(cur.length() - 1) != next.charAt(0)) {
                int fail = (i % n) + 1;
                int turn = (i / n) + 1;
                return new int[] {fail, turn};
            }
            set.add(next);

---

📌배열을 모두 돌았지만, 반복문 탈출을 하지 못했다면

• 모두가 똑똑한 나머지 끝말잇기를 잘 했다면 0,0 을 리턴해주었다.

return new int[] {0 ,0};

---

💻 최종 코드 💻

import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        Set<String> set = new HashSet<>();
        set.add(words[0]);

        for (int i = 1; i < words.length; i++) {
            String cur = words[i - 1];
            String next = words[i];

            if (set.contains(next) || cur.charAt(cur.length() - 1) != next.charAt(0)) {
                int fail = (i % n) + 1;
                int turn = (i / n) + 1;
                return new int[] {fail, turn};
            }
            set.add(next);
        }
        return new int[] {0 ,0};
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int n = 3;
        String[] words = {"tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"};
        System.out.println(Arrays.toString(sol.solution(n, words)));
    }
}

👏👏👏👏👏👏👏👏👏