[프로그래머스/ Summer/Winter Coding(~2018)] 영어 끝말잇기

Q. 영어 끝말잇기

A1.

import java.util.HashSet;

class Solution {
    public int[] solution(int n, String[] words) {
    
        //HashSet을 생성한 후에, 끝말잇기에서 나온 단어를 저장(중복 확인을 위해)
        //첫번째 단어는 중복 될 일이 없으니까 바로 HashSet에 저장
        HashSet<String> duplication = new HashSet<>();
        duplication.add(words[0]);
        
        //두번째 단어부터 마지막 단어까지 순차적으로 확인
        for(int i = 1; i < words.length; i++) {
        
        //last : 이전 단어의 마지막 글자, first : 현재 단어의 첫 글자
            char last = words[i - 1].charAt(words[i - 1].length() - 1);
            char first = words[i].charAt(0);
            
            //첫글자랑 마지막 글자가 다르거나, HashSet에 이미 단어가 있다면 실패
            //몇번 사람이 몇번째 차례에서 실패했는지 계산
            if(first != last || duplication.contains(words[i])) { 
                int human = (i % n) + 1;
                int turn = (i / n) + 1;
                
                return new int[]{human, turn};
            }
            
            //조건문에서 실패하지 않고 나왔다면, 그 단어는 HashSet에 추가
            duplication.add(words[i]);
        }

        return new int[]{0,0};
    }
}

 

A2.

import java.util.ArrayList;

class Solution {
    public int[] solution(int n, String[] words) {

        ArrayList<String> duplicaition = new ArrayList<>();
        
        duplicaition.add(words[0]);
        
        for (int i = 1; i < words.length; i++) {
        
            String prevWord = words[i - 1];
            String currWord = words[i];
            
            char last = prevWord.charAt(prevWord.length() - 1);
            char first = currWord.charAt(0);
            
            if (first != last || duplicaition.contains(currWord)) {

                int human = (i % n) + 1;
                int turn = (i / n) + 1;
                
                return new int[] {human, turn};
            }
            
            duplicaition.add(currWord);
        }
        
        return new int[] {0, 0};
    }
}

---

<HashSet vs ArrayList>

1. HashSet

• 구조 : 내부적으로 해시 테이블(배열 + 연결 리스트, 트리 구조)을 사용
• 특징
  • 순서 보장하지 않음
  • 해시 함수를 사용해 요소 저장 위치를 결정
  • 존재 여부(contains)를 평균적으로 O(1)의 시간에 검사할 수 있음
  • 중복 체크나 특정 값의 존재 여부를 확인할 때나 큰 데이터 집합에서 효율적

2. ArrayList

• 구조 : 내부적으로 동적 배열을 사용
• 특징
  • 요소의 순서 유지
  • 특정 인덱스에 있는 요소에 접근은 O(1)이지만, 요소를 검색(contains)할 때는 앞에서부터 하나씩 확인하므로 오래 걸릴 경우 O(n)의 시간이 걸림
  • 순서가 중요하거나, 요소의 추가/삭제가 빈번할 때 효율적

3. HashSet이 빠른 이유

• 검색 시간
  • ArrayList의 contains() 메서드는 내부적으로 순차 탐색을 해, 리스트 크기가 커지면 검색 시간이 선형적으로 증가
  • HashSet은 해시 함수를 이용하여 요소가 저장된 버킷을 바로 찾아내 검색 시간이 평균적으로 O(1)에 처리
• 해시 함수
  • HashSet은 각 객체의 hashCode() 값을 사용해서 저장 위치를 결정
  • 해시 코드를 통해 저장된 위치를 바로 찾기 때문에, 많은 요소가 있더라도 대부분 빠른 검색이 가능