lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read



제한사항

  • 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
  • words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
  • 단어의 길이는 2 이상 50 이하입니다.
  • 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
  • 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
  • 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
  • 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.


입출력 예시

Input-1
78
Output-1
83

Input-2
15
Output-2
23


문제 풀이

끝말잇기 배열에서 n번째마다 돌아가며 n번째 사람의 끝말잇기가 틀렸을 때를 알아야 한다.
그리고 이전 끝말잇기 단어의 마지막 글자와 현재 끝말잇기 단어의 첫글자가 같은지도 검증해야 한다.

n번째 순서 구하기

먼저, 끝말잇기 단어 배열을 순회하며 n명이 돌아가며 단어를 주고받도록 해야한다.
예시의 words배열의 경우 9번의 단어를 주고받는데 3명이서 돌아가며 주고받는다.
n이 3이고, 9번 끝말잇기 단어를 주고받는다고 하면 i를 n으로 즉, 3으로 나눈 나머지를 통해 알 수 있다.

  • n번째 사람 : i % n

실패한 사람 및 차례 구하기

n명이 돌아가며 단어를 주고받는 것을 구했으니, 몇번째 차례에서 끝말잇기를 누가 실패했는지 알아야 한다.
만약 n이 3이고, 끝말잇기 단어를 9번 주고받았다면, 총 3명이 3번씩 주고받는다. 즉, i를 n으로 나눈 나머지가 0일 때 차례가 뒤바뀐다.

  • n번째 차례 : i%n == 0

그리고 이전 단어의 마지막 글자와 현재 단어의 첫글자를 비교하여 다르다면 실패한 것으로 간주하자.
또한, HashSet에 끝말잇기 단어를 담으며, 중복으로 끝말잇기 단어가 나올 경우 실패한 것으로 간주하자.

위에서 정한 내용을 코드로 작성해보자.

1
2
3
4

int num = 0;
int cnt = 0;
int fail = 0;
HashSet<String> set = new HashSet<>();

먼저 사용할 변수와 자료구조를 초기화하였다.
num의 경우는 n번째 사람을 저장하고, cnt는 몇번째 차례인지, fail은 실패한 사람을 담는다.
HashSet은 끝말잇기 단어를 담을 자료구조이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

for(int i=0; i<words.length; i++) {
    num = i%n;
    if(num == 0) cnt++;
    if(set.contains(words[i])) {
        fail = num+1;
        break;
    }
    else set.add(words[i]);
    if(i>0) {
        String beforelastLetter = words[i-1].substring(words[i-1].length()-1, words[i-1].length());
        String nowFirstLetter = words[i].substring(0,1);
        if(!beforelastLetter.equals(nowFirstLetter)) {
            fail = num+1;
            break;
        }
    }
}

끝말잇기 배열을 순회하며 num에 몇번째 사람인지를 담아두고, num이 0이라면 한바퀴 차례를 돌았기에 cnt 횟수를 증가시킨다.
그리고 끝말잇기 단어를 Hashset에 저장하며, 중복 단어가 나왔다면 fail에 실패한 사람을 담고 반복문을 탈출한다.
마지막으로 이전단어의 마지막글자와 현재단어의 첫글자를 비교하고 다르다면 fail에 실패한 사람을 담고 반복문을 탈출한다.

작성한 코드를 제출하니 모든 테스트케이스를 정상적으로 통과하였다.


작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] words = {"tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"};

        long start = System.currentTimeMillis();
        solution(n,words);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }

    public static int[] solution(int n, String[] words) {
        int num = 0;
        int cnt = 0;
        int fail = 0;
        HashSet<String> set = new HashSet<>();

        for(int i=0; i<words.length; i++) {
            num = i%n;
            if(num == 0) cnt++;
            if(set.contains(words[i])) {
                fail = num+1;
                break;
            }
            else set.add(words[i]);
            if(i>0) {
                String beforelastLetter = words[i-1].substring(words[i-1].length()-1, words[i-1].length());
                String nowFirstLetter = words[i].substring(0,1);
                if(!beforelastLetter.equals(nowFirstLetter)) {
                    fail = num+1;
                    break;
                }
            }
        }
        if(fail==0) cnt=0;
        int[] answer = {fail, cnt};
        return answer;
    }
}

회고

  • i%n 연산을 통해 n번째 사람마다 돌아가며 끝말잇기 배열에 접근할 수 있었고, HashSet을 활용해 중복단어를 적절히 거를 수 있었다.

You may also enjoy