reverse()

졸업 후 급하게 방을 빼고 올라와서 또 급하게 정보처리기사를 준비하느라 최근 백준에 손을 대지 않았다. 3월 7일에 필기 시험이 끝나 새로운 계획을 짜고 어제부로 다시 문제를 풀기 시작했다. 오랜만에 들어가니 단계별로 풀어보기란에 새로운 문제들이 추가가 된 모습을 볼 수 있었다. 난이도는 낮지만 감도 찾을 겸 첫 단계에 추가된 문제부터 쭉 풀어보기로 했다.

 

오늘 10811번을 풀고 이건 글로 남겨보는 것도 나쁘지 않을 것 같아 정리해보려 한다. 일단 배열 뒤집기 문제인데, 나는 뇌가 C에 절여 있어 웬만한 알고리즘은 만들어 쓰는 것을 선호했었다. 이전에 코딩테스트를 보던 중 정렬 문제가 나왔는데 처음에 선택정렬로 해결하니 시간 초과가 떠서 어느 TC는 맞고 어느 TC는 틀리는 현상이 발생했다. 그래서 항상 외우고 다니던 Heap Sort를 만들어 쓰려했는데 웬걸 갑자기 기억이 나지 않는 것이다... 그 이후로 그냥 깝치지말고 algorithm 헤더에 있는 sort를 쓰기로 마음 먹었다. 곰곰이 생각해보니 다 쓰라고 만들어 놓은 것들인데 나만 너무 원시인 행동을 하는 것 같아 이제는 C에서 조금 벗어나 C++을 C++답게 써보는 것도 나쁘지 않을 듯 했다. 그래서 그 이후로 C++을 좀 찾아보니 생각보다 굉장한 언어인 것 같아 객체지향 등의 개념도 직접 구현해보는 등 이것저것 공부해보려 한다.

그렇긴 하지만... 나는 여전히 C가 재밌고 포인터 쓰는 게 좋다. 그래서 결국 불편한 방법(C)과 편한 방법(C++) 두 가지 모두 해보기로 했다.

 

문제는 다음과 같다.

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

10811번: 바구니 뒤집기

 

1. 포인터 활용 풀이

스스로 항상 완벽주의적인 성격이라고 생각하지는 않는데 왜 항상 코딩할 때는 그런 성격이 되는지 모르겠다 ㅋㅋ 사실 main 함수에서 다 구현해도 되는 거고.. 어차피 코테가 목적이면 전역변수를 적극 활용해도 사실 아무런 문제가 없는데 뭔가 그렇게 하기가 그냥 싫다. 드러운 코드가 싫어서 포인터를 공부했고, 더 간결하게 하고 싶어 함수를 공부했다.

 

일단 배열을 뒤집는 함수가 필요하다. 어디부터 어디까지 뒤집을지 결정해야하니까 매개변수로는 int 형 2개, int* 형(배열)이 1개 필요하다(만약 배열을 전역변수로 두면 굳이 배열을 매개변수로 줄 필요는 없다). 그래서 탄생한 함수

void rev(int first, int last, int* arr) {
  for (int i = first - 1, j = last - 1; i < (last + first) / 2; i++, j--) {
    swap(&arr[i], &arr[j]);
  }
}

음.. 만들고 보니 swap 함수도 필요하다. 직접 적어도 되지만 swap은 항상 만들어 놓는 것을 선호하는 편이다.

void swap(int* first, int* last) {
  int temp = *first;
  *first = *last;
  *last = temp;
}

이렇게 하면 아래처럼 i와 j의 값을 받자마자 rev 함수 하나만으로 배열 뒤집기가 가능해진다.

for (int k = 0; k < M; k++) {
  cin >> i >> j;
  rev(i, j, arr);
}

 

2. reverse() 함수 활용 풀이

나는 결국 int 형 배열에 맞춰서 함수를 제작해서 쓴 것인데.. 그렇다면 이미 만들어놓은 것도 있지 않을까? 라는 생각에 C++ 배열 뒤집기를 검색해보니 아니나다를까 reverse()라는 함수가 있었다.정의문을 찾아보니

template <class BidirectionalIterator>
  void reverse (BidirectionalIterator first, BidirectionalIterator last)
{
  while ((first!=last)&&(first!=--last)) {
    std::iter_swap (first,last);
    ++first;
  }
}

양방향 반복자 클래스에 선언되어 있다. 예제는 벡터로 나와있는데 나는 벡터가 아닌 배열을 이용할 것이기에 배열로 이용해보았다. '아마 객체로 사용할 수 있는 형태를 이것저것 만들어놨겠지'라는 생각을 하며.

for (int k = 0; k < M; k++) {
  cin >> i >> j;
  reverse(arr + i, arr + j);
}

처음에는 위처럼 하면 'i 부터 j 까지 바뀌겠지' 생각하며 적었는데,

엥? 안바뀌네? 싶어서 배열에 대해 살짝 생각해보니 그냥 arr + i 라고 적으면 첫 번째 공이 아니라 두 번째 공이구나 싶어 i - 1로 고쳤다.

음, 잘 나온다. 물론 답도 잘 나온다.

그거 하나 바꿨는데 코드 길이가 거의 300 바이트정도 차이 난다. 코테는 가뜩이나 시간 절약하는 것도 중요하니 이런 함수는 외워서 두고두고 쓰는 것도 나쁘지 않을 듯 하다.

 

< 전체 코드 >

#include <iostream>
#include <algorithm>

using namespace std;

void rev(int first, int last, int* arr);
void swap(int* first, int* last);

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N, M;
  cin >> N >> M;

  int i, j;
  int arr[100] = { 0 };
  for (int k = 0; k < N; k++) {
    arr[k] = k + 1;
  }
  for (int k = 0; k < M; k++) {
    cin >> i >> j;
    rev(i, j, arr);
  }

  for (int k = 0; k < N; k++) {
    cout << arr[k] << " ";
  }

  return 0;
}

void rev(int first, int last, int* arr) {
  for (int i = first - 1, j = last - 1; i < (last + first) / 2; i++, j--) {
    swap(&arr[i], &arr[j]);
  }
}

void swap(int* first, int* last) {
  int temp = *first;
  *first = *last;
  *last = temp;
}

reverse 함수 이용 코드는 위에 언급한 부분만 바꿔주면 된다.