C++ 학습/C++ 코딩인터뷰[6장]

[6. 문자열] 6.4 문자열 바꾸고 삭제하기

msugi 2025. 1. 23. 13:37

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "Q6.h"
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec)
{
    os << "[";
    for (size_t i = 0; i < vec.size(); i++)
    {
        os << vec[i];
        if (i != vec.size() - 1)
        {
            os << ", ";
        }
    }
    os << "]";
    return os;
}
 
 cs
 
// main에서 vector 형태로 출력하기위한 기본 셋팅
 

 

Q 6.4 문자열 바꾸고 삭제하기

문자 배열이 주어졌을 때, 이 문자 배열에 다음 규칙을 적용하는 프로그램을 작성하라.

  • 'a'는 'd' 두 개로 바꾼다.
  • 'b'는 삭제한다.

ex) <a,c,d,b,b,c,a>의 배열에 이 규칙을 적용하면 <d,d,c,d,c,d,d> 가 되어야 한다.

배열을 읽으면서 b를 삭제하고 a의 갯수를 읽는다.
거꾸로 a를 dd로 교체한다.
위의 방법의 소스코드와 결과는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 6.4 문자열 바꾸고 삭제하기
#include<vector>
std::vector<int> ReplaceAndRemove(int size, std::vector<int> s)
{
    int write_idx = 0, a_count = 0;
    for (int i = 0; i < size; i++)
    {
        if (s[i] != 'b')
        {
            s[write_idx++] = s[i];
        }
        if (s[i] == 'a')
        {
            a_count++;
        }
    }
 
    int cur_idx = write_idx - 1;
    write_idx = write_idx + a_count - 1;
    const int final_size = write_idx + 1;
    s.resize(final_size);
    while (cur_idx >= 0)
    {
        if (s[cur_idx] == 'a')
        {
            s[write_idx--] = 'd';
            s[write_idx--] = 'd';
        }
        else
        {
            s[write_idx--] = s[cur_idx];
        }
        cur_idx--;
    }
    return s;
}
 cs

배열을 앞뒤로 한번 읽는게 끝이므로 시간 복잡도는 O(n)이다.

1
2
3
4
// main
std::vector<int>TestVector_Int={'a','c','a','a',};
std::vector<int>TestVector=ReplaceAndRemove(TestVector_Int.size(),TestVector_Int);
std::vector<char>TestVector_Char(begin(TestVector),end(TestVector));
std::cout << "6-4 " <<  TestVector_Char<< std::endl; //6-4
 cs

결과