[프로그래머스] 영어 끝말잇기 C++ 풀이

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

프로그래머스

 

전체 코드

#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    map<string,bool> m;
    m.insert({words[0],true});
    string recent=words[0];
    
    for(int i=1;i<words.size();i++)
    {
        if((recent[recent.length()-1]!=words[i][0])||m.find(words[i])!=m.end())
        {
            answer.push_back((i%n)+1);
            answer.push_back((i/n)+1);
            break;
        }
        else
        {
            m[words[i]]=true; 
            recent=words[i];
        }
    }
    
    if(answer.size()==0)
    {
        answer.push_back(0);
        answer.push_back(0);
    }
    
    return answer;
}

 

풀이 방법

map을 이용해 중복된 단어인지 체크합니다.

반복문을 통해 words를 돌며 최근 단어(recent)와 현재 단어(i)가 끝말잇기가 가능한지 확인합니다.

위의 두 조건중 하나라도 문제가 있으면 끝말잇기는 종료합니다.

이때 탈락자의 번호는 i%n에 1을 더함으로써 구할 수 있습니다.

자신의 몇번째 차례인지는 i/n에 1을 더함으로써 구해집니다.

 

 

+ map에 관한 이야기

 

이상하게 아래의 코드로 작성하면 map에 이미 존재하는지 확인이 안 됩니다.

삽입시 아래의 두 방법으로 insert하고

m.insert(make_pair(words[i],true));
m.insert({words[i],true});

 

중복 체크할 때 [] 연산으로 앞전에 삽입된 적이 있는지 확인하면

if(...||m[words[i]]==true)
{
	...
}

 

앞전에 이미 나온 단어임에도 불구하고 

아래의 테스트 케이스에서

["land", "dream", "mom", "mom", "ror"]

2번째 mom의 출현 시 if문에 걸리지 않습니다.

 

하지만 또 삽입할 때 위의 두 방법 말고 아래의 방식으로 하면 중복 체크가 m[words[i]]==true로 가능합니다.

m[words[i]]=true;

 

중복을 확인할 때 아래의 코드로 확인하면 삽입의 3가지 방법 모두 체크가 가능합니다.

m.find(words[i])!=m.end()

 

간단히 말해,

insert로 map에 삽입한 것은 [ ] 연산으로 중복 확인에 문제가 있습니다.

 

**********************************************************************************************************

=> 

 

map에 넣기 전 []으로 확인하고, 넣고 []으로 확인을 해봤더니

cout << m[words[i]]<<" ";
m.insert(make_pair(words[i], true));
cout << m[words[i]] << endl;

넣기 전에도 false, 넣은 후에도 false로 나온다.

[]와 insert는 방식이 다르기에 이런 상황이 발생하는 것 같다.

 

삽입을 [ ]으로 해봤더니 존재 유무가 잘 확인된다.

cout << m[words[i]]<<" ";
m[words[i]] = true;
cout << m[words[i]] << endl;

앞으로 삽입, 조회를 insert와 find를 같이 쓰거나 []로 통일하거나 해야겠다.

 

문제 발생 이유

==>  [ ]의 경우 조회만 하더라도 삽입이 이루어지기에 위의 문제가 발생한것이였다..!