[탐색 및 시뮬레이션] 파이썬 알고리즘 문제 2-3 "카드 역배치"

카드 역배치

[시간복잡도]

O(n²) : 이중 for문 작성

[공간복잡도]

O(1)

Problem

1부터 20까지 숫자가 하나씩 쓰인 20장의 카드가 아래 그림과 같이 오름차순으로 한 줄로 놓 여있다. 각 카드의 위치는 카드 위에 적힌 숫자와 같이 1부터 20까지로 나타낸다.

 

 

이제 여러분은 다음과 같은 규칙으로 카드의 위치를 바꾼다: 구간 [a, b] (단, 1 ≤ a ≤ b ≤ 20)가 주어지면 위치 a부터 위치 b까지의 카드를 현재의 역순으로 놓는다.

예를 들어, 현재 카드가 놓인 순서가 위의 그림과 같고 구간이 [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개의 구간 순서대로 뒤집 는 작업을 했을 때 마지막 카드들의 배치를 한 줄에 출력한다.

 

▣ 입력예제

 

5 10

9 13

1 2

3 4

5 6

1 2

3 4

5 6

1 20

1 20

 

▣ 출력예제

 

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

💯 Solution ①

: 시도해봤지만 풀지못해서 튜터님의 코드 참고

 

### 카드 역배치 ###
import sys
sys.stdin=open("input.txt","rt")
 
# 카드 배열 생성
card_list=list(range(21))
 
# 반복이 10번 시행됨
for _ in range(10):
    s, e = map(int,input().split())
    for i in range((e-s+1)//2):
        card_list[s+i], card_list[e-i] = card_list[e-i], card_list[s+i]
 
card_list.pop(0)
for a in card_list:
    print(a, end=" ")

 

 

💯 Solution ②

: Tutor 님 Code

import sys
sys.stdin=open("input.txt","rt")
#a, b=map(int,input().split())
#a와 b가 자리가 바뀜
#a, b=b, a
 
# 0~20까지의 리스트가 생성됨
a=list(range(21))
 
# _ : 변수가 없는 것 / 평소에 i를 넣어서 i에 변수를 넣었음 : _를 활용해서 시간을 단축시킬 수 있음
for _ in range(10):
    s, e=map(int,input().split())
    # (e-s)+1 을 하면 배열의 첫 값과 마지막값을 교환하는 과정을 할 수 있음
    for i in range((e-s+1)//2):
        a[s+i], a[e-i] = a[e-i], a[s+i]
 
# 제일 앞쪽(0번 인덱스)에 값을 없앤다.  
a.pop(0)
for x in a:
    print(x, end=" ")
 

 

-  a=list(range(21)) : 0부터 20까지 리스트 값이 들어가있는 배열 생성

- for 문을 통해서 input.txt에 주어진 값들을 가져온다.

- s : strat / e : end 를 바탕으로 해당 인덱스의 값들을 역순으로 바꾸기 위해서 다시 for문을 돌린다.

 

- 여기서 제일 중요한 점은 for문의 반복횟수를 (e-s+1)//2 로 한다는 것이다.

: 예를들어, s=5 / e=10 이라고 한다면, 5 6 7 8 9 10 의 인덱스를 바꿔야하는데 5-10 / 6-9 / 7-8 총 세번의 반복을 시행하면된다. 그래서 e-s+1 // 2 를 하면 10-5+1//2 =3이 나온다. 즉, 3번만 반복문을 실행하면 된다는 것이다.

 

- a[s+i] 와 a[e-i]의 값을 거꾸로 바꿔주면 된다. ( a[s+i], a[e-i] = a[e-i], a[s+i]) 

: a, b = b, a 를 하면 a와 b의 값이 바뀐다.

 

- 배열의 제일 앞쪽에 들어간 0을 없애줘야한다. 이를 위해서 pop()을 사용하여 0번째 인덱스를 지운다. 

:pop(0)

 

- 배열을 하나씩 뽑아내서 붙인 상태로 출력하면 출력양식과 동일하게 나온다.

 

📚 참고

brownbears.tistory.com/452

[Python] 리스트 slice, pop, del 성능 비교 및 사용방법

 

• 리스트 = list(range(횟수))

>>> a = list(range(10))
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

• 파이썬에서는 다음과 같이 한 줄로 두 값을 바꿔치기할 수 있습니다.

a = 3
b = 'abc'
 
a, b = b, a # 참 쉽죠?