BOJ 백준 2840 : 행운의 바퀴

시작하면서

　이번 문제는 리스트(list) 문제이다. 리스트도 워낙 많이 접하고, 구현해보고, 공부했기 때문에 개념 공부는 따로 글을 올리지 않았다. 바로 문제로 들어가보자.

BOJ 2840 - 행운의 바퀴

​

문제 이해

문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 3가지이다.

• N : 바퀴의 칸 수
• K : 바퀴를 돌리는 횟수
• 글자
• S : 바퀴를 돌리면서 글자가 몇 번 바뀌었는지

​

문제 아이디어

　이 문제는 설명이 많이 난해하다. 그래서 문제를 자세히 읽어야만 했다.

1. 바퀴에는 같은 글자가 두 번 이상 등장할 수 없다.
2. “상덕이가 적어놓은 종이에 해당하는 행운의 바퀴가 없다면” 조건은 다음과 같이 해석할 수 있다.
   • 한 칸에 같은 글자가 겹치면 안 된다.

​

해결

#include <iostream>
#include <list>

using namespace std;

bool InsertWordToList(list<char> *wordList, list<char>::iterator &iter, int S, char word);
bool CheckSameWord(list<char>* wordList, int N);
void PrintAnswer(list<char>* wordList, list<char>::iterator& iter, int N);

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N = 0, K = 0, S = 0;

    char input;
    list<char> wordList;
    list<char>::iterator iter;

    cin >> N >> K;

    wordList.assign(N, '?');
    iter = wordList.begin();

    for (int i = 0; i < K; i++)
    {
        cin >> S >> input;

        if (InsertWordToList(&wordList, iter, S, input) == false)
        {
            cout << "!";
            return 0;
        }
    }

    if (CheckSameWord(&wordList, N) == true)
	{
		PrintAnswer(&wordList, iter, N);
	}
    else
    {
        cout << "!";
    }

    return 0;
}

bool InsertWordToList(list<char> *wordList, list<char>::iterator &iter, int S, char word)
{
    bool bResult = false;

    while (S > 0)
    {
        iter++;
        S--;

        if (iter == (*wordList).end())
        {
            iter = (*wordList).begin();
        }
    }

    if (*iter != '?' && *iter != word)
    {
        bResult = false;
    }
    else
    {
        *iter = word;
        bResult = true;
    }

    return bResult;
}

bool CheckSameWord(list<char>* wordList, int N)
{
    bool bResult = true;
    bool bFlag[26] = { false, };
    list<char>::iterator iter = wordList->begin(); 

    while (N > 0)
    {
        // '?' 는 제외한다.
        if (*iter == '?')
        {
            iter++;
            N--;
            continue;
        }

        // 해당 글자가 이미 들어있었는지 확인한다.
        if (bFlag[(int)*iter - (int)'A'] == true)
        {
            bResult = false;
            break;
        }

        bFlag[(int)*iter - (int)'A'] = true;
        iter++;
        N--;
    }

    return bResult;
}

void PrintAnswer(list<char>* wordList, list<char>::iterator& iter, int N)
{
    while (N > 0)
    {
        cout << *iter;

        if (iter == (*wordList).begin())
        {
            iter = (*wordList).end();
        }

        iter--;
        N--;
    }
}

​

마치며

　이 문제는 개인적으로 마음에 들지 않았다. 리스트를 사용해보기에는 좋은 문제였지만, 문제 설명이 명확하지 않아서 쓸데없이 시간을 낭비했기 때문이다. 정답 비율이 18퍼센트인 이유도 문제가 어려워서라기 보다는 조건이 명확하게 서술되지 않아서임이 큰듯하다.