[LeetCode] C++ 344. Reverse String

https://leetcode.com/problems/reverse-string/

문제

 

문제 분석

- 출력을 거꾸로 하는게 아니라 해당 벡터 내부를 직접 조작해야하므로 맨 뒤에서부터 하나씩 맨 앞으로 넣으면 되지않을까 생각했다.

 

풀이 1

using namespace std;

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i = 0; i < s.size(); ++i){
            s.insert(s.begin() + i, s.back());
            s.pop_back();
        }      
    }
};

insert를 통해 "삽입"을 해버리니까 계속 뒤에 있는 것들이 밀리게 되므로 굉장히 시간이 오래걸렸다.

 

풀이 2

using namespace std;

class Solution {
public:
    void reverseString(vector<char>& s) {
        int len = s.size();
        for(int i = 0; i < len/2; ++i){
            swap(s[i], s[len - i - 1]);
        }      
    }
};

벡터의 사이즈가 바뀌는 것이 아니므로 값만 바꾸었더니 그나마 개선되었다.

 

빠른 풀이

class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(),s.end());
    }
};

vector에 algorithm에 있는 reverse라는 함수를 사용할 수 있어서 이를 활용하는 것이 제일 효율적이었다.

namespace std {
    template<class BidirectionalIterator>
    void reverse(BidirectionalIterator first, BidirectionalIterator last) {
        while ((first != last) && (first != --last)) {
            iter_swap(first, last);
            ++first;
        }
    }
}

reverse함수의 내부설계는 위와 같았다. swap하는 방식은 같지만 최적화가 따로 되어있어서 더 빨랐던 것 같다.