4-2 끝말 잇기

유태형·2022년 5월 11일

Java 알고리즘 프로그래머스

알고리즘 - Java

목록 보기

8/32

출처

해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다.

문제

문제 분석

끝말 잇기가 정상적으로 진행 되었는지 확인하는 문제입니다. 배열이 주어지고 해당 배열의 문자열들을 확인하며 정상 여부를 확인합니다.

풀이

끝말 잇기가 제대로 될려면 2가지를 조건을 지켜야 합니다.

이전 단어의 마지막 글자와 현재 단어의 첫글자가 동일해야 합니다.
단어가 중복 되면 안됩니다.

1번의 경우charAt()메서드를 이용하여 단어에서 알파벳을 뽑아내면 되고, 2번의 경우는 Set.size()를 이용하여 중복여부를 확인합니다.

나의 풀이

import java.util.*;

public class 끝말잇기 {
    public static boolean solution(String[] words) {
        Set<String> set = new HashSet<>();
        String prev= "";
        //단어를 Set에 입력
        for(String word : words){
            if(set.size() >= 1){ //2번째 단어부터
                if(word.charAt(0) != prev.charAt(prev.length()-1)) return false;
                //이전 단어와 현재 단어가 다르면 false반환
            }
            set.add(word);
            prev = word;
        }
        //단어 배열길이 == Set길이 시 중복 x
        return set.size() == words.length;
    }

    public static void main(String[] args) {
        String[] input1 = {"tank", "kick", "know", "wheel", "land", "dream"};
        System.out.println(Arrays.toString(input1));
        System.out.println(solution(input1));

        String[] input2 = {"tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"};
        System.out.println(Arrays.toString(input2));
        System.out.println(solution(input2));
    }
}

향상된 for문과 String으로 단어를 받고 처리 하였었습니다. set.size() >= 1로 두번째 단어부터 이전 단어의 마지막 알파벳, 현재 단어의 첫 알파벳이 동일한지 확인합니다.

강의의 풀이

import java.util.*;

class Solution {
    public boolean solution(String[] words) {
        Set<String> set = new HashSet<>();
        
        //첫번째 단어는 추가
        set.add(words[0]);
        char last = words[0].charAt(words[0].length()-1);
        //첫번째 단어의 마지막 글자
        for(int i=1;i<words.length;i++){
            String w= words[i]; //현재 단어
            char first = w.charAt(0); //현재 단어의 첫 글자
            
            if(last != first) return false; //끝말잇기 x
            if(!set.add(words[i])) return false; //중복
            
            last = w.charAt(w.length()-1); //이전 단어의 마지막 글자
        }
        
        return true; //모두 통과하면 정상적
    }
}

첫 단어와 첫 단어의 마지막 글자를 미리 추출하고 시작합니다.
현재 단어의 첫글자와 이전 단어의 마지막 글자를 비교하고, if(!set.add(words[i]))를 응용하여 중간에 중복되는 단어가 있으면 바로 false를 반환 합니다. Set.add() 삽입되면 true를 반환하고, 중복으로 인해 삽입이 되지 않으면 false를 반환합니다.