디지털 티비 in Python
문제
- 2012년 12월 31일 새벽 4시부터 지상파 아날로그 TV방송이 종료되었다. TV를 자주보는 할머니를 위해서, 상근이네 집도 디지털 수신기를 구입했다.
- 원래 상근이네 집에는 KBS1과 KBS2만 나왔다. 할머니는 두 방송만 시청한다. 이제 디지털 수신기와 함께 엄청난 양의 채널을 볼 수 있게 되었다. 하지만, 할머니는 오직 KBS1과 KBS2만 보려고 한다. 따라서, 상근이는 채널 리스트를 조절해 KBS1을 첫 번째로, KBS2를 두 번째로 만들려고 한다.
- 티비를 켜면 디지털 수신기는 시청 가능한 채널 리스트를 보여준다. 모든 채널의 이름은 서로 다르고, 항상 KBS1과 KBS2를 포함하고 있다. 상근이는 이 리모콘을 이용해서 리스트의 순서를 바꾸는 법을 알아냈다. 리스트의 왼편에는 작은 화살표가 있고, 이 화살표는 현재 선택한 채널을 나타낸다. 가장 처음에 화살표는 제일 첫 번째 채널을 가리키고 있다.
- 다음과 같은 네 가지 버튼을 이용해서 리스트의 순서를 바꿀 수 있다. 각각은 1번부터 4번까지 번호가 적혀져있는 버튼이다.
- 화살표를 한 칸 아래로 내린다. (채널 i에서 i+1로)
- 화살표를 위로 한 칸 올린다. (채널 i에서 i-1로)
- 현재 선택한 채널을 한 칸 아래로 내린다. (채널 i와 i+1의 위치를 바꾼다. 화살표는 i+1을 가리키고 있는다)
- 현재 선택한 채널을 위로 한 칸 올린다. (채널 i와 i-1의 위치를 바꾼다. 화살표는 i-1을 가리키고 있다)
- 화살표가 채널 리스트의 범위를 넘어간다면, 그 명령은 무시한다.
- 현재 채널 리스트의 순서가 주어졌을 때, KBS1를 첫 번째로, KBS2를 두 번째로 순서를 바꾸는 방법을 구하는 프로그램을 작성하시오. 방법의 길이는 500보다 작아야 한다. 두 채널을 제외한 나머지 채널의 순서는 상관없다.
입력 데이터
- 첫째 줄에 채널의 수 N이 주어진다. (2 ≤ N ≤ 100)
- 다음 N개 줄에는 채널의 이름이 한 줄에 하나씩 주어진다. 채널의 이름은 최대 10글자이고, 알파벳 대문자와 숫자로만 이루어져 있다.
- 이미 KBS1이 첫 번째에, KBS2가 두 번째에 있는 입력은 주어지지 않는다.
- 입력 예
4
ABC1
ABC02
KBS2
KBS1
출력 데이터
- 상근이가 눌러야 하는 버튼을 순서대로 공백없이 출력한다.
- 출력 예
11144411144
33144413
해결 방법
- 다른 채널을 아래로 내려서 KBS1과 KBS2가 상대적으로 위로 올라오는 경우는 버튼 누르는 방법의 길이가 500 이하임을 보장하기 힘듬
- 그러나, KBS1과 KBS2를 찾아 이 둘을 위로 올리는 경우 무조건 500보다 버튼을 누르는 방법의 길이가 500 보다 작을 수 밖에 없음 (최대 100개의 채널 중, KBS1과 KBS2가 맨 마지막에 나란히 있다하더라도, 버튼을 최대 400번 가량(화살표를 처음부터 끝까지 2번 왕복)만 누르면 됨)
- 또한 KBS1이 첫 번째에, KBS2가 두 번째에 있는 입력은 주어지지 않는다고 했으므로, 위의 논리에 따라 화살표를 옮기는 1번과 채널을 위로 올리는 4번만 고려하면 됨
- 다만, KBS2가 KBS1보다 먼저 등장하는 경우, KBS1을 KBS2 위로 올리는 순간 KBS2가 한 칸 밀려나는 것을 고려해야 함
코드
TARGET = {"KBS1": 0, "KBS2": 0}
command = ""
n = int(input())
chs = []
for i in range(n):
ch = input()
chs.append(ch)
if ch=="KBS1":
TARGET["KBS1"] = i
elif ch=="KBS2":
TARGET["KBS2"] = i
is_reversed = True if TARGET["KBS2"]<TARGET["KBS1"] else False
for _ in range(TARGET["KBS1"]):
command += "1"
for _ in range(TARGET["KBS1"]):
command += "4"
if is_reversed:
TARGET["KBS2"] += 1
for _ in range(TARGET["KBS2"]):
command += "1"
for _ in range(TARGET["KBS2"]-1):
command += "4"
print(command)
문제 원본 링크
https://www.acmicpc.net/problem/2816
