서가 정리 지시서

문제

도서관 사서는 한 줄로 꽂힌 책들을 구간 단위로 뒤집어 배치를 바꿉니다.

책 코드가 꽂힌 순서대로 담긴 배열 shelf와, 정리 지시 목록 orders가 주어집니다. orders의 각 원소는 [l, r] 형태이며, shelf의 l번 칸부터 r번 칸까지(양 끝 포함)를 통째로 뒤집으라는 뜻입니다. 지시는 주어진 순서대로 차례차례 적용합니다.

모든 지시를 적용한 뒤의 배열을 반환하는 solution(shelf, orders) 함수를 작성하세요.

중요: 새 배열을 만들어 쌓지 말고, 주어진 배열의 원소를 서로 맞바꾸는 방식으로 제자리(in-place)에서 처리한 뒤 그 배열을 반환하세요.

예시

shelf = ["AL", "BM", "CT", "DR", "EK"]
orders = [[1, 3]]
→ ["AL", "DR", "CT", "BM", "EK"]
  1~3번 칸 [BM, CT, DR]이 [DR, CT, BM]으로 뒤집힌다.
 
shelf = ["AL", "BM", "CT", "DR", "EK"]
orders = [[0, 4], [0, 1]]
→ ["DR", "EK", "CT", "BM", "AL"]
  먼저 전체를 뒤집어 [EK, DR, CT, BM, AL],
  이어서 0~1번 칸을 뒤집어 [DR, EK, CT, BM, AL]이 된다.
 
shelf = ["KM", "LN", "MO"]
orders = [[0, 2], [0, 2]]
→ ["KM", "LN", "MO"]
  같은 구간을 두 번 뒤집으면 원래 배치로 돌아온다.

제약 조건

• 1 ≤ shelf.length ≤ 100,000
• 책 코드는 서로 같을 수도 있는 문자열입니다
• 0 ≤ orders.length ≤ 1,000
• 각 지시 [l, r]은 0 ≤ l ≤ r < shelf.length를 만족합니다
• 지시 구간의 길이가 1이면 (l === r) 배치는 변하지 않습니다
• 배열 자체를 제외하고 O(1)의 추가 메모리만 사용하세요

시간 복잡도 목표: O(모든 지시 구간 길이의 합)