[SAP/C++] K consecutive identical characters

 

www.geeksforgeeks.org/reduce-the-string-by-removing-k-consecutive-identical-characters/

Reduce the string by removing K consecutive identical characters - GeeksforGeeks

 

연속되는 k개의 알파벳 제거 문제

입력으로 k와 string을 입력받는다.

그 후 string을 검사하여 특정 알파벳이 k회 반복되면, 제거한다.

 

코드 

//
// Created by 이유정 on 2021/04/21.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

vector<pair<char, int>> table;

string solution(int k, string input) {

	if(k==1) return"";

    int count = 1; //최초는 1개
    char Pword = input.at(0); //이전글자
    char Nword;//현재글자
    for (int i = 1; i < input.size(); i++) {
        Nword = input.at(i); //현재글자를 읽어옴
        if (Pword == Nword) { //이전글자와 같음
            count++; //글자수 증가
        } else { //이전글자와 다름
            table.push_back({Pword, count}); // 글자, 갯수를 table에 저장
            count = 1; // 글자수 초기화
        }
        Pword = Nword;
    }
    table.push_back({Pword, count}); //마지막인덱스에 대해서 1회더 실행


    //테이블검사
    int i = 0;
    int index = 0;
    int size = table.size();
    do {

        if (k == table[i].second) {
            input.erase(index, k);
            table.erase(table.begin() + i);
            if (table[i].first == table[i - 1].first) {
                table[i - 1].second = table[i - 1].second + table[i].second; //합치고
                table.erase(table.begin() + i); //다음껄 지워버림(합쳐졌으니깐)
                i = i - 2;//합쳐졌으니까 i 1개줄이기
                index = index - k;
            }

            size = table.size();

        }

        index = index + table[i].second;
        i++;
    } while (i != size + 1);


    return input;

}

int main() {
    string input;
    int k;

    cin >> k;
    cin >> input;
    cout << solution(k, input);

    return 0;

}

약간 비효율적일 수도 있을 것이라고 생각한다...

 

정답)

// C++을 이용한 코드 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
// Basic Approach is to create a Stack that store the
// Character and its continuous repetition number This is
// done using pair<char,int> Further we check at each
// iteration, whether the character matches the top of stack
// if it does then check for number of repetitions
// else add to top of stack with count 1
 
class Solution {
public:
    string remove_k_char(int k, string s)
    {
 
        // k = 1인 경우, 모든 string이 제거됨 
        if (k == 1)
            return "";
            
            
        // 결과 string을 저장할 변수 
        string output = "";
 
        // 스택 pair를 이용해서 생성
        // pair<char,int> 형식으로 -> 각각 char과 반복횟수를 저장
        stack<pair<char, int> > stk;
 
        // string의 길이만큼 반복해줌 
        for (int i = 0; i < s.length(); i++) {
 
            // 스택이 비어있는 경우
            // string에서 해당 index의 word를 반복횟수 1회로 stack에 삽입
            if (stk.empty() == true) {
                stk.push(make_pair(s[i], 1));
            }
            else { //스택이 비어있지 않은 경우 
 
                // 가장 최근에 넣은 값word(top)과 현재 넣으려는 word를 비교해봄
                // current character increase the number of
                // repetitions in the top of stack by 1
                if (s[i] == (stk.top()).first) { //같은경우 
                    stk.push({ s[i], stk.top().second + 1 });//이전 스택에서 반복횟수+1로 스택에 삽입
                    if (stk.top().second == k) { //넣는 중 가장윗부분의 중복횟수가 k가되면
                        int x = k;
                        while (x) { //k회 반복하여 이를 제거 
                            stk.pop();
                            x--;
                        }
                    }
                }
                else { // 다르면 
 
                    // 반복횟수 1로 스택에 넣기 
                    stk.push(make_pair(s[i], 1));
                }
            }
        }
 
        // Iterate through the stack
        // Use string(int,char) in order to replicate the
        // character multiple times and convert into string
        // then add in front of output string
        while (!stk.empty()) { // 스택에 쌓여있는 것을 그대로 빼서 붙이기 
            output += stk.top().first;
            stk.pop();
        }
        reverse(output.begin(), output.end()); // 스택은 거꾸로니까 바꿔서 넣기 
        return output;
    }
};
 
// Driver Code
int main()
{
 
    string s = "geeksforgeeks";
    int k  = 2;
    Solution obj;
    cout << obj.remove_k_char(k, s) << "\n";
 
    return 0;
}
 
// This code has been contributed by Navansh Goel

 

뭐야 코드 짠사람... 똑똑하다...이런방법이...ㅠㅠ

더 열심히 해야지 ㅠ

 

 

이건시행착온데 그냥 붙여놓는다 ㅠ

//
// Created by 이유정 on 2021/04/21.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

string solution(string input) {
//    char preWord = input.at(0);
//    int num = 0;
//    //cout << input.size();
//    for (int i = 1; i < input.size(); i++) {
//        char nowWord = input.at(i);
//        if (preWord == nowWord) {
//            //cout << "same";
//            num++;
//        } else if (nowWord != preWord && num != 0) {
//            //cout << "diff";
//            input.erase(i - num - 1, num + 1);
//            num = 0;
//        }
//
//        preWord = nowWord;
//    }
    char preWord = input.at(0);
    int i = 1;
    int num = 0;
    int size = input.size();
    do {

        char nowWord = input.at(i);
        if (preWord == nowWord) {
            //cout << "same";
            num++;
        } else if (nowWord != preWord && num != 0) {
            //cout << "diff";
            input.erase(i - num - 1, num + 1);
            i = i - (num + 2);
            num = 0;
            size = input.size();
        }

        preWord = nowWord;
        i++;
    } while (i != size);

    return input;


}

int main() {
    string input;

    cin >> input;

    cout << solution(input);
    return 0;

}