백준 알고리즘 10811번
백준 알고리즘 10811번 바구니 뒤집기
문제
도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, …, 가장 오른쪽 바구니를 N번째 바구니라고 부른다.
도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.
바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N (1 <= N <= 100)과 M (1 <= M <= 100)이 주어진다.
둘째 줄부터 M개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어진다. 방법은 i j로 나타내고, 왼쪽으로부터 i번째 바구니부터 j번째 바구니의 순서를 역순으로 만든다는 뜻이다. (1 <= i <= j <= N)
도현이는 입력으로 주어진 순서대로 바구니의 순서를 바꾼다.
출력
모든 순서를 바꾼 다음에, 가장 왼쪽에 있는 바구니부터 바구니에 적혀있는 순서를 공백으로 구분해 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 4 1 2 3 4 1 4 2 2 | 3 4 1 2 5 |
풀이
import sys
# N은 바구니의 개수, M은 연산의 개수
N, M = map(int, input().split())
# 바구니 초기화 (1부터 N까지의 공을 1번 바구니부터 N번 바구니까지 넣음)
basket = [i for i in range(1, N+1)]
temp = 0
# M번의 연산 수행
for _ in range(M):
i, j = map(int, sys.stdin.readline().split())
temp = basket[i-1:j]
temp.reverse()
basket[i-1:j] = temp
for x in range(N):
print(basket[x], end=" ")
- 바구니 수 N, 반복 횟수 M을 입력받는다.
basket이라는 배열에 1부터 N까지 값을 넣는다.N + 1을 해줘야 N까지 들어간다.
temp라는 변수를 0으로 초기화 해둔다.- 반복 횟수
M만큼 반복하면서i,j를 입력받는다.temp = 1부터 시작햇으므로basket의i-1번째부터 시작,j는 포함해야 하므로-1하지 않고 슬라이싱 해준다.reverse()함수를 사용해 순서를 역순으로 바꾼다.- 그리고 다시
basket의i-1:j를temp변수로 업데이트 해준다.
- 순서를 바꾼
basket을 반복문을 통해 출력하는데end=" "를 사용해 각 숫자마다 공백을 넣어서 출력한다.
basket[i-1:j]표현은 리스트basket에서 인덱스i-1에서j-1까지의 요소를 새로운 리스트로 반환한다. 이 때, 시작 인덱스는 포함되고, 종료 인덱스는 포함되지 않는다. 예를 들어basket = [1, 2, 3, 4, 5, 6]이라고 하면,basket[0:3]은[1, 2, 3]을 반환한다.basket[1:4]은[2, 3, 4]을 반환한다.만약
i-1과j가 주어졌다면,basket[i-1:j]는 인덱스i-1부터j-1까지의 요소를 포함하는 새로운 리스트를 반환한다.basket[1-1:4]는basket[0:4]와 같으며[1, 2, 3, 4]를 반환한다.인덱스는 0부터 시작한다. 따라서
i-1이라고 표현된 이유는 1-based 인덱싱을 0-based 인덱싱으로 바꾸기 위함이다.
