Algorithm - 카드 역배치

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[카드 역배치]

 

1부터 20까지 숫자가 하나씩 쓰인 20장의 카드가 아래 그림과 같이 오름차순으로 한 줄로 놓여 있다.

각 카드의 위치는 카드 위에 적힌 숫자와 같이 1부터 20까지로 나타낸다.

이제 다음과 같은 규칙으로 카드의 위치를 바꾼다. 

 

구간 [a, b]가 주어지면 위치 a부터 위치 b까지의 카드를 현재의 역순으로 놓는다. (단, 1 ≤ a ≤ b ≤ 20)

예를 들어, 현재 카드가 놓인 순서가 위의 그림과 같고 구간이 [5, 10]으로 주어진다면 위치 5부터 위치 10까지의 카드 5, 6, 7, 8, 9, 10을 역순으로 하여 10, 9, 8, 7, 6, 5로 놓는다.

 

이제 전체 카드가 놓인 순서는 아래 그림과 같다.

이 상태에서 구간 [9, 13]이 다시 주어진다면, 위치 9부터 위치 13까지의 카드 6, 5, 11, 12, 13을 역순으로 하여 13, 12, 11, 5, 6으로 놓는다.

 

이제 전체 카드가 놓인 순서는 아래 그림과 같다.

오름차순으로 한 줄로 놓여있는 20장의 카드에 대해 10개의 구간이 주어지면, 주어진 구간의 순서대로 위의 규칙에 따라 순서를 뒤집는 작업을 연속해서 처리한 뒤 마지막 카드들의 배치를 구하는 프로그램을 작성하시오.

 

 

*입력 설명

총 10개의 줄에 걸쳐 한 줄에 하나씩 10개의 구간이 주어진다.

i번째 줄에는 i번째 구간의 시작위치 ai와 끝 위치 bi가 차례대로 주어진다.

이 때, 두 값의 범위는 1 ≤ ai ≤ bi 20이다.

 

*출력 설명

1부터 20까지 오름차순으로 놓인 카드들에 대해, 입력으로 주어진 10개의 구간 순서대로 뒤집는 작업을 했을 때 마지막 카드들의 배치를 한 줄에 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_13.txt', 'rt')

a = list(range(21))
for _ in range(10):
    s, e = map(int, input().split())
    for i in range((e-s + 1) // 2):
        a[s+i], a[e-i] = a[e-i], a[s+i]

a.pop(0)
for x in a:
    print(x, end= ' ')

# 출력 : 1 2 3 4 10 9 8 7 13 12 11 5 6 14 15 16 17 18 19 20

 

input_13.txt(입력)

5 10
9 13
1 2
3 4
5 6
1 2
3 4
5 6
1 20
1 20

 

 

중요내용

1. a = list(range(21)) 코드는 0~20까지의 리스트 데이터를 변수 a에 선언한다.
2. a, b = b, a 코드는 두 변수의 값을 스왑해준다.
3. for _ in range(10): 코드는 특정 변수 없이 for문을 10번 반복하겠다는 의미이다.
4. a.pop() 함수는 변수 a에 있는 데이터를 삭제해준다. (만약, 해당 함수의 인자가 없으면 마지막 데이터를 삭제하고 인자가 있으면 해당 인자와 매칭되는 인덱스 번호의 데이터를 삭제함)