[백준] 10597 순열장난 python, c/c++

https://www.acmicpc.net/problem/10597

10597번: 순열장난

백트래킹 문제이다. 한글자, 두글자씩 읽어서 확인하고 마지막까지 순회했을 때 (포커의 스트레이트 같이) 모든 값이 이어지는지 확인한다.

 

# import sys; input = sys.stdin.readline
def backtrack(ind, limit):
    global s, stack
    if ind == limit:
        max_v = max(stack)
        for i in range(1, max_v+1):
            if visit[i] != 1:
                return
        print(*stack)
        exit(0)
        # return
    tmp = int(s[ind])
    if not visit[tmp]:
        visit[tmp] = 1
        stack.append(tmp)
        backtrack(ind + 1, limit)
        visit[tmp] = 0
        stack.pop()

    if ind + 2 > limit: return
    tmp = int(s[ind:ind+2])
    if tmp <= 50 and not visit[tmp]:
        visit[tmp] = 1
        stack.append(tmp)
        backtrack(ind + 2, limit)
        visit[tmp] = 0
        stack.pop()


def main():
    global s, stack, visit
    visit = [0 for _ in range(51)]
    s = input().rstrip()
    stack = []
    backtrack(0, len(s))


if __name__ == "__main__":
    main()

#include<stdio.h>
#include<stdlib.h> // exit

int visit[51] = { 0, };
int stack[51] = { 0, };
int stack_idx = 0;
char s[100];
int change_int(int size, char first, char second) {
    int ret;
    ret = first - '0';
    if (size == 1)
        return ret;
    ret *= 10;
    ret += second - '0';
    return ret;
}

void backtrack(int ind, int limit) {
    if (ind == limit) {
        int max = 0;
        int i;
        for (i = 1; i < 51; i++)
        {
            if (visit[i]) {
                max = i;
            }
        }
        for (i = 1; i < max + 1; i++)
        {
            if (!visit[i]) {
                return;
            }
        }

        // print length and all stack
        for (i = 0; i < stack_idx; i++)
        {
            printf("%d ", stack[i]);
        }
        printf("\n");
        exit(0);
    }
    int tmp;
    tmp = change_int(1, s[ind], 0);
    
    if (tmp && !visit[tmp]) {
        visit[tmp] = 1;
        stack[stack_idx++] = tmp;
        backtrack(ind + 1, limit);
        visit[tmp] = 0;
        stack_idx--;
    }
    if (ind + 2 <= limit) {
        tmp = change_int(2, s[ind], s[ind + 1]);
        if (tmp <= 50 && !visit[tmp]) {
            visit[tmp] = 1;
            stack[stack_idx++] = tmp;
            backtrack(ind + 2, limit);
            visit[tmp] = 0;
            stack_idx--;
        }
    }
}

int main() {
    int len, i;
    scanf("%s", s);
    for (i = 0; i < 100; i++)
    {
        if (s[i] == '\0') {
            len = i;
            break;
        }
    }
    backtrack(0, len);

    return 0;
}

 

오늘도 한 문제 풀다가 막혀서 다른 쉬운 문제로 갈아탔다.....