본문 바로가기
<알고리즘 문제풀이&연습>/[C,C++] Hackerrank

[C 자료구조] Array - Left Rotation

by 사용자 BlockDMask 2017. 7. 13.
반응형

0) 제목

Hackerrank 의 Arrays 부분의 Left Rotation 문제입니다.

왼쪽으로 배열을 옮긴다! 이런 문제입니다.

C언어를 이용하여 풀었습니다.


1) 문제설명

  • 배열이 주어지면 그 배열을 왼쪽으로 rotation 시키는 문제입니다. 

  • 예를들어 배열 {1, 2, 3, 4, 5, 6} 이 주어지고, rotation이 3이 나오게 되면

  • 출력을 {4, 5, 6, 1, 2, 3} 순으로 출력하면 됩니다.

  • 처음에 배열의 길이와, rotation의 숫자를 입력 받고

  • 배열의 길이만큼 데이터를 입력 받는 형태입니다.

2) 풀이과정

  • 자료구조 항목의 배열 문제 이지만, 재미있는 알고리즘 문제라고 생각합니다.

  • 처음에는 무식하게 "배열을 rotation 숫자만큼 이동하면 되겠다"라고 생각했는데, 

  • 잘 읽어보니까 "출력"만 rotation 된 형태로 하면 된다고 나와있는걸 중심으로 생각했습니다.

  • 생각한 결과, 

  • 배열을 움직이지말고, rotation 을 화살표라고 생각을하고 그것을 움직이는 방법으로 생각해봤습니다.

  • "rotation 화살표를 기준으로 배열의 끝까지 출력한다음, 배열의 맨 앞부터  rotation 화살표 까지 출력하면 되겠구나!"

  • 라는 결론에 도달하게 되었고

  • 지금의 코드가 나오게되었습니다.

3) 함수설명

주석 달려있습니다.

  • 입력받은 배열의 길이(arrLen) 만큼 동적할당을 합니다.

  • 저장해 두었던 rotation의 수(rNum)를 배열의 길이로 나누어 나머지를 다시 저장합니다.

  • 이제 rotation 수의 index 부터 배열의 끝까지 출력하고, 배열의 처음부터 rotation 수의 index까지 출력합니다.

4) 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<stdio.h>
#include<stdlib.h>
 
int main() {
    int arrLen; //배열의 길이를 저장할 변수
    int tmp;
    int rNum; //rotate를 몇번할지를 받는 변수
    int *arr;
 
    scanf("%d %d"&arrLen, &rNum);
    arr = (int *)malloc(sizeof(int* arrLen); //동적할당.
 
    //배열의 값을 받는다.
    for(int i=0; i<arrLen; i++){
        scanf("%d"&arr[i]);
    }
 
    //로테이션이횟수 % 배열의크기 = 현재로부터 몇번 움직여야하는지.
    rNum = rNum % arrLen;
 
    //로테이션 기준 뒤부터 배열의 끝까지 출력.
    for(int i=rNum ; i< arrLen; i++){
        printf("%d ", arr[i]);
    }
 
    //배열의 앞부터 로테이션 기준 까지 출력.
    for(int i=0; i<rNum; i++){
        printf("%d ", arr[i]);
    }
 
    //동적할당 해제
    free(arr);
    return 0;
}
cs


5) 인증

경로 : Dashboard>Data Structures>Arrays>Left Rotation

출처 : [HackerRank] https://www.hackerrank.com/challenges/array-left-rotation/

더 나은 코드로 보완 할 곳이 있으면 말씀해주세요.

부족한 코드 많은 지적 부탁드립니다.

반응형

댓글0