[백준][C++] 16719번: ZOAC <186>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

16719번: ZOAC

 

생각의 흐름

와 이번문제 나는 어려웠다.

단순하게 A부터 찾아서 추가하는 식으로 해결하기도 어렵다. 왜냐하면 문자는 중복이 가능하기 때문이다.

A가 2개 이상이라면 어디부터 시작해야 할까? 이또한 문제이다...

 

따라서 나는 다음과 같은 알고리즘으로 문제를 해결해 나갔다. (다른분의 풀이를 참고하였다)

1) 문자열의 길이가 1일때, 2일때, 3일때, ... , N일때 각각의 경우에서 가능한 경우들을 구해야 한다.

예를 들어 길이가 4인 case를 구한다고 해보자.

 

2) 새롭게 추가하는 문자는 아직 추가한적 없는 문자열 중 하나를 추가한다.

이전에 길이가 3일때의 사용한 문자들을 제외하고, 새로운 문자를 하나 선택하는 것 이다.

 

3) 이미 추가했던 문자들 또한 추가.

for문을 돌면서 차례대로 temp라는 string변수에 이전에 사용했던 문자 + 이번에 사용할 문자를 추가한 문자열을 추가해 준다.

 

4) 그 값들중 가장 사전순으로 빠른것을 출력해 준다.

 

예를 들어보자, 문제의 다음 예를 보자.

STARTLINK

이미 AIK 가 추가된 상황이다. 4번째 문자를 선택할 순서이다.

따라서 추가 가능한 예시는 SAIK, TAIK, RAIK, TAIK, LAIK, NAIK 가 있다.

(위 예시는 사용했다는 의미이지, 저 순서대로 출력한다는 의미가 아니다. 단순하게 사용한 문자들을 선택한것 이다)

 

이제 vector에 사용한 문자인 temp와 추가된 문자의 위치를 pair로 묶어서 삽입한다.

이후 정렬했을때 맨 앞에서 나오는 것을 출력해주면 된다.

 

이번 방식은 최대 길이가 100이기 때문에 완전탐색 방식으로 해결이 가능한것 이다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;

#define MAX 101

string str;
bool visited[MAX];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> str;

    int len = str.length();
    for(int i = 0; i < len; i++){
        vector<pair<string, int>> vec; // 각 case를 저장해둘 vector

        for(int j = 0; j < len; j++){
            if(!visited[j]){ // 이전에 사용한적이 없는 문자라면
                string temp;
                for(int k = 0; k < len; k++){ // 이전에 사용한 문자들 추가
                    if(k == j || visited[k]){
                        temp += str[k];
                    }
                }
                vec.push_back({temp, j});
            }
        }
        sort(vec.begin(), vec.end());
        cout << vec[0].first << "\n";
        visited[vec[0].second] = true;
    }

    return 0;
}