[PCCP] Lv2: 영어 끝말잇기(12981) 해설

문제

- 문제 링크: 영어 끝말잇기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: words의 길이

- words의 길이만큼 반복문을 순회하고 각 연산의 시간 복잡도는 O(1)이므로 최종 시간 복잡도는 O(N)

#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer(2, 0);
    unordered_set<string> usedWords;
    
    usedWords.insert(words[0]);
    
    // 두 번째 단어부터 끝까지 반복
    for (int i = 1; i < words.size(); ++i) {
        // 단어가 이미 사용되었거나, 끝말잇기 규칙에 맞지 않는 경우
        if (!usedWords.insert(words[i]).second || words[i].front() != words[i-1].back()) {
            // 플레이어 번호와 턴 번호 저장 후 바로 반환
            answer[0] = i % n + 1;
            answer[1] = i / n + 1;
            return answer;
        }
    }
    
    return answer; // 중간에 탈락하는 플레이어가 없으면 [0, 0] 반환
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: words의 길이

- words의 길이만큼 반복문을 순회하고 각 연산의 시간 복잡도는 O(1)이므로 최종 시간 복잡도는 O(N)

import java.util.HashSet;

class Solution {
    public int[] solution(int n, String[] words) {
        // 이미 사용한 단어를 저장하는 set
        HashSet<String> usedWords = new HashSet<>();
        // 이전 단어의 마지막 글자, 최초 상태는 첫 번째 사람이 말하는 첫 번째 글자로 초기화
        char prevWord = words[0].charAt(0);
        
        for (int i = 0; i < words.length; ++i) {
            // 이미 사용한 단어이거나 첫 글자가 이전 단어와 일치하지 않으면
            if (usedWords.contains(words[i]) || words[i].charAt(0) != prevWord) {
                // 탈락하는 사람의 번호와 차례를 반환
                return new int[]{(i % n) + 1, (i / n) + 1};
            }
            // 사용한 단어로 추가
            usedWords.add(words[i]);
            // 이전 단어의 마지막 글자 업데이트
            prevWord = words[i].charAt(words[i].length() - 1);
        }
        
        // 모두 통과했을 경우 반환값
        return new int[]{0, 0};
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: words의 길이

- words의 길이만큼 반복문을 순회하고 각 연산의 시간 복잡도 O(1)이므로 최종 시간 복잡도: O(N)

def solution(n, words):
    used_words = set() # 이미 사용한 단어를 저장하는 set
    prev_word = words[0][0] # 이전 단어의 마지막 글자
    
    for i, word in enumerate(words):
        # 이미 사용한 단어거나 첫 글자가 이전 단어와 일치하지 않으면
        if word in used_words or word[0] != prev_word:
            # 탈락하는 사람의 번호와 차례 반환
            return [(i % n) + 1, (i // n) + 1]
        used_words.add(word) # 사용한 단어로 추가
        prev_word = word[-1] # 이전 단어의 마지막 글자 업데이트
    return [0, 0] # 모두 통과했을 경우 반환값

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: words의 길이

- words의 길이만큼 반복문을 순회하고 각 연산의 시간복잡도: O(1)

- 최종 시간 복잡도: O(N)

function solution(n, words) {
    usedWords = new Set(); // 이미 사용한 단어를 저장하는 set
    prevWord = words[0][0]; // 이전 단어의 마지막 글자
    
    for (let i = 0; i < words.length; ++i) {
        word = words[i];
        
        // 이미 사용한 단어거나 첫 글자가 이전 단어와 일치하지 않으면
        if (usedWords.has(word) || word[0] != prevWord) {
            // 탈락하는 사람의 번호와 차례를 반환
            return [i % n + 1, Math.floor(i / n) + 1];
        }
        
        usedWords.add(word); // 사용한 단어로 추가
        prevWord = word.slice(-1); // 이전 단어의 마지막 글자 업데이트
    }
    return [0, 0]; // 모두 통과했을 경우 반환값
}

solution 2)

import

solution 3)

import