용꿀
꼬마개발자허니
용꿀
전체 방문자
오늘
어제
  • 분류 전체보기 (248) N
    • 개발 (75) N
      • 스프링 입문 (7)
      • 스프링 기본 (9)
      • ToDo List using JPA (2)
      • 스프링 개념 (9)
      • 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 (8)
      • 스프링 MVC (3)
      • CS (19) N
      • 개발 팁 (8)
      • 스프링 MSA (5)
      • 곰터뷰🐻 (5)
    • 알고리즘 (169)
      • 알고리즘 문제 풀이 (165)
    • 잡동사니 (1)
      • 노래 가사 (1)
hELLO · Designed By 정상우.
용꿀

꼬마개발자허니

(C++) 백준 1021번 - 회전하는 큐
알고리즘/알고리즘 문제 풀이

(C++) 백준 1021번 - 회전하는 큐

2023. 3. 22. 18:43

문제 링크 : https://www.acmicpc.net/problem/1021

 

1021번: 회전하는 큐

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

www.acmicpc.net

풀이

덱의 push와 pop을 사용하여 회전하는 큐를 어렵지 않게 구현할 수 있다.

다만 왼쪽으로 가는 것과 오른쪽으로 가는 것을 선택하는 알고리즘을 짜는 것에 고민을 많이 했는데, 단순하게 순회하며 어디가 더 가까운지 세는 것으로도 해결이 된다.

#include <iostream>
#include <deque>

using namespace std;

deque<int> D;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  
    
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        D.push_back(i);
    }
    int cnt = 0;
    while(m--){
        int i;
        cin >> i;
        int left, right;
        
        // 왼쪽으로 가는 것이 빠른지, 오른쪽으로 가는 것이 빠른지 체크
        for(int index = 0; index < D.size(); index++){
            if(D[index] == i){
                left = index;
                right = D.size()-index;
                break;
            }
        }
        if(left >= right){ // 오른쪽으로 이동 (3번 연산)
            while(1){
                if(i == D.front()){
                    D.pop_front();
                    break;
                }
                int tmp;
                tmp = D.back();
                D.pop_back();
                D.push_front(tmp);
                cnt++;
            }
        }else{ // 왼쪽으로 이동 (2번 연산)
            while(1){
                if(i == D.front()){
                    D.pop_front();
                    break;
                }
                int tmp;
                tmp = D.front();
                D.pop_front();
                D.push_back(tmp);
                cnt++;
            }            
        }
    }
    cout << cnt;
}

'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글

(C++) 백준 1926번 - 그림  (0) 2023.03.29
(C++) 백준 2504번 - 괄호의 값  (0) 2023.03.22
(C++) 백준 4949번 - 균형잡힌 세상  (0) 2023.03.22
(C++) 백준 10866번 - 덱  (1) 2023.03.21
(C++) 백준 10845번 - 큐  (0) 2023.03.21
    '알고리즘/알고리즘 문제 풀이' 카테고리의 다른 글
    • (C++) 백준 1926번 - 그림
    • (C++) 백준 2504번 - 괄호의 값
    • (C++) 백준 4949번 - 균형잡힌 세상
    • (C++) 백준 10866번 - 덱
    용꿀
    용꿀

    티스토리툴바