순열장난 - 10597

[Silver I] 순열장난 - 10597

문제 링크

1️⃣ 분류

백트래킹(backtracking), 수학(math)

2️⃣ 문제 설명

kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다.

그런데 sujin이 그 파일의 모든 공백을 지워버렸다!

kriii가 순열을 복구하도록 도와주자.

3️⃣ 입력

첫 줄에 공백이 사라진 kriii의 수열이 주어진다.

kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다.

4️⃣ 출력

복구된 수열을 출력한다. 공백을 잊으면 안 된다.

복구한 수열의 경우가 여러 가지 일 경우, 그 중 하나를 출력한다.

---

🔓 풀이

• 1부터 N까지의 수로 이루어진 순열에서 일단은 N을 알아야 Kriii의 순열이 어떤 수로 이루어진지 알 수 있음
• 그리고 kriii의 순열은 최대 50개의 수로 이루어져 있으니 N 이 50을 넘지는 않음 즉 두자릿수 한 정!
• 예제의 예가 아닌 14151243751161610981312 즉 N이 16인 내가 만든 임의의 수로 예를 들겠음

✌ 구현

• 처음 부터 탐색을 하는데 1 ~ N까지의 수에서 이미 처리를 했는지 체크를 하기 위해 visit 배열을 사용
• 그리고 이어진 수가 N을 넘거나 3자릿수 이면 더 이상 진행하지말고 백트래킹을 해서 새롭게 다시 방문해야 함

1, 4, 15(1?), 12(1?), 43???? 진행불가!!

• 15에서 (1?) 이라고 적은 것은 1은 방문했으니 뒤에꺼랑 합쳐서 뒤에꺼랑 합친 것이 N이랑 작거나 같아서 그 다음 단계로 진입이 가능
• 12도 마찬가지
• 그러나 43은 N보다 크니깐 kriii의 순열에 포함될 수 없음 백트래킹을 해야함!

1, 4, 15(1?), 12(1?)

• 백트래킹을 해야하는데 12 다음에 뭘 어떻게 할 수 가 없음 15도 마찬가지

1, 41??? 진행불가

• 4까지와서 두자릿수를 만들 수 있는데 뒤에꺼랑 합치니깐 41임.. 마찬가지로 백트래킹

14, 1, 51?? 진행불가

• 이런 방법으로 코드를 구현하면 된다

그럼 종료조건은?? tmp(kriii의 순열을 복원)가 꽉차면 총 N개의 숫자가 있을 거니깐 멈추면 된다!

• 백트래킹을 할 때 해당 부분을 방문했다는 것을 없애야하니깐 visit에서 해당 수를 방문제거함

📃 코드

s = input()

def dfs(s_idx, tmp_idx):
  global flag
  if flag :
    return
  if s_idx == len(s):
    if tmp_idx == cur:
      flag = True
      for k in tmp:
        print(k, end=' ')
    return

  i = int(s[s_idx])
  # 한 자릿 수 일 때,
  if not visit[i]:
    tmp[tmp_idx] = i
    # 방문기록 
    visit[i] = 1
    dfs(s_idx+1, tmp_idx+1)
    # 방문기록 삭제
    visit[i] = 0
    tmp[tmp_idx] = 0
    
  
  
  # 두 자릿 수 일 때,
  if s_idx+1 < len(s):
    j = int(s[s_idx]+s[s_idx+1])
    if j <= cur and not visit[j]:
      tmp[tmp_idx] = j
      visit[j] = 1
      dfs(s_idx+2, tmp_idx+1)
      visit[j] = 0
      tmp[tmp_idx] = 0
      
  
if len(s) < 10:
  new_s = list(int(i) for i in s)
  for k in new_s:
    print(k, end=' ')
else:
  flag = 0
  i = 0

  while flag == 0:
    cur = s[i] + s[i+1]
    r_len = 9 + (2*(int(cur) - 10))
    if r_len == (len(s)-2):
      flag = 1
    i+=1
  
  
  cur = int(cur)
  visit = [0 for _ in range(cur+1)]
  tmp = [0 for _ in range(cur)]
  flag = False
  dfs(0, 0)

🤣 고찰

이게 머라고… 하루종일 날렷다 실험을 하느라 ㅠㅠ 맨 처음에는 백트래킹인 지모르고 진행했다가 계속 틀려서 분류를 봣는데 백트래킹이엿다. 근데 나는 백트래킹에 매우 약했다… 그래서 다른 사람의 코드를 참조했는데 그래도 이해하는데 오래걸렸다 그래서 하루종일 백트래킹에 대해서 공부해보고 공부한 내용을 바탕으로 이것저것 코드를 실험했다.. 시간은 많이 소요했지만 그래도 백트래킹에 대한 자신감이 생겨서 내일 1문제도 백트래킹관련 문제를 풀어서 내껄로 만들어야 겠다!!