코드 챌린지 3일차 - 문자열, 분할 정복과 백트래킹

회문 - 앞뒤 방향으로 볼 때, 같은 순서의 문자로 구성된 문자열
ex ) "1234321", "level"

def is_palindrime(s):
    for i in range(len(s)):
        if s[i]!=s[len(s) -i -1]:
            return False
    return True

def is_palindrome(s):
    return s == s[::-1]

올바른 괄호 문자열 (VPS)

스택을 사용해서 해결하는 것으로 )가 입력될 때마다, 스택에 있는 (를 하나씩 지운다!
(가 없으면 올바른 괄호 문자열이 아니다.
모두 순회한 뒤 스택이 비어있으면 올바른 괄호 문자열이다.

분할정복 - 큰 문제를 작은 문제로 분할하여 작은 문제의 답을 모아 큰 문제의 답을 구한다.
합병 정렬이 분할 정복의 예이다.

def fibo(N) :
    if N <= 2 :
        return 1
    return fibo(N-1) + fibo(N-2)

백트래킹 - 답이 될 수 없는 경우를 탐색 대상에서 제외한다. == 가지치기를 하여 연산량을 유의미하게 줄여준다.

분할 정복과 백트래킹
공통점 - 재귀적인 방식으로 주로 구현된다.
차이점 - 분할 정복은 하위 문제를 해결하고 결과를 결합하지만, 백트래킹은 문제 해결을 위해 모든 가능한 선택을 시도한 후 가능성이 없다고 판단되면 이전 단계로 돌아가거나 이전 결정을 변경한다.

 

문자열 압축 해제

• 시간 제한: 1초

엘리스 토끼는 문자열을 직접 압축 해제하려고 합니다.

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열 중 어떤 부분 문자열은 K(Q)와 같이 압축할 수 있습니다. 이것은 Q라는 문자열이 K 번 반복된다는 뜻입니다. K는 한 자릿수의 정수이고, Q는 0자리 이상의 문자열입니다.

예를 들면, 53(8)은 다음과 같이 압축을 해제할 수 있습니다.

53(8) = 5 + 3(8) = 5 + 888 = 5888

압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하세요.

 

지시사항

입력

• 첫째 줄에 압축된 문자열 S를 입력합니다.
• S의 길이는 최대 50입니다.
• 문자열은 (, ), 숫자로만 구성되어 있습니다.

출력

• 압축되지 않은 문자열의 길이를 출력합니다.

입력 예시

11(18(72(7)))

출력 예시

26

 

a = input()

result = 0
for i in range (len(a)-1, -1, -1 ):
    print(result, i , a[i])
    if(a[i]== ')') :
        continue
    elif(a[i] == '('):
        i = i -1
        if(i<0) :
            break;
        result = result * int(a[i])
        
    
    else :
        result = result +1
    

    
print(result)

처음 짠 코드인데 파이썬에선 i를 건든다고 다음 턴 i를 건들 수 없다는 것을 알았다...........

a = input()

result = 0
i = len(a) - 1

while i >= 0:
    #print(result, i, a[i])
    if a[i] == ')':
        i -= 1
        continue
    elif a[i] == '(':
        i -= 1
        if i < 0:
            break
        result *= int(a[i])
    else:
        result += 1
    i -= 1

print(result)

while로 바꿨습니다...

 

C++

#include <iostream>
#include <string>
using namespace std;

string S;
int len(string str) {
  for (int i = 1; i < str.length(); i++)
    if (str[i] == '(')
      return (i - 1) +
             (str[i - 1] - '0') * len(str.substr(i + 1, str.length() - i - 2));
  return str.length();
}
int main() {
  cin >> S;
  cout << len(S);
}

Python

string = input()

stack = []
depth_result = [0] * 50
depth = 0

for ch in string:
    if ch != ")":
        if ch == "(":
            depth += 1
            depth_result[depth] = 0
        stack += [ch]
    else:
        for i in range(len(stack) - 1, -1, -1):
            if stack[i] == "(":
                num = depth_result[depth]
                for j in stack[i + 1 :]:
                    num += 1
                depth -= 1
                depth_result[depth] += num * int(stack[i - 1])
                del stack[i - 1 :]

                break
print(depth_result[0] + len(stack))

Java

import java.util.Stack;

class Main {
    public static void main(String[] args) {
        String string = new java.util.Scanner(System.in).nextLine();
        
        Stack<Character> stack = new Stack<>();
        int[] depthResult = new int[50];
        int depth = 0;
        
        for (char ch : string.toCharArray()) {
            if (ch != ')') {
                if (ch == '(') {
                    depth += 1;
                    depthResult[depth] = 0;
                }
                stack.push(ch);
            } else {
                for (int i = stack.size() - 1; i >= 0; i--) {
                    if (stack.get(i) == '(') {
                        int num = depthResult[depth];
                        for (int j = i + 1; j < stack.size(); j++) {
                            num += 1;
                        }
                        depth -= 1;
                        depthResult[depth] += num * Character.getNumericValue(stack.get(i - 1));
                        while (stack.size() > i - 1) {
                            stack.pop();
                        }
                        break;
                    }
                }
            }
        }
        System.out.println(depthResult[0] + stack.size());
    }
}