백준 9019번, 시간 초과 오류(Python3, PyPy3)

 

 

 

 

 

 

백준 문제를 진행하면서 코드에 문제가 없다고 판단이 드는데

9019번의 시간 설정(6초) 때문인지 '시간 초과'가 무려 12번이나 반복되고, 해결점을 찾았다!

 

간단하게 문제를 소개하면서 해결 방법을 작성해보려고 한다.

 

 

 

---

 

 

 

DSLR 

시간	메모리 제한	제출	정답	맞힌 사람	정답 비율
6 초	256 MB	79135	19331	12638	20.759%

 

문제

 

네 개의 명령어 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

 

 

제출 소스코드

from collections import deque
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    A,B = map(int,input().split())
    q = deque()
    q.append((A,""))
    visit = [False] * 10000
    
    while q:
        num, path = q.popleft()
        visit[num] = True
        if num == B:
            print(path)
            break
        
        num2 = (2*num)%10000
        if not visit[num2]:
            q.append((num2,path+"D"))
            visit[num2] = True

        num2 = (num-1)%10000
        if not visit[num2]:
            q.append((num2,path+"S"))
            visit[num2] = True

        num2 = (10*num+(num//1000))%10000
        if not visit[num2]:
            q.append((num2,path+"L"))
            visit[num2] = True
            
        num2 = (num//10+(num%10)*1000)%10000
        if not visit[num2]:
            q.append((num2,path+"R"))
            visit[num2] = True

 

 

해설

1. 첫 번째 루프에서는 테스트 케이스의 수를 입력받고, 각 테스트 케이스에 대해 아래의 작업을 반복한다.
2. 시작 숫자 A와 목표 숫자 B를 입력받는다.
3. BFS(너비 우선 탐색)를 사용하여 A에서 B로 변환하는 최소한의 명령을 찾는다.
4. 큐를 사용하여 현재 숫자와 현재까지의 명령 경로를 저장합니다. 방문한 숫자는 visit 배열에 표시한다.
5. 큐가 빌 때까지 다음 단계를 반복한다.
   • 현재 숫자와 명령 경로를 가져온다.
   • 현재 숫자가 목표 숫자와 같으면 명령 경로를 출력하고 종료한다.
   • 각각 'D', 'S', 'L', 'R'에 대해 다음 숫자와 명령을 큐에 추가합니다. 단, 방문한 숫자는 다시 방문하지 않도록 한다.

 

 

 

 

---

 

 

 

PYTHON3 / PY3PY3

 

백준 온라인 저지(BOJ)에서는 사용자가 제출한 코드를 실행하는 데 두 가지 주요 언어를 지원한다. 바로 Python3와 PyPy3, 이 두 언어 간에는 몇 가지 중요한 차이점이 있다.

 

1. 인터프리터와 JIT 컴파일러

• Python3
  • CPython 인터프리터를 사용하여 Python 코드를 실행한다. CPython은 속도가 느릴 수 있지만 안정적이며 표준 Python 인터프리터로 널리 사용된다.
• PyPy3
  • PyPy는 Python의 JIT(Just-In-Time) 컴파일러를 사용하여 코드를 실행한다. 이는 일부 경우에는 Python 코드를 더 빠르게 실행할 수 있도록 해준다.

 

2. 성능

• 일반적으로 PyPy3는 CPython보다 더 빠른 실행 속도를 보인다. 특히 반복적이고 CPU 집약적인 작업에서 성능 향상을 볼 수 있다. 그러나 모든 상황에서 PyPy3가 항상 더 빠르지는 않다.

 

3. 호환성

• 대부분의 표준 Python 코드는 PyPy3에서도 잘 작동한다. 그러나 특정한 경우에는 CPython과의 호환성 문제가 발생할 수 있다.
• PyPy3는 CPython과 다르게 일부 C 확장 모듈을 지원하지 않거나 특정한 표준 라이브러리의 기능이 구현되지 않을 수 있다.

 

4. 메모리 사용량

• PyPy3는 일반적으로 CPython보다 더 많은 메모리를 사용한다. 이는 JIT 컴파일러가 추가 메모리를 필요로 하기 때문이다. 따라서 문제에 따라 적합한 언어를 선택해야 한다.
• 속도와 성능이 중요한 경우 PyPy3를 사용하는 것이 좋을 수 있다. 그러나 코드가 특정한 C 확장 모듈을 사용하거나 특정한 라이브러리와의 호환성이 필요한 경우 Python3를 선택하는 것이 더 나을 수 있다.