vector와 string 추가 메서드 - 짝지어 제거하기(프로그래머스)

vector

#include <vector>

1. 마지막 원소 제거: vec.pop_back();

2. 범위 제거: vec.erase(start_iter, end_iter); // iterator 사용!!, end 전까지 삭제

원래 벡터 자체가 변한다! 따로 반환할 필요x

ex)

int main(){

    vector<int> vec = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    for(int i=0; i<vec.size(); i++){
        cout << vec[i] << ' ';
    }
    cout << '\n';

    // (1) pop_back();
    vec.pop_back();

    for(int i=0; i<vec.size(); i++){
        cout << vec[i] << ' ';
    }
    cout << '\n';
    // => 0 1 2 3 4 5 6 7 8 

    // (2) erase(start, end);
    auto iter = vec.begin();	// 먼저 iterator을 구하자.
    // end 전까지 삭제
    vec.erase(iter+0, iter+ 3); // 0번 인덱스부터 2번 인덱스까지 삭제

    for(int i=0; i<vec.size(); i++){
        cout << vec[i] << ' ';
    }
    cout << '\n';
    // => 3 4 5 6 7 8
}

3. 특정 원소 가리키기: vec.begin();, vec.end();

auto iter = vec.begin(); // 첫번째 원소를 가리킴
auto iter = vec.end(); // 마지막 다음을 가리킴

4. 삽입하기->나머지는 뒤로 밀림: vec.insert(start_iter, 삽입할 요소);

vector<int> vec = {3, 4, 5, 6, 7, 8, 9};
auto iter = vec.begin();

vec.insert(iter+0, 2);	// 2 3 4 5 6 7 8 9 / size = 8
vec.insert(iter+0, 1);	// 1 2 3 4 5 6 7 8 9 / size = 9

string

#include <string>

1. 문자열 부분 삭제: str.erase(start, size);

start 인덱스부터 size 만큼 삭제
본래의 문자열 자체에서 삭제된다.

2. 부분 문자열 반환: str.substr(start, size);

원래 문자열은 변하지 않는다. 따로 사용하려면 반환하여 다른 문자열 변수가 받아야 함.

start 인덱스부터 size만큼 잘라 반환한다.
ex)

int main(){

    string str = "0123456789";
    string str2;
	
    str2 = str.substr(0,3);

    cout << str << '\n'; 	// 0123456789
    cout << str2 << '\n';	// 012 (size == 3)	
}

3. 매개변수로 들어온 문자열과, 내 문자열 중 일치하는 게 있는지 확인: str.find(str2);

str 문자열 중 str2 문자열이 포함되어 있다면 시작 인덱스를 반환한다.

int main(){

    string str = "0123456789";
    
    string str3 = "456";

    cout << str.find(str3) << '\n'; // => 4번 인덱스 부터 시작

    string str4 = "468";
    int n = str.find(str4);
    cout << n  << '\n';   // -1
}

4. 비교 연산자 (==)

c++에서 string 문자열일 경우 == 연산자 사용 가능. 연산자 오버라이딩

5. compare()

string str1 = ..
string str2 = ..

if(str1.compare(str2) == 0)
    // str1 == str2
else if(str1.compare(str2) < 0)
    // str1이 str2보다 사전적으로 앞에 있음
    // str1: AAA, str2: BBB
else if(str1.compare(str2) > 0)
    // str1이 str2보다 사전적으로 뒤에 있다. 
    // str1: CCC, str2: BBB

6. operator +

string str1 = "AAA";
string str2 = "BBB";

str1 += str2; // => str1 == "AAABBB"

7. clear()

str.clear();
length는 0이 되고, capacity는 그대로 남게됨.

8. reverse() (in argorithm 헤더)

string str = "BlockDMask";
cout << str << endl;            //"BlockDMask";
reverse(str.begin(), str.end());
cout << str << endl;            //"ksaMDkcolB";

이 reverse() 메서드는 문자열 뿐 아니라 벡터에도 적용가능 !

9. transform() (int argorithm 헤더)

소문자 <===> 대문자

// to 대문자
transform(str.begin(), str.end(), str.begin(), ::toupper);
// to 소문자 
transform(str.begin(), str.end(), str.begin(), ::tolower);

추가 메서드 참고 사이트: https://blockdmask.tistory.com/338?category=249379

---

짝지어 제거하기(프로그래머스)

=> 최소 O(NlogN)의 시간복잡도로 해결해야 함.

#include <iostream>
#include<string>
#include<vector>
using namespace std;

int solution(string s)
{
    int answer = -1;

    /*
    O(n)
    문자를 하나 넣는다.
    전에것을 확인한다. 
    만약 같다면 전에 것과 함께 삭제한다.       // like stack
    */
    
    int sSize = s.size();
    
    /* 
    * string 활용 방식, str.erase(start_index, size);
    */ 
    
    string stk = "";    // 스택과 같다 
    int beforeIdx = -1;
    
    for(int i=0; i< sSize; i++){                    // O(N)
        char now = s[i];

        if(beforeIdx < 0){  // 비교할 전 요소 없음 => 그냥 push 
            beforeIdx++;
            stk += now;
        }
        else{               // 전에 것이 있는 경우
            // 전에 것과 같다면
            if(now == stk[beforeIdx]){
                //stk.erase(beforeIdx, 1);  // (1) // start 인덱스(beforeIdx)부터, size=1 만큼 erase
                //stk.pop_back();		  // (2)
                stk.erase(stk.size()-1, 1); // (3) , (1) = (2) = (3) 모두 같은 동작, 단 str.erase는 본래의 문자열을 바꾸진 않는다.
                beforeIdx--;   
            }
            // 전에 것과 다르다면
            else {
                stk += now;
                beforeIdx++;
            }
        }
    }
    
    //cout << "check " << stk << '\n';
    if(stk.size() == 0)
        answer = 1;
    else
        answer = 0;
        
    /* 
    * vector 활용 방식
    vector<char> stk; 
    //auto iter = stk.begin();
    int beforeIdx = -1; 
    for(int i=0; i<sSize; i++){
        char now = s[i];

        if(beforeIdx < 0){
            beforeIdx++;
            stk.push_back(now);
        }
        else{   // 전에 것이 있는 경우
            // 전에 것과 같다면
            if(now == stk[beforeIdx]){

                //stk = stk.erase(beforeIdx, stk.end())); (x)
                
                auto iter = stk.begin();	// vector는 iterator 필요
                stk.erase(iter+beforeIdx, iter+beforeIdx+1);
                beforeIdx--;   
            }
            // 전에 것과 다르다면
            else {
                stk.push_back(now);
                beforeIdx++;
            }
        }
    }
    
    if(stk.size() == 0)
        answer = 1;
    else
        answer = 0;
    *
    */
    
    
    return answer;
}

---

cf) 가장 간단하게 STL의 stack 템플릿 클래스 사용

#include <iostream>
#include<string>
#include <stack>

using namespace std;

int solution(string s)
{
    stack<char> stk;
    
    int len = s.size();
    for(int i=0; i<len; i++){
        char c = s[i];
        
        // 스택이 비어있다면
        if(stk.empty())
            stk.push(c);
        else{
            int beforeChar = stk.top();
            
            // 이전에 문자와 같다면
            if(beforeChar == c)
                stk.pop();
            else
                stk.push(c);
        }
    }
    
     if(stk.empty())
            return 1;
        else
            return 0;
}