⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다 ⚠️
문제 링크 : https://www.acmicpc.net/problem/1021
1021번: 회전하는 큐
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가
www.acmicpc.net
Code
#include <stdio.h>
void reset_arr(int N, int array[]){
for(int i = 1; i < N + 1; i++){ // 배열 초기화
array[i] = i;
}
}
int main() {
int arr[51] = {0,};
int size = 0; // 총 배열의 크기
int size_temp = 0; // 현재 배열의 길이
int half_size = 0; // 배열의 이동방향 결정 변수
int cycle = 0; // 추출해야하는 숫자의 갯수
int number = 0; // 추출되는 숫자
int cnt = 0; // 배열이 총 움직인 횟수 => 최종 도출되는 답
scanf("%d %d",&size, &cycle);
size_temp = size;
reset_arr(size, arr);
for(int i = 0; i < cycle; i++){
scanf("%d", &number);
int temp = arr[number];
// 배열을 왼쪽으로 움직일지, 오른쪽으로 움직일지 계산
if(size_temp % 2 == 0) // 짝수
half_size = size_temp / 2;
else // 홀수
half_size = size_temp / 2 + 1;
if(arr[number] <= half_size){ // 배열이 왼쪽으로 갈때
// move_left();
for(int j = 1; j < size + 1; j++){
if(arr[j] < temp){
arr[j] = arr[j] + size_temp - temp;
}
else{
arr[j] = arr[j] - temp;
}
}
cnt += temp - 1;
size_temp -= 1;
}
else if(temp > half_size){ // 배열이 오른쪽으로 갈때
for (int j = 1; j < size + 1; j++) {
if(arr[j] > temp){
arr[j] = arr[j] - temp;
}
else{
arr[j] = arr[j] + size_temp - temp;
}
}
cnt += size_temp - temp + 1;
size_temp -= 1;
}
}
printf("%d\n", cnt);
return 0;
}
Code 필수 요소
1. 배열의 이동방향 판단
2. 배열의 이동방향에 따른 값의 변화
이것만 생각해내면 절반은 끝났다.
// 배열 초기화
계산의 편의성을 위해서 배열의 0번 index가 아닌 1번 index부터 값을 입력했다.
// 배열을 왼쪽으로 움직일지, 오른쪽으로 움직일지 계산
배열의 절반값 보다 크면 오른쪽으로, 작으면 왼쪽으로 움직여야 한다는건 다 알것이다. 하지만 C언어에서는 홀수를 절반으로 나누면 0.5는 버린다. 그렇기때문에 홀수일 경우 그 값의 절반에 1을 더해줬다.
ex) size가 5일 경우 그 절반은 2가 나오게 된다. 그럴경우 3이라는 숫자를 움직일때 절반인 2보다 크기때문에 오른쪽으로 움직여야 한다는 결론이 나오지만, 실제로는 왼쪽으로 움직이는것이 더 적은 횟수다.
// 배열이 왼쪽으로 갈때
이 문제에서 답으로 요구하는 것은 총 움직인 횟수이다. 그렇기때문에 기존에 숫자를 받았던 배열은 답을 출력하는데 직접적 필요가 없다고 판단하여 배열의 첫번째 값에 현재 숫자들 위치의 첫번째 값을 저장하는 것이 아닌, 배열의 첫번째 숫자인 1이 어느 위치에 있는지를 나타내는 용도로 사용했다. 즉 arr[1]의 값은 숫자 1의 위치를 나타낸다.
예시를 들어서 설명을 하겠다. 길이 5의 배열에서 숫자 2를 회전하여 제거하는 경우이다.
temp는 제거하려는 숫자의 위치인 2.
size_temp는 현재 배열의 크기. 아직 하나를 제거하지 않은 상황이므로 5.
cnt는 숫자 2를 제거하기 위해 움직인 횟수.
길이 5의 배열에서 숫자 2를 회전하여 제거했을경우 왼쪽으로 움직여 숫자는 3,4,5,1 이 남아있게 된다.
arr[1]인 1의 경우 temp인 2보다 작기때문에 if문속 코드가 동작하게 된다.arr[1] = arr[1] + size_temp - temp; == arr[1] = 1 + 5 - 2즉 arr[1]은 숫자 4가 아닌, 숫자 1의 현재 위치가 4번째에 있다는 것을 나타낸다.
arr[3]인 3의 경우 temp인 2보다 크기때문에 else문속 코드가 동작하게 된다.
arr[3] = arr[3] - temp; == arr[3] = 3 - 2즉 arr[3]은 숫자 1이 아닌, 숫자3의 현재 위치가 첫번째에 있다는 것을 나타낸다.
그렇다면 삭제된 2의 경우에는 어떻게 되는지 궁금할것이다.결론적으로 말하면 arr[2]의 값들도 계산이 된다. 하지만, 실질적인 결과에는 영향을 미치는 부분이 없다.즉, arr[2]의 값이 100이되든, -100이되든 이미 회전하여 나가는 숫자로 입력받았을 경우 결과에 전혀 영향이 없다.
cnt는 총 움직인 횟수를 나타내는데, 좌측으로 움직일 경우 제거하고자 하는 숫자의 위치보다 한칸 덜 움직인다.숫자가 하나 제거되었기 때문에 현재 배열의 크기를 나타내는 size_temp는 1을 마이너스해준다.
// 배열이 오른쪽으로 갈때
배열이 왼쪽으로 갈때와 기본적 원리는 똑같다. 간단한 계산만 변화를 준것이기 때문에 설명은 스킵한다.
더 깔끔하게 짤 수 있었을거 같은데 아쉽다.
-끝-