[백준 1784] 골드 2 팰린드롬 인코딩
백준 1784 골드 2 팰린드롬 인코딩
문제 요약
0110 처럼 이진수 형태의 입력이 문자열로 주어지고, 짝수의 팰린드롬을 찾아 뒤쪽 절반을 제거하는 연산을 계속 반복하여 원본 문자열을 최대한 줄였을 때 길이를 출력하는 문제이다.
문제 접근
4개월 전 즈음에 아무 생각 없이 팰린드롬 문제를 해결할 때 사용하는 DP와 DFS 조합으로 접근하였는데 메모리 초과로 실패했다. 문자열이 매 제거 연산 이후 변하기 때문에 당연한 결과였다.
그래서 패턴을 좀 유심히 살펴보았다.
예제로 주어진 0111001 을 살펴보면 011 1001 에서 뒷 1001을 먼저 제거한 후 01110 형태에서 가운데 111중 두개를 뽑아 1 하나를 제거한다. 0110 이 되며 이 형태는 다시 절반으로 줄어들어 10이 되고 답이 2가 된다.
여기서 눈 여겨봐야할 것은 100과 011 이다. 이 패턴들 뒤에 나오는 숫자는 어떤 경우라도 전부 제거가 가능하다. 예를들어
100 1 = 10 이 되면서 제거 100 0 => 뒤쪽 00을 0으로 만들고 100을 10으로 만든다.
즉, 문자열의 가장 뒤에서부터 이런 패턴이 나오는 가장 빠른 위치의 인덱스를 찾는다면, 해당 인덱스 + 3 부터의 부분 문자열은 100 또는 011 등의 패턴이 전혀 포함이 되지 않는다는 것이 보장된다.
01001011 100 1010101 위와 같은 형태가 된다.
이걸 잘 살펴보면 100 뒤의 숫자는 100이나 011의 패턴이 없다면 전부 제거가 가능하다는 것을 알 수 있다.
위의 예를 살펴보면 01001011 100 1010101 => 01001011 10 010101 => 01001011 1001 0101 => 01001011 10 0101 => 01001011 1001 01 => 01001011 10 01 => 01001011 1001 => 01001011 10 로 줄어드는 것을 알 수 있다.
또한 위 두 패턴이 발견 된 이후의 부분 문자열은 제한이 걸리는데, 100의 경우 01이 반복되는 패턴이 나오거나, 0으로만 이루어진 패턴이 나올 수 밖에 없다. 1이 연속되는 패턴은 10 011 에서 011 패턴이 나오기 때문에 성립하지 않으며, 오직 100 010101... 또는 100 101010... 등의 패턴이 올 수 밖에 없다.
011의 경우에도 마찬가지로 1이 연속된 패턴이 나오거나 혹은 10 또는 01이 반복되는 패턴이 나와야한다.
따라서 아래와 같은 로직을 생각할 수 있다.
- 문자열 S에서 100 또는 011 패턴이 나오는 가장 마지막 인덱스를 찾는다. 이걸 idx 라고 하자
- S의 idx+2 이후부터의 부분 문자열을 S에서 제거한다.
- 1과 2를 반복한다.
이렇게 하면 우선 100 또는 011 패턴이 나오는 문자열에 대한 인코딩을 수행할 수 있다. 하지만 문제가 존재한다.
0000 과 같은 문자열은 해당 패턴이 등장하지 않지만, 0으로 줄일 수 있다. 이런 예외 경우는 일반적인 팰린드롬 알고리즘을 이용하여 제거한다.
소스 코드
class Solution {
private String input;
public Solution(BufferedReader reader) throws IOException {
input = reader.readLine();
}
private int findPattern(List<char[]> data) {
for(int i = 0 ; i <= data.size() - 3 ; i++) {
if(data.get(i)[0] == '1' && data.get(i + 1)[0] == '1' && data.get(i + 2)[0] == '0') {
return i;
}
if(data.get(i)[0] == '0' && data.get(i + 1)[0] == '0' && data.get(i + 2)[0] == '1') {
return i;
}
}
return -1;
}
private boolean isReducable(List<char[]> data) {
for(int i = 0 ; i < data.size() - 1 ; i++) {
if(data.get(i)[0] == data.get(i + 1)[0]) {
return true;
}
}
return false;
}
private int findLongestLength(String s) {
List<char[]> listString = new LinkedList<>();
for(char c : s.toCharArray()) {
listString.add(new char[]{c});
}
int index = 0;
while((index = findPattern(listString)) != -1) {
if(index >= 2) {
for(int i = 0 ; i <= index ; i++) {
listString.remove(0);
}
} else if(index == 1) {
listString.remove(0);
listString.remove(0);
} else {
listString.remove(0);
}
}
// 이 과정을 끝내고 나온 문자열 리스트는 모두 같은 수로 이루어져 있거나
// 110 또는 001의 패턴이 존재하지 않는 문자열이다.
while(isReducable(listString)) {
for(int i = 0 ; i < listString.size() - 1 ; i++) {
if(listString.get(i)[0] == listString.get(i + 1)[0]) {
listString.remove(i);
break;
}
}
}
return listString.size();
}
public void run() throws IOException {
// 011 또는 100 뒤에 오는 수는 무조건 제거가 가능하다.
// 예)
// 011 0 이면 팰린드롬이므로 절반 제거 가능 01
// 011 1 이면 1이 중복되기 때문에 1을 두번 제거 가능하다. 01
// 100 0 이면 0이 중복되기 때문에 0을 두번 제거 가능하다. 10
// 100 1 이면 팰린드롬이므로 10 으로 제거 가능
//
StringBuilder sb = new StringBuilder();
// 계산 편의를 위해 문자열을 뒤집고 시작
String reverse = new StringBuilder(input)
.reverse()
.toString();
System.out.println(findLongestLength(reverse));
}
}
문제에 따른 최적화
위 알고리즘은 인코딩 된 최종 결과를 확인할 수 있다. 하지만 문제 자체는 길이만 출력하면 되기 때문에 좀 더 최적화가 가능하다. 아까 살펴보았던 패턴을 다시 생각해보자.
011, 100 이 두 패턴은 다음과 같은 특징이 존재한다.
- 첫 숫자와 두번째 숫자가 다르다.
- 동일한 문자가 연속해서 나온다.
그리고 문자열을 제거할 수 없는 경우는 어떤 경우일까? 01010101 또는 1010101.. 과 같이 서로 다른 숫자가 계속해서 반복되는 경우이다. 이런 패턴 뒤의 문자열들이 모두 제거될 수 있는 경우는 단일 숫자로만 이루어진 값이 들어가는 경우에 해당한다. 01010101 111111111111 => 01010101 01010101 000000000000 => 010101010
따라서 다음과 같은 방식으로 최적화가 가능하다.
class Solution {
private String input;
... // 초기화 및 데이터 입력
public void run() {
int answer = 1; // 문자열의 최소 길이는 1부터 시작
int ptr = 0;
while ((ptr+1) < input.length() && input.charAt(ptr) == input.charAt(ptr+1)) {
// 현재 문자와 다음 문자가 같다면 포인터만 증가 시킨다.
++ptr;
}
while ( ptr+1 < input.length() && input.charAt(ptr) != input.charAt(ptr+1)) {
// 현재 문자와 다음 문자가 다르다면 답을 1 증가시키고 ptr도 1 증가시킨다.
++ptr;
++answer;
}
System.out.println(answer);
}
}