[백준/8981] 입력숫자 (Python)

Problem : https://www.acmicpc.net/problem/8981

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 01:02:24

 

---

 

문제 설명

 

아래 mystery.c는 입력파일 X를 읽어서 그 안에 기록된 N개의 정수를 배열 NUM에 저장한 뒤에 이 N개의 수를 어떤 순서에 따라서 화면에 출력하는 프로그램이다. mystery.c가 X를 입력으로 받아 화면에 출력한 결과를 Y라고 하자. 

#include <stdio.h>
int NUM[101] ;
FILE *fin ;
int main(){
    int i, token,N ;
    int count=0, from= 0, value ;
    fin = fopen("X","r");
    fscanf(fin,"%d",&N);
    for(i=0; i<N; i++){
        fscanf(fin,"%d",&token);
        NUM[i]= token;
    } /* end of for */
    printf("%d\n", N ) ;
    value = NUM[ from ] ;
    while( count < N ) {
        while( value == 0 ) { 
            from = (from+1)%N; 
            value = NUM[ from ] ; 
        } /* end of inner while */ 
        printf("%d ", value ) ;
        count++ ;
        NUM[ from ] = 0 ; 
        from = (value +from )% N ; 
        value = NUM[ from ] ; 
    } /* end of outer while */
    return(0);
} /* end of main() */

여러분은 mystery.c에서 생성된 Y를 파일로 받아서 그것의 입력에 해당하는 X를 찾아내는 프로그램을 작성해야 한다. 

 

 

입력 및 출력

 

입력

첫 줄에는 정수 N (1 ≤ N ≤ 30)이 주어진다. 그리고 두 번째 줄에는 100이하 양의 정수 N개가 빈칸을 사이에 두고 모두 나열되어 있다. 단 그 정수 중에는 같은 수가 있을 수도 있다.

 

출력

첫 줄에는 정수 N이 제시되어 있고, 그 다음 줄에는 N개의 양의 정수가 빈칸을 사이에 두고 기록되어 있어야 한다. 만일 입력을 생성하는 mystery.c의 입력파일 X가 없는 경우에는 음수인 -1 을 첫 줄에 출력하면 된다.

 

입력 예시

5
1 2 4 3 5

 

 

출력 예시

5
1 2 3 4 5

 

 

---

 

풀이

너무 어렵게 생각해서 시간이 오래걸린 문제. 두 가지 접근 방법을 시도해 보았다.첫 번째에 너무 매몰되어 허투루 시간을 낭비한듯...

 

1. 역산하기 : 마지막 원소부터 차례대로, 모든 0에 들어갈 수 있는 경우를 따져보며 역산해가기. 이 방법은 모든 경우의 수를 따져야 하므로 당연히 TLE이다.

 

2. 순차적으로 접근하기 : 잘 생각해 보면, 이 알고리즘은 다음과 같다 :

• idx가 0이 아닌 원소를 가리킬 때까지 idx를 증가시킴
• idx가 가리키는 값을 출력 후 그 칸을 0으로 만들기. 그리고 idx를 그 값만큼 증가시킴
• 이를 N번 반복

그런데, 잘 생각해보면 초기 idx(from)은 0으로 주어졌으니 초기 배열의 0번째 값은 입력받은 배열의 0번째 값과 동일하다. 또한, i번째 값을 구하기 위해 idx를 회전시킬 때, 이미 채워진 값과 제거된 값은 반대가 된다. 즉 이미 제거되었어야 하는 값은 우리가 복원하는 리스트에 이미 저장되어 있고, 아직 남아있는 값은 우리가 복원하는 리스트에서 0으로 남겨져 있다. 따라서 다음과 같이 접근하면 빠르게 구할 수 있다.

 

• idx가 0인 원소를 가리킬 때까지 idx를 증가시킴
• idx에 현재의 값을 저장 후 idx를 그 값만큼 증가시킴
• 이를 N번 반복

...이 간단한 걸 늦게 떠올린 내가 안타깝다.

 

 

 

풀이 코드 (1번, TLE)

 

import sys

N = int(input())
result_list = list(map(int, input().split()))
result_list.reverse()

answer_list = [0]*N

def is_inside_zeros(start, end) :
  if start < end :
    return 0 in answer_list[start:end]
  else :
    return 0 in answer_list[:end] and 0 in answer_list[start:]

def dfs(frm, idx) :
  answer_list[frm] = result_list[idx]
  if idx == N-1 :
    for _ in range(frm) :
      answer_list.append(answer_list.pop(0))
    print(N)
    print(*answer_list)
    return True

  is_enable = False
  _frm = frm
  while True :
    prev_frm = ( _frm - result_list[idx+1] ) % N
    if not answer_list[prev_frm]:
      is_enable |= dfs(prev_frm, idx+1)
    _frm = (_frm - 1) % N
    if answer_list[_frm] or _frm == frm :
      break

  answer_list[frm] = 0
  return is_enable


flg = dfs(0, 0)
if not flg :
  print(-1)

 

 

풀이 코드 (2번)

 

import sys

N = int(input())
result_list = list(map(int, input().split()))

answer_list = [0]*N

answer_list[0] = result_list[0]
idx = answer_list[0] % N

for value in result_list[1:] :
  while answer_list[idx] :
    idx = (idx + 1) % N

  answer_list[idx] = value
  idx = (idx + value) % N

print(N)
print(*answer_list)

풀이 완료~