[자바, JS] 프로그래머스 - 영어 끝말잇기 (Lv2, Java, JavaScript)

문제 : Programmers-영어 끝말잇기

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

 

필요 알고리즘 개념

• Set
  
  • 해시셋을 사용해 이전에 나온 문자열이 중복으로 나왔는지 확인할 수 있어야 한다.
• 문자열, 파싱
  
  • 문자열의 첫 문자와 마지막 문자를 확인할 수 있어야 한다.

 

 

 

  문제에서 찾고자 하는 종료 조건은 아래의 두 가지 이다.

1. 이전에 나온 단어가 다시 나오는지

2. 직전에 나온 단어의 마지막 문자(character)가 이번에 보고 있는 단어의 첫번째 문자와 동일한지

 

  '1'의 경우엔 Set을 사용해 중복 체크를 할 수 있다. 자바의 경우엔 HashSet을 사용하면 되고, js의 경우엔 Set을 사용해주면 된다. '2'의 경우엔 문자열에서 원하는 character을 얻을 수 있어야 한다. 자바의 경우엔 charAt 함수를 사용하고, js는 str[0]과 같이 배열 인덱스 접근하듯이 찾을 수 있다.

 

 

 

  다음으로 출력 하고자 하는 값을 생각해보자.

A. 위 종료조건에 걸린 경우가 해당 사람의 몇 번째 순서인지

B. 위 종료조건에 걸린 경우가 몇 번째 사람인지

 

  이 문제의 경우 N명이 차례대로 진행한다. 현재 i번 인덱스의 문자열을 보다가 종료 조건에 걸린 경우, 그 이전에 i/N번만큼 1,2,3,...,N번 사람이 단어를 말했을 것이다. 따라서 A는 간단하게 i/N+1로 찾을 수 있다. 마찬가지로 B는 1,...,N번 사람이 단어를 말한 이후, 이번 차례에서 그 이전에 몇 번 사람까지 말했는지 확인하면 되므로 i%N+1로 찾을 수 있다.

 

 

 

코드(자바) : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        int[] answer = {0, 0};
        char last = words[0].charAt(words[0].length()-1);
        HashSet<String> hs = new HashSet<>();
        hs.add(words[0]);
        for (int i = 1; i < words.length; i++) {
            if (words[i].charAt(0) != last || hs.contains(words[i])) {
                answer[0] = i%n+1;
                answer[1] = i/n+1;
                break;
            }
            last = words[i].charAt(words[i].length()-1);
            hs.add(words[i]);
        }

        return answer;
    }
}

 

 

코드(자바스크립트) : github

/*
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
function solution(n, words) {
    let answer = [0,0];
    let last = words[0][words[0].length-1];
    let hs = new Set();
    hs.add(words[0]);
    for (let i = 1; i < words.length; i++) {
        if (words[i][0] != last || hs.has(words[i])) {
            answer[0] = i%n+1;
            answer[1] = parseInt(i/n)+1;
            break;
        }
        last = words[i][words[i].length-1];
        hs.add(words[i]);
    }
    return answer;
}