[프로그래머스] 영어 끝말잇기 (12981) - C++

 

https://school.programmers.co.kr/learn/courses/30/lessons/12981

문제 간단 요약

• n명이 영어 끝말잇기를 진행한다.
• 이전 단어의 마지막 문자로 다음 단어를 시작해야 한다.
• 이미 사용한 단어를 다시 말하거나,
• 단어 길이가 1이면 탈락이다.

👉 규칙을 어긴 사람의 번호와 차례를 구하는 문제
👉 끝까지 문제가 없으면 [0, 0] 반환

 

문제의 핵심 포인트

 

이 문제는 알고리즘 자체는 어렵지 않다.
대신 다음 요소들을 꼼꼼하게 처리해야 한다.

1. 이미 사용한 단어인지
2. 끝말잇기 규칙이 지켜졌는지
3. 단어 길이가 1인지
4. 탈락한 인덱스로부터 사람 번호 / 차례 계산

 

사용한 해결 전략

• unordered_set<string>
  → 이미 나온 단어를 빠르게 확인하기 위해 사용
• 반복문으로 단어를 하나씩 검사
• 규칙을 어기는 순간 인덱스를 저장하고 종료

전체 코드

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

using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    unordered_set<string> used;

    used.insert(words[0]);
    answer.push_back(0);
    answer.push_back(0);

    int idx = -1;

    for(int i = 1; i < words.size(); i++){
        // 이미 나온 단어이거나 길이가 1인 경우
        if(used.count(words[i]) || words[i].length() == 1){
            idx = i;
            break;
        }

        // 끝말잇기 규칙 위반
        if(words[i-1][words[i-1].length()-1] != words[i][0]){
            idx = i;
            break;
        }

        // 사용한 단어로 등록
        used.insert(words[i]);
    }

    // 첫 단어가 길이 1인 경우 예외 처리
    if(words[0].length() == 1) idx = 0;

    if(idx != -1){
        answer[0] = idx % n + 1;   // 사람 번호
        answer[1] = idx / n + 1;   // 차례
    }

    return answer;
}

 

---

코드 핵심 설명

1. 중복 단어 체크

used.count(words[i])

• 이미 나온 단어인지 확인
• unordered_set 사용 → 평균 O(1)

---

2. 끝말잇기 규칙 체크

words[i-1][words[i-1].length()-1] != words[i][0]

• 이전 단어의 마지막 문자
• 현재 단어의 첫 문자 비교

---

3. 단어 길이 조건

words[i].length() == 1

• 문제 조건에 명시된 부분
• 자주 실수하는 조건

 문제 조건은 항상 끝까지 읽자…

---

이번 문제에서 했던 실수들 

❌ 1. 반복문 증가 조건 누락

used.insert(words[i]);

• 이 줄을 안 넣어서
• 중복 단어 체크가 제대로 안 됨

 

❌ 2. 인덱스 계산 실수

• % n, / n 계산 헷갈림
• +1 빠뜨림

0-based 인덱스 → 문제는 1-based ( 자주 하는 실수...)  -> 손으로 직접 검증하자!

 

❌ 3. 첫 단어 예외 처리

if(words[0].length() == 1) idx = 0;

• 첫 단어도 규칙 위반 가능
• 루프 밖에서 별도 처리 필요