프로그래머스 110 옮기기(월간 코드 챌린지 시즌2)
문제 URL : https://programmers.co.kr/learn/courses/30/lessons/77886
코딩테스트 연습 - 110 옮기기
0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다. x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다. 예를
programmers.co.kr
문제 접근법 :
0또는 1로 이루어진 문자열안에 110만을 뽑아서 마음대로 배치한후 사전순으로 가장 앞에 나오는 문자열을 만드는 문제입니다.
우선 110을 뽑기전에 110을 최적화로 뽑았다고 가정하고
문제를 생각하면 어떤 문자열을 110을 뽑고난후 그문자열을 어떻게 사전순으로 가장 앞서게 만들까요?
잘 생각해보면 문자열은 0과 1로만 이루어져있습니다.
우선 문자 0 은 110보다 앞섶니다. 0뒤에 어떤 무한이 많은수가 0xxxxx 나오든 110보단 앞섭니다.
1은 110보다 앞섭니다.
10 혹은 10x~~ 또한 110보다 앞섭니다.
그렇지만 11과 11x~는 어떨까요?
생각해보면 글자가 3글자 라면 x는 반드시 1입니다. 왜냐하면 우리는 최적화로 110을 뽑았으니까요 110은 존재할수가없지요
하지만 4글자 이상이라면 1110 이나 1111은 110보다 뒤에 위치하기 때문에 110이 앞섭니다.
자 그럼 어떤 문자열 1011110 을 110을 뽑아서 사전순으로 어떻게 바꿀까요?
우린 최적화로 110을 뽑았다고 가정하면 1011110 은 ->1011 로 우선바뀝니다. 그리고 1011
앞 10은 110보다 앞서기때문에 냅두고 뒤 11을 생각하면 11이 앞서지만 잘생각해보시면 11은 예외적으로 110 +11 을 해서 11011을 만드는것이 다사전순으로 빠르게 만듭니다. 즉 11만 예외적으로 110으로 바꿔서 11을 채워서 문자열을 조합해서 만들면됩니다.
혹은 1이었을경우도 1101 을 만드는것이 더빠르기때문에 뒤에숫자가 1이거나 혼자만 1인경우 110을 채워줘서 문자열을 맞춰주면 사전순으로 앞선문자열들을 만들수있습니다.
자그럼 인제 마무리로 110을 어떻게 최적화로 뽑을가요??
이문제는 매우 간단합니다. 뒤에서부터 문자열들을 더한후 뒤에서부터 110인지 확인하면 쉽게 110을 찾을수있습니다.
즉 110을 찾은수에서 110을 2번지웠으면 다중에 다시 110을 2번 끼어넣으면 되기때문에
110을 찾는문제는 백준 문자열 폭발 ->https://congsoony.tistory.com/108
백준 9935 문자열 폭발
문제URL : https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는
congsoony.tistory.com
이문제와 똑같기때문에 이링크를 따라 이문제를 풀어보시길 권해드립니다.
소스코드 :
|
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
|
#include<bits/stdc++.h>
using namespace std;
vector<string> solution(vector<string> s) {
vector<string> answer;
for (string& t : s) {
string res,r;
int cnt = 0;
for (int i = 0; i < t.size(); i++) {//최적화로 110을뽑아냄
res += t[i];
if (res.size() >= 3 && res.substr(res.size() - 3, 3) == "110") {
for (int j = 0; j < 3; j++)
res.pop_back();
cnt++;
}
}
//res는 최적화로 110문자열들만 뽑아냈으니 110에해당하는 사전중 맨앞에 나올수있도록 끼어넣기
for (int i = 0; i < res.size(); i++) {
if (res[i] == '1') {//현재 보는것이 1이고
if(i + 1 >=res.size() ||res[i + 1]=='1')//다음이 1이거나 혹은 문자열이 1개밖에 없다면 110들으 집어넣어야함
while (cnt-- > 0)//110뽑은 개수만큼 집어넣기
r += "110";
}
r += res[i];
}
while (cnt-- > 0)
r += "110";
answer.push_back(r);
}
return answer;
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.