DSLR

문제

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →L 2341 →L 3412
1234 →R 4123 →R 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

입력

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

출력

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

예제 입력 1

3

1234 3412

1000 1

1 16

예제 출력 1

LL

L

DDDD

 

 

 

# 접근법

우선 문제를 마주하자마자 시뮬레이션 문제와 BFS가 섞였다는 것을 짐작하였고

회전이 나오는 것을 봐서 deque - rotate() 를 적절히 쓰면되겠다고 방향성을 잡았다.

 

그렇게 설계를 시작하였는데, 1000을 회전한다고 했을 때 문자열을 정수로 바꾸고 정수를 다시 문자열로 바꾸는

로직을 짜다보니 뭔가 로직이 더러워지면서 내가 잘 못된 길을 가고 있음을 직감하고 검색을 하였다.

알고리즘 문제상 코드가 더러워지면서 답을 맞히게 하는 경우를 아직 못봤다. 즉 간결하면서도 휴먼에러를 최소화 시키고 효율적인 코드를 짜기 위한 훈련인데, 그 의도에 반하여 뭔가 내 코드가 필요 이상의 if가 많아지기 시작하면 나는 개인적으로 stop한다. 대게는 내가 방향성을 잘 못 잡았거나 함정에 빠졌을 확률이 거의 그냥 100%였다.

 

그래서 이번에도 신속하게 검색을 하였고 잘 못된 길을 가고 있었음을 확인했다.

deque의 rotate를 이용하게 되면 문자열을 넣어서 회전하고, 두 배해주거나 뺄 때에는 정수로 변환하는 등 

로직이 상당히 복잡해지며 찾아보니 시간복잡도에도 어긋난다고 한다.

 

그래서 다른 사람 코드를 보니,

상당히 영리하게 처리를 했다... 이렇게 또 하나를 배워간다.

 

oper_L(n):

oper_R(n):

위 두 함수에 각각 1234를 직접 넣어본다면 원리를 쉽게 이해할 수 있을 것이다. 또 0010 이런 부분에 대한 로직을 별도로 처리해줄 필요도 없다. 즉 코드가 간결해졌다.

 

deq에는 값을 (현재값, "연산기록문자열 ex)LL, DDD....") 이렇게 들고 있는다.

deq.append((tmp, oper+'D'))

위와 같은식으로...

 

또 출력 조건을 보면 아래와 같이 설명돼 있다.

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

즉 값이 일치하면 아무거나 출력해도 되기 때문에 중복이 필요없으니 

visited를 list가 아닌 set으로 설정한다.

굳이 list가 아닌 set인 이유는 당연하게도 시간복잡도이다.

list는 O(n)인 반면 set은 O(1)이므로 성능차이가 압도적이기 때문이다.

 

나머지 부분은 전형적인 BFS로직이다.

 

# 코드

import sys    
from collections import deque   
# n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 
# 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 
# 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.
def oper_D(n):
  # D: D 는 n을 두 배로 바꾼다. 
  # 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 
  # 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
  res = n*2
  if res > 9999:
    res%=10000
  return res
 
def oper_S(n):
  # S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다.
  # n이 0 이라면 9999 가 대신 레지스터에 저장된다.
  res = n
  if res <= 0:
    return 9999
  res-=1
  return res
 
def oper_L(n):
  # L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 
  # 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
  front=n%1000
  back =n//1000
  res  =front*10+back
  return res
 
def oper_R(n):
  # R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 
  # 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.
  front=n%10
  back =n//10
  res  =front*1000+back
  return res
 
def bfs(a, b):
 
  origin, target = a, b
  deq = deque()
  deq.append((origin, ''))
  visited = set()
  visited.add(origin)
 
  while deq:
    cur_val, oper = deq.popleft()
    if cur_val == target:
      print(oper)
      return
    
    tmp = oper_D(cur_val)
    if tmp not in visited:
      visited.add(tmp)
      deq.append((tmp, oper+'D'))
 
    tmp = oper_S(cur_val)
    if tmp not in visited:
      visited.add(tmp)
      deq.append((tmp, oper+'S'))
 
    tmp = oper_L(cur_val)
    if tmp not in visited:
      visited.add(tmp)
      deq.append((tmp, oper+'L'))
    
    tmp = oper_R(cur_val)
    if tmp not in visited:
      visited.add(tmp)
      deq.append((tmp, oper+'R')) 
 
if __name__ == "__main__":
  input   = sys.stdin.readline
  t       = int(input())
  for _ in range(t):
    a, b    = map(int, input().split()) 
    bfs(a, b)