ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1021.회전하는 큐
    알고리즘/백준 BAEK JOON 2020. 4. 9. 00:41

    이번 문제도 조금 당황할 순 있어도 난이도가 그렇게 어렵지 않았다. 

     

     

     

     

    문제에서 시키는 대로 차근차근 생각하면 되고 문제를 제대로 읽어야 한다.

    이번 문제에서는 조건을 대충 읽었다가 내 맘대로 구현을 해버렸다. 문제를 다시 읽고 나서야

    내 맘대로 문제를 풀었다는 것을 확인했다. ( 문제 대충 읽는 실수 주의! )

    1021번: 회전하는 큐

    첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

    www.acmicpc.net

     

    < Code 설명 >

    #include <iostream>
    #include <queue>
    #include <string.h>
    
    using namespace std;
    
    int main()
    {
        int n, m;            // 큐의 크기와 뽑을 수의 갯수
        cin >> n >> m;       // 입력받기
        int a[100]={0,};     // 그냥 넉넉하게 줬음
        deque<int>ex;        // 실제로 동작하는 덱
        deque<int>x;         // 임시저장 덱
        int v = 0;           // 숫자 위치 값
        for(int i=1; i<=m; i++){ // 뽑을 수가 3개니까
            cin >> v;            
            a[v-1]=i;            // 해당 숫자를 입력받은 위치에 가져다놓음
        }
        for(int i=0; i<n; i++){  // 10개의 크기의 덱을 만들기 위함
            ex.push_back(a[i]);  // 배열을 그대로 실행 덱에 복사
        }
        int count1=0, count2=0,ans=0; // 왼쪽 연산 수, 오른쪽 연산수, 정답 변수
        for(int i=1; i<=m; i++){      // 숫자 3개만 뽑으면 되므로
            x=ex;                     // 실행 덱을 임시 덱에 저장함
            while(ex.front()!=i){     // 제일 앞에 첫 번째 숫자가 올떄까지 돌린다.
                ex.push_back(ex.front()); // 왼쪽으로 이동시키는 연산일 때
                ex.pop_front();           
                count1++;                 // 왼쪽 연산 수 증감
            }
            ex=x;                     // 복사해놓은 기존의 덱을 실행 덱으로 가져옴
            while(ex.front()!=i){     
                ex.push_front(ex.back()); // 오른쪽으로 이동시키는 연산일 때
                ex.pop_back();
                count2++;                 // 오른쪽 연산 수 증감
            }
            ex.pop_front();    // 왼쪽이던 오른쪽이던 가장 앞일 때 뽑기 때문에 
            ans += count1 >= count2 ? count2:count1; // 더 작은 값을 정답으로 누적
            count1=0;  // 초기화
            count2=0;  // 초기화
        }
        cout << ans <<endl;
        return 0;
    }
    

    반드시 알아야 할 TIP!!

    # 문제를 제대로 읽자! -> 대충 읽으면 조건을 마음대로 예상하게 됨

    ex) 왼쪽으로 이동하니까 제일 앞에서 뽑네? 그럼 오른쪽은 제일 뒤에서 뽑겠지?

     

    # 설계하는 시간은 충분히 가져야 한다 -> 손부터 나갔다가 코드 중간에 예외처리를 빠트린 걸 발견하면 이미 끝.....

    # 입력받는 부분도 우습게 보면 안 된다 -> 생각보다 시간이 많이 들 수도 또는 오히려 시간을 줄일 수도 있음

    반응형

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    1722.순열의 순서  (0) 2020.04.15
    5430.AC  (0) 2020.04.13
    1966.프린터 큐  (0) 2020.04.07
    11866.요세푸스 문제 0  (0) 2020.04.06
    4949.균형잡힌 세상  (0) 2020.04.06

    댓글

Designed by Tistory.