[Algorithm] 백준 - 문자열 잘라내기 (2866번)

문제

[백준] 문자열 잘라내기
(Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #3 4번)

2866번: 문자열 잘라내기

 

 

사용 알고리즘

- 자료구조 (vector, set)

- 문자열

- 정렬

해결방법

• 위에서 아래로 읽어서 단어를 판별한다고 했으므로, 세로방향으로 문자열을 벡터에 저장한다

3 4
alfa
beta
zeta

• 문자열에 다음과 같이 주어지면 vec_alpha 벡터엔 아래와 같이 저장
  [0] abz
  [1] lee
  [2] ftt
  [3] aaa
• 열 개수 - 1 만큼 루프를 돌면서, 벡터에 저장된 요소의 첫번째 값을 지운 단어를 set 집합에 넣어 중복을 방지하고, 완성된 set 집합 내의 요소가 열의 개수와 같은지를 확인한다. (같지 않으면 루프를 중단한다.)
  
  • 원래 arr_alpha 배열에서 가장 윗줄을 지웠다면, vec_alpha 에 저장된 요소들은 첫번째 알파벳이 지워진 bz, ee, tt, aa 가 남게 된다. 이를 set 집합으로 만든 후, 원래 열개수인 4개가 맞는지 체크한다
  • 한 줄 더 지우게 되면, [z, e, t, a] 가 남으므로 똑같이 4개가 되므로 count는 2가 되고 루프가 끝난다.

 

소스코드

사용언어 : c++

#include <iostream>
#include <vector>
#include <string>
#include <set>
 
using namespace std;
 
string arr_alpha[1000];
 
int main()
{
    int R, C;
    vector<string> vec_alpha;
 
    cin >> R >> C;
 
    for(int i=0; i<R; i++) {
        cin >> arr_alpha[i];
    }
 
    for (int i=0; i<C; i++) {
        string str = "";
        for (int j=0; j<R; j++) {
            str += arr_alpha[j][i];
        }
        vec_alpha.push_back(str);
    }
 
    int cnt;
    for (cnt=0; cnt<R-1; cnt++) {
        for (string& s : vec_alpha) {
            s = s.substr(1);
        }
        
        set<string> s(vec_alpha.begin(), vec_alpha.end());
        if (s.size() != C) {
            break;
        }
    }
 
    cout << cnt << endl;
 
    return 0;
}

set<string> s(vec_alpha.begin(), vec_alpha.end());

* 벡터를 집합으로 변환하기 (벡터의 모든 요소를 집합 s로 복제)

* set<자료형> s(vec.begin(), vec.end());

 

한줄평

결론적으론 가로방향, 세로방향 배열을(벡터) 2개만든 셈이 된건데, 하나의 벡터로만 풀 수 있을지..?? 귀찮아서 시도해보진 않았다.