[C++로 풀이] 110 옮기기 (스택, 덱) ⭐⭐⭐

Date: 2021.05.22 Updated: 2021.05.22

카테고리: Programmers

📌 110 옮기기

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이

월간 코드 팰린지 시즌2 : 5월 문제 해설

s 원소마다 DFS 로 풀고 제출했다가 온갖 시간 초과 결과를 마주한 후..⭐ (s의 최대 원소는 백 만개이니 너무나 당연한 결과다. 반성해야 돼..!!!) 프로그래머스 공식 해설을 본 후에 다시 풀이하게 되었다.

스택!!!!!을 사용하면 O(N) 으로 풀 수 있구나.. 작년에 풀었던 주식 가격 문제가 생각났다.(이왕 이렇게 된거 주식 가격 문제도 스택을 사용해 다시 풀이했다. 이때 내가 스택으로 안 풀어 봤네..)

💡 로직

하나의 문자열 s[i]에 대해
- 1️⃣ 모든 “110” 을 찾아 그 개수(count)를 세고 + 제거한다.
  - 이때 스택을 사용하면
    - \(O(3N = N)\) 선형시간으로 찾아낼 수 있으며
    - 111100 👉 110 이렇게 110 제거를 통해 새롭게 만들어지는 110 또한 제거할 수 있게 된다. 11110 까지 스택에 들어있다가 110 은 제거하고 11 만 스택에 남게 되는데 이 상태에서 새로운 0 이 들어오면 다시 110 이 되야 제거 가능. 올바른 괄호 문제처럼 생각하면 된다.
    - 스택의 top 3 개가 “110” 이면 이 3 개를 pop한다. “110” 이 아니라면 현재 문자를 push 한다.
  - 이 과정이 완료된 후 “110” 이 아예 없었다면 answer[i]에 s[i]를 그대로 넣고 종료한다. (이 경우엔 다음 과정 실행하면 안돼서)
- 2️⃣ 스택에 남아 있는 문자들(“110”이 모두 제거된 형태의 문자열)을 꺼내 문자열로 만듬과 동시에 count 개수의 연속된 “110” 문자열을 삽입할 위치가 될 인덱스를 찾는다.
  - 이 삽입 위치가 될 인덱스는 문자열의 오른쪽 끝에서부터 연속된 1 이 시작되는 곳.이 되어야 한다. (그러니, 오른쪽 끝 문자가 0이면 그냥 맨 뒤에 추가)
    - 왜냐하면 “111111…” 연속된 1 보다 “110” 이 사전적으로 더 앞서기 때문이다. 예를 들어 스택에 “1011” 이렇게 남아 있는 상태였다면 count 개수의 연속된 “110” 은 10 ✔ 11 체크한 이 부분에 들어가야 할 것이다.
- 3️⃣ 이전 과정에서 구한 삽입 인덱스에(오른쪽에서부터 연속된 1이 시작되는 곳) count 개수의 연속된 “110”을 삽입하면 된다. 이렇게 완성된 문자열을 answer[i]에 넣고 다음 s[i] 문자열 검사하러 떠나면 된다.

🔥 stack 사용한 풀이

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<string> solution(vector<string> s) {
	vector<string> answer(s.size());

	for (int i = 0; i < s.size(); ++i) {
		stack<char> st;
		int count = 0; // s[i] 문자열에서 만들 수 있는 "110" 개수
		
        // 1️⃣ 모든 "110" 을 찾아 그 개수(count)를 세고 제거한다.
		for (int j = 0; j < s[i].length(); ++j) {
            st.push(s[i][j]);
			if (st.size() >= 3) {
                // 스택의 위에 있는 3 개를 일단 pop 시키자. (스택은 top 을 제외한 중간 원소 임의 접근 불가능하기 때문에 일단 빼내서 볼 수 밖에 없다. ㅠ)
                char three = st.top(); st.pop();
				char two = st.top(); st.pop();
				char one = st.top(); st.pop();

                // 스택의 위에 있는 3 개가 1 1 0 이라면 count 를 증가시킨다. (이미 pop 시켰음)
				if (one == '1' && two == '1' && three == '0') {
					++count;
					continue;
				}
                // 아니라면 다시 스택에 넣어 준다.
				else {
					st.push(one);
					st.push(two);
					st.push(three);
				}
			}
		}
        // "110" 이 하나도 없는 문자열이라면 현재 모습 그대로 answer 에 넣고 끝낸다.
		if (count == 0) {
			answer[i] = s[i];
			continue;
		}

        // 2️⃣ 스택에 남아 있는 문자들("110"이 모두 제거된 형태의 문자열)을 꺼내 문자열로 만듬과 동시에 count 개수의 연속된 "110" 문자열을 삽입할 위치가 될 인덱스를 찾는다. 
        // 스택에 1011 이 있는 상태라면 1👉1👉0👉1 순으로 꺼내지게 되며 각각 str의 맨 앞에 삽입한다. 결론적으로 str은 "1011" 이 되고 인덱스는 2가 된다. 
		int insert_idx = st.size(); // 삽입할 위치가 될 인덱스
		string str = ""; 
        // 스택에서 하나씩 꺼내면서 연속된 1 인지 검사. 인덱스 업뎃. 동시에 꺼낸 문자는 str 맨 앞에 삽입 
		while (!st.empty() && st.top() == '1') {
			--insert_idx; 
			str = st.top() + str;
			st.pop();
		}
        // 연속된 1은 다 빼냈고, 스택에 있는 나머지 문자들 꺼내서 str 맨 앞에 삽입 
		while (!st.empty()) {
			str = st.top() + str;
			st.pop();
		}

        // 3️⃣ 이전 과정에서 구한 삽입 인덱스에(오른쪽에서부터 연속된 1이 시작되는 곳) count 개수의 연속된 "110"을 삽입하면 된다.
		while (count-- > 0) 
			str.insert(insert_idx, "110");
        // 완성! 
		answer[i] = str;
	}

    return answer;
}

🔥 deque 사용한 풀이

다른 분의 풀이 중에 deque을 사용하신 분이 계셔서 적용해보았다. deque 은 여타 배열처럼 [] 써서 중간 원소에 대한 접근하는게 가능하다. 따라서 deque을 쓰면 스택처럼 일일이 빼고난 후에 검사할 필요는 없고, 뒤에 있는 세 원소가 110 인게 확인이 되면 그때서야 제거하면 된다. deque도, stack도 제거 연산이 O(1) 으로 매우 빠른 자료구조다! (deque 은 중간 원소 삭제가 아닌 pop_back, pop_front 한정)

#include <string>
#include <vector>
#include <deque>

using namespace std;

vector<string> solution(vector<string> s) {
	vector<string> answer(s.size());

	for (int i = 0; i < s.size(); ++i) {
		deque<char> dq;
		int count = 0;
		
		for (int j = 0; j < s[i].length(); ++j) {
			dq.push_back(s[i][j]);
			int n = dq.size();
			if (n >= 3 && dq[n - 3] == '1' && dq[n - 2] == '1' && dq[n - 1] == '0') {
				++count;
				dq.pop_back(); 
				dq.pop_back(); 
				dq.pop_back();
			}
		}

		if (count == 0) {
			answer[i] = s[i];
			continue;
		}

		int insert_idx = dq.size();
		string str = "";
		bool end_111 = false;
		for (int i = dq.size() - 1; i >= 0; --i) {
			if (!end_111 && dq[i] == '1') --insert_idx;
			else end_111 = true;
			str = dq[i] + str;
		}

		while (count-- > 0) 
			str.insert(insert_idx, "110");
		answer[i] = str;
	}

    return answer;
}

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️