문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/77886?language=cpp
[월간 코드 챌린지 시즌2]에 나온 문제라고 한다.문제는 짧아서 좋긴 한데, 풀기 어려웠다.
문제 핵심 및 풀이
우선순위 파악
이 문제에서 구해야 하는 것은
입력 숫자에 대해 사전순으로 가장 빠른 것을 찾는 것이다.
앞자리에 '0'이 많을수록 사전순으로 빠르다.110을 삽입할 때,
적어도 기존의 위치보다는 더 앞자리에 있어야 한다.
110을 삽입한다고 생각해 보자.만약 '0' 앞에 삽입한다면
이 자리에 있던 '0'은 원래 자리보다 3칸이나 더 뒤로 미뤄지는 것이다.
그래서 '0'이 있다면 뒤에 삽입하는 것이 사전순으로 이득일 것이다.
이런 식의 사고를 이어가 보면
110을 삽입하는 곳 뒤에는 0이 있으면 안 된다. 라는 결론에 이른다.
이런 식으로 110을 뽑아내고도
아래와 같은 순서를 유지하는 입력이 있다고 생각해 보자.
110을 삽입할 수 있는 곳은 체크된 곳 중 하나다.
한 위치씩 넣어보면서 시뮬레이션을 돌려보자.
가장 오른쪽 2개의 경우를 제외하고선 전부 1개 이상의 '0'이 뒤로 밀린다.
이는 곧 사전순으로 가장 빠른 것이 아님을 의미한다.
오른쪽의 2개의 경우는 모두 그 위치를 기점으로 0이 존재하지 않는다.
그리고 당연히 둘 중 사전순으로 빠르게 하기 위해선 오른쪽에서 두 번째에 넣어야 한다.
이는 뽑을 수 있는 110의 개수가 몇 개든 상관없이 똑같이 적용되는 논리다.
이것도 시뮬레이션 돌려보면 알겠지만,
하나의 110 쌍을 넣고, 넣을 위치를 찾아보면 자동으로 110 뒤에 이어 붙이는 것이 나온다.
그래서 신경 써줘야 하는 것은 110의 개수뿐이다.
나중에 만들어지는 110은 어떻게 하지?
한 가지 걸림돌은 아래와 같은 경우가 생길 수 있다는 것이다.
2가지 문제점이 있다.
1. 나중에 생겨난 110을 어떻게 찾아낼 것인가?
2. 한번 옮겼던 110을 어떻게 넘길 것인가?
위 2가지 문제점을 한 번에 해결하는 방법은 스택을 사용하는 것이다.
스택을 사용하면 순서를 유지한 채 가운데의 숫자를 뺄 수 있다.
그 방법은 앞에서부터 하나씩 스택에 넣으면서 검사하는 것이다.
그리고 110의 개수를 한 번에 구한다
.그렇게 하면 중복이 될 일은 절대 없다.
스택을 이용한 순서 정렬 방법
알고리즘은 다음과 같다.
1.
인덱스를 순차적으로 검사한다.
2.
현재 인덱스와 스택에서 2개를 꺼내서 110이 만들어지는지 확인한다.
2-1.
만들어진다면 110의 개수 + 1을 한다.
2-2.
그렇지 않다면, 스택에서 꺼낸 요소와 인덱스의 숫자를 다시 넣는다.
3.
끝까지 다 탐색하면,
이제 가장 뒤에 있는 0의 위치를 찾는다.
4.
해당 위치에 찾은 110의 개수만큼 이어 붙인다.
이를 위의 들었던 예시로 시뮬레이션 돌리면 다음과 같다.
위의 예시를 이용하여 스택으로 한번 해보자.
순차적으로 탐색하는데, 스택에서 2개를 꺼낼 수가 없기 때문에 그냥 넣어준다.
스택에서 2개를 꺼내고 이번에 탐색하는 인덱스와 함께 110을 만족하는지 확인한다.
이때, 순서가 틀리지 않도록 유의해야 한다.
여기서는 만족하지 않았기 때문에 이번에 탐색한 인덱스를 포함하여 다시 스택에 넣었다.
순차적으로 진행하다가, 이번에는 110과 일치한다.
그렇다면 스택에서 뽑아낸 2개를 삭제하고, 해당 인덱스는 스택에 넣지 않는다.
그리고 110 쌍의 개수를 1개 더해준다.
바로 위와 동일한 원리로 110이 발견됐으니 스택에서 2개를 지워준다.
이렇게 되면 총 110의 개수는 2개가 된다.
마지막까지 탐색을 마치면 스택의 상태는 아래와 같이 된다.
이제 이를 이용해서 가장 끝에 있는 0의 위치를 알아낸다.
그리고 그 뒤에 110을 찾아낸 개수만큼 붙인다.
이어 붙이면 위와 나오게 되는데, 이게 정답이 된다.
이제 이 과정을 코드로 옮기기만 하면 된다.
실수하기 쉬운 부분
탐색이 끝난 후 스택에 남아있는 값을 꺼내준 후, 문자열들을 한번 뒤집어 줘야 한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
// 스택을 쌓고, 110의 개수를 구함
int stackAndFind(stack<char>& s, string numbers){
int result = 0; // 개수
// 순차 탐색
for(int i = 0; i < numbers.length(); i++){
char third = numbers[i];
// 스택에 들어있는게 2개 미만이라면 넣기만함
if(s.size() < 2) s.push(third);
else{
// 스택에서 2개를 꺼냄
char second = s.top();
s.pop();
char first = s.top();
s.pop();
// 110 쌍인지 확인하여 맞으면 result+1
if(first == '1' && second == '1' && third == '0') result++;
else{
// 아니라면 다시 넣음
s.push(first);
s.push(second);
s.push(third);
}
}
}
return result;
}
// 숫자를 바꾸는 로직 함수
string changeNumbers(string numbers){
// 애초에 110을 찾을 수 없다면 원래 숫자를 반환
if(numbers.find("110") == string::npos) return numbers;
stack<char> s;
string result = ""; // 최종 반환할 값
int count = stackAndFind(s,numbers);
int idx = s.size(); // 가장 마지막 0 뒤에 넣기 위해 인덱스를 찾음
bool flag = false;
while(!s.empty()){
char cnt = s.top();
s.pop();
if(!flag){
if(cnt == '0') flag = true;
else idx--;
}
result.push_back(cnt);
}
// 스택에 남아있는걸 꺼내주고 뒤집어줘야함
reverse(result.begin(),result.end());
// 110의 개수만큼 idx 뒤에 붙임
for(int i = 0; i < count; i++){
result.insert(idx,"110");
}
return result;
}
vector<string> solution(vector<string> s) {
vector<string> answer;
for(auto numbers : s){
answer.push_back(changeNumbers(numbers));
}
return answer;
}
Java 구현 코드
↓
import java.util.*;
class Solution {
public String[] solution(String[] s) {
String[] answer = new String[s.length];
for(int i = 0; i < s.length; i++){
String numbers = s[i];
answer[i] = changeNumbers(numbers);
}
return answer;
}
// 숫자를 바꾸는 로직 함수
public String changeNumbers(String numbers){
// 애초에 110을 찾을 수 없다면 원래 숫자를 반환
if(!numbers.contains("110")) return numbers;
Stack<Character> s = new Stack<>();
// 문자열을 붙여야하기 때문에 StringBuilder 사용
StringBuilder sb = new StringBuilder();
int count = stackAndFind(s,numbers);
int idx = s.size(); // 가장 마지막 0 뒤에 넣기 위해 인덱스를 찾음
boolean flag = false;
while(!s.isEmpty()){
char cnt = s.pop();
if(!flag){
if(cnt == '0'){
flag = true;
}
else{
idx--;
}
}
sb.append(cnt);
}
sb.reverse(); // 스택에 남아있는걸 꺼내주고 뒤집어줘야함
// 110의 개수만큼 idx 뒤에 붙임
for(int i = 0; i < count; i++){
sb.insert(idx,"110");
}
return sb.toString();
}
// 스택을 쌓고, 110의 개수를 구함
public int stackAndFind(Stack<Character> s, String numbers){
int count = 0; // 개수
// 순차 탐색
for(int i = 0; i < numbers.length(); i++){
char third = numbers.charAt(i);
// 스택에 들어있는게 2개 미만이라면 넣기만함
if(s.size() < 2){
s.push(third);
}
else{
// 스택에서 2개를 꺼냄
char second = s.pop();
char first = s.pop();
// 110 쌍인지 확인하여 맞으면 count+1
if(first == '1' && second == '1' && third == '0'){
count++;
}
else{
// 아니라면 다시 넣음
s.push(first);
s.push(second);
s.push(third);
}
}
}
return count;
}
}↑
시행착오
스택을 사용하는 방법은 생각조차 못했다.
문자열을 이용해서 처리하다가
시간초과, 메모리초과로 실패했다.
순서 관련된 문제가 나오면 스택의 가능성도 항상 고려해야겠다.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me