이 영역을 누르면 첫 페이지로 이동
자라자 블로그의 첫 페이지로 이동

자라자

페이지 맨 위로 올라가기

자라자

개발자를 준비하는 자라자의 블로그입니다.

BOJ 1021 회전하는 큐 C++

  • 2022.02.02 12:10
  • PS/BOJ

백준로고

[문제 링크]

https://www.acmicpc.net/problem/1021

[입출력 예]

입력 출력
10 3
2 9 5
8

[소스코드 - 내 풀이]

#include <bits/stdc++.h>
using namespace std;
int main(){

  //n,m입력받기
  int n, m;
  cin>>n>>m;

  deque<int> D;

  //덱에 숫자 채우기
  for (int i=1; i<=n; ++i){
    D.push_back(i);
  }

  //정답
  int cnt=0;

  while(m--){
    int x,tmp;
    tmp=0;
    cin>>x;
      while(D.front()!=x){
        D.push_back(D.front());
        D.pop_front();
        tmp++;
      }
      if (tmp>D.size()/2){
        cnt+=(D.size()-tmp);
      }
      else{
        cnt+=tmp;
      }
      D.pop_front();
  }

  cout<<cnt;


  return 0;
}

/*
[코멘트]
1. 처음 접근 시 문제 조건을 제대로 안 읽어서 앞에서도 뽑고 뒤에서도 뽑을 수 있는 줄 알았음.
2. 결국 위 풀이는 덱 풀이가 아닌 큐로 푼 것이었는데, 아래 모범 답안은 덱 풀이임.
3. find메소드로 iterator 범위와 목표값을 주면 iterator를 얻을 수 있음. 여기서 begin을 빼주면 인덱스가 나옴.
*/

[소스코드 - 모범답안]

// Authored by : haneulkimdev
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/9571e70535a34702812d2a03510ac182
#include <bits/stdc++.h>
using namespace std;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  deque<int> DQ;
  for (int i = 1; i <= n; i++) DQ.push_back(i);
  int ans = 0;
  while (m--) {
    int t;
    cin >> t;
    int idx = find(DQ.begin(), DQ.end(), t) - DQ.begin(); // idx : t가 있는 위치
    while (DQ.front() != t) {
      if (idx < DQ.size() - idx) {
        DQ.push_back(DQ.front());
        DQ.pop_front();
      }
      else {
        DQ.push_front(DQ.back());
        DQ.pop_back();
      }
      ans++;
    }
    DQ.pop_front();
  }
  cout << ans;
}

/*
20번째 줄에서, 지금은 idx가 항상 DQ.size()보다 작아서 문제가 없지만
DQ.size()는 unsigned int(or unsigned long long)이기
때문에 만약 idx가 DQ.size()보다 컸다면 overflow가 발생해
의도한대로 동작하지 않을 수 있음을 인지해야 함. 그래서 size()로
받아온 값에 대해서는 안전하게 (int)DQ.size() 로 항상 형변환을
하는 것도 괜찮음.
*/

'PS > BOJ' 카테고리의 다른 글

백준 1926 그림 C++  (0) 2022.02.06
백준 5430 AC C++ 풀이  (0) 2022.02.05
백준 2164 카드2 c++  (0) 2022.02.01
백준 10845 큐,큐2 c++  (0) 2022.02.01
백준 6549 히스토그램에서 가장 큰 직사각형 풀이 c++  (0) 2022.01.25

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • 백준 1926 그림 C++

    백준 1926 그림 C++

    2022.02.06
  • 백준 5430 AC C++ 풀이

    백준 5430 AC C++ 풀이

    2022.02.05
  • 백준 2164 카드2 c++

    백준 2164 카드2 c++

    2022.02.01
  • 백준 10845 큐,큐2 c++

    백준 10845 큐,큐2 c++

    2022.02.01
다른 글 더 둘러보기

정보

자라자 블로그의 첫 페이지로 이동

자라자

  • 자라자의 첫 페이지로 이동

검색

메뉴

  • 🏠 HOME
  • 💡 ABOUT
  • 💻 GITHUB

카테고리

  • 분류 전체보기 (91)
    • Tech Note (3)
    • Dev Log (11)
    • Study Log (11)
    • Settings (3)
    • PS (53)
      • Programmers (21)
      • BOJ (32)
    • Diary (10)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • 리액트
  • 공식문서읽기
  • ㅣ

나의 외부 링크

정보

자라자의 자라자

자라자

자라자

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. © 자라자. Designed by Fraccino.

티스토리툴바