백준 16719번 ZOAC

문제 링크입니다: https://www.acmicpc.net/problem/16719

문자열의 길이가 짧기 때문에 브루트 포스로 O(N^3)에 풀 수 있는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 문자의 길이가 1부터 N까지 출력해야 하므로 반복문을 한번 돌리고

2. 아직 추가하지 않은 문자를 추가해봐야하기 때문에 또 반복문을 돌리고

3. 이미 추가되었던 문자들을 추가해야하기 떄문에 1, 2번과 함께 총 3번의 반복문을 돌려봅니다.

4. 벡터에 추가된 문자들 중 사전순으로 제일 빠른 단어를 출력하고 추가된 문자를 추가되었다고 visited 배열에 표시해줍니다.

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 100;

 

bool visited[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        string s;

        cin >> s;

 

        for (int i = 0; i < s.length(); i++)

        {

                 vector<pair<string, int>> v;

                 //문자의 수를 늘려가며 비교

                 for (int j = 0; j < s.length(); j++)

                 {

                         //아직 추가되지 않은 문자를 넣어봄

                         if (!visited[j])

                         {

                                 string temp;

                                 for (int k = 0; k < s.length(); k++)

                                          //이미 넣었던 문자는 넣어줘야함

                                          if (j == k || visited[k])

                                                  temp += s[k];

                                 v.push_back({ temp, j });

                         }

                 }

                 sort(v.begin(), v.end());

                 cout << v[0].first << "\n";

                 visited[v[0].second] = true;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~