바구니 순서 바꾸기

백준 10812

문제 링크

---

문제

---

문제 이해

• I J K 순서대로 입력되고, 바구니가 K부터 재배열된다.

• 예시1

  입력 : 1 6 4
  원래 배열 : 1 2 3 4 5 6
  바뀐 배열 : 4 5 6 1 2 3

• 예시2

  입력 : 3 9 8
  원래 배열 : 3 4 5 6 7 8 9
  바뀐 배열 : 8 9 3 4 5 6 7

---

• 모든 순서를 회전시킨 다음, 가장 왼쪽에 있는 바구니부터 공백으로 구분해 출력한다.

---

• 바구니의 번호는 100을 넘지 않는다. 따라서, I/K/J도 100을 넘지 않는다.

(1 ≤ N ≤ 100, 1 ≤ M ≤ 100)

---

💡문제 해결 과정

1. 첫째 줄에 N,M을 입력받는다.
   바구니를 N 크기의 배열로 선언하고, 바구니 번호에 맞는 공을 담는다.

int N,M;
scanf("%d %d", &N, &M);
int basket[M+1];
for(int i=0; i<N; i++) basket[i] = i+1;

3. M번 동안 반복되며, I J K를 순서대로 입력받는다.
   편의상 beg : end : mid라고 부르겠다.

int beg, end, mid;
for(int i=0; i<M; i++) {
scanf("%d %d %d", &beg, &end, &mid);
}

3. 여기서 본격적인 고민이 시작된다. 배열이 나열되는 순서는 다음과 같다.

mid,mid + 1, ... ,end - 1,end, beg, beg+1, ... , mid - 1

따라서 첫번째로 mid - end값을 begin까지 앞으로 밀어줘야 한다.

for(int j=mid-1; j<= end-1; j++)
        basket[j-1] = basket[j];

그러나 위와 같은 알고리즘을 실행했을 때 mid-1부터 beg까지의 값이 사라지게 된다.
이를 해결하기 위해 임시 변수 temp에 그 값을 저장시킨다음, 다시 end부터 차례대로 temp값을 넣어준다.

int temp;
for(; beg - 1 < mid - 1; mid--, end--) {
      temp = basket[mid - 2];
      for(int j=mid-1; j<= end-1; j++)
        basket[j-1] = basket[j];
      basket[end-1] = temp;
    }

(INDEX는 0부터 시작하므로 모든 beg,mid,end값에서 1를 빼야 한다.)

5. basket배열을 차례대로 출력한다.

for(int j=0; j<N; j++) printf("%d ", basket[j]);

코드

#include <stdio.h>
int main() {
  int N,M, basket[100], temp;
  int beg, end, mid;
  scanf("%d %d", &N, &M);
  for(int i=0; i<N; i++) basket[i] = i+1;
  for(int i=0; i<M; i++) {
    scanf("%d %d %d", &beg, &end, &mid);
    for(; beg - 1 < mid - 1; mid--, end--) {
      temp = basket[mid - 2];
      for(int j=mid-1; j<= end-1; j++)
        basket[j-1] = basket[j];
      basket[end-1] = temp;
    }
  }
  for(int j=0; j<N; j++) printf("%d ", basket[j]);
  return 0;
}

✅성능 및 결과