[Algorithm] 기초 문제 / 카드 역배치

▶ 문제

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

 

---

▷ 내가 짠 코드

문제 설명은 엄청 거창한테 실제 구현 자체는 생각보다 간단했다. 결국 그냥 배열의 뒤집기를 할 수 있느냐를 물어 본 것과 같다. 

import sys
sys.stdin = open('input.txt', 'rt')

cards = []
for i in range(1, 21):
    cards.append(i)

for i in range(10):
    a, b= map(int, input().split())
    picked = cards[a-1:b]
    cards[a-1:b] = picked[::-1]

for i in cards:
    print(i, end=' ')

일단 1부터 20개의 카드 리스트를 만들었고, 입력값 10줄을 받아와 작업하기 위해 for문을 돌렸다. 

for문 안에서 선택된 구간의 숫자를 뒤집는 코드를 구현했다. 가장 쉬운 방법인 슬라이싱을 사용했지만 방법은 아주 다양하다. 

그 후, 그 뒤집은 카드들을 원래 있던 index 구간에 그대로 덮어 씌워 주었다. 

마지막 출력은 숫자의 가로 나열이 돼야하기 때문에, 다시 for 문을 돌려 list의 값들을 하나하나 옆으로 출력했다.

 

 

▷ 예시 코드

import sys
sys.stdin=open("input.txt", "r")

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=' ')

엄청 깔끔하고 스마트한 코드에 눈이 휘둥그래졌다. 

 

우선 카드 리스트를 만드는 부분부터 놀랐다. 특정 범위 숫자를 담은 리스트를 저렇게 한 줄로 코딩하는 방법이 있었다니. 

 

그리고 또 깨알 팁이 「for _ in range(10)」 이 부분이다. 아무 변수 없이 반복문을 돌릴 때 언더바( _ )를 사용할 수 있다고 한다. 안그래도 「for i in range(10)」이라고 짜면서 i의 값을 쓸 일이 없는데 이렇게 하는 거 맞나?라는 생각을 했었는데, 이런 방법이 존재했다. 

 

 

구간을 뒤집는 부분은 이전에 공부했던 회문문자열의 방식과 유사하다. 

 

https://allsound.tistory.com/40?category=1029640 

[Algorithm] 기초 문제 / 회문 문자열 검사

 

위 링크의 예시코드를 보면

    for i in range((e-s+1)//2):

이 부분의 이해가 쉬워진다. 

간단히 말하자면 s부터 e까지의 index 범위 내에서 서로 대칭되는 값을 확인하기 위한 for 문이다. 

 

 

다음으로 따라오는 코드에서 또 하나 주목해야 할 부분이 있다. 

      a[s+i], a[e-i] = a[e-i], a[s+i]

두 변수 값을 바꾸는 swap을 사용해서 되칭되는 값을 뒤집는 코드이다. 

 

복잡해 보이지만 간단한 예시를 보면 이해가 쉽다.

x, y = 'Hello', 'World'
x, y = y, x
print(x, y)  # World Hello

이렇게 순서를 바꾸어 할당하면 두 변수의 값이 바뀌게 된다.

 

한 번도 사용해 본 적이 없는 문법이라 처음 볼 땐 뭐지? 싶었는데 알고나니 아주 편리하게 잘 쓸 수 있을 것 같다.