[LeetCode] 2000. Reverse Prefix of Word

https://leetcode.com/problems/reverse-prefix-of-word/description/

leetcode - Reverse Prefix of Word

문제 유형 : 문자열 처리, 스택, 큐

문제 난이도 : Easy

 

문제

Given a 0-indexed string word and a character ch, reverse the segment of word that starts at index 0 and ends at the index of the first occurrence of ch (inclusive). If the character ch does not exist in word, do nothing.

• For example, if word = "abcdefd" and ch = "d", then you should reverse the segment that starts at 0 and ends at 3 (inclusive). The resulting string will be "dcbaefd".

Return the resulting string.

 

문자열 word와 문자 ch가 주어진다.

인덱스 0부터 ch까지(ch를포함)의 전위부를 뒤집은 문자열을 반환하시오.

ch가 word에 없으면, 아무것도 안하면 됩니다.

 

풀이

문자열 뒤집기를 위한 스택 하나,

ch 이후를 담을 큐 하나를 만든다.

ch가 나올때까지는 스택에 담고, 이후에는 큐에 담는다.

만약 ch를 스택이 문자열을 다 담는동안 못찾았다면, 원본 문자열을 반환한다.

 

스택에서 꺼내서 빈 문자열에 붙이고, 그 뒤에는 큐에서 꺼내서 붙인다.

스택, 큐 대신에 부분 문자열 함수를 이용해도 좋다.

 

코드

C++

class Solution {
public:
    string reversePrefix(string word, char ch) {
        stack<char> st;
        queue<char> q;
        bool flag = false;
        int idx = 0;
        while(idx < word.size()) {
            st.push(word[idx]);
            if(word[idx] == ch) {
                flag = true;
                break;
            }
            idx++;
        }
        if(!flag) return word;
        idx++;
        while(idx < word.size()) {
            q.push(word[idx]);
            idx++;
        }

        string res = "";
        while(!st.empty()) {
            res += st.top();
            st.pop();
        }

        while(!q.empty()) {
            res += q.front();
            q.pop();
        }

        return res;
    }
};