26번 : 병합정렬 스타일의 코드

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

26. 마라톤

작성

268

안녕하세요 선생님. 강의 잘 듣고 있습니다.

아래는 채점기에서 100점을 받은 제 정답 코드입니다. 병합 정렬 스타일의 코드는 이런 느낌일까요?

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

int main(int argc, char** argv) {
	
	// freopen("input.txt", "rt", stdin);
	
	// init
	int n;
	cin >> n;
	vector<int> arr(n);
	vector<int> res(n, 1);
	deque<int> mydeque;
	for(int i = 0; i < n; i++) cin >> arr[i]; 
	
	// logic
	for(int i = 0; i < n; i++){
		// 1. deque가 빈 경우 맨 앞에 삽입
		if(mydeque.empty())
			mydeque.push_front(arr[i]);
		// 2. deque의 맨 앞에 있는 원소보다 현재 값이 더 작은 경우 맨 앞에 삽입
		else if(mydeque.front() >= arr[i]){
			res[i] += mydeque.size(); // deque의 사이즈만큼 정답 배열에 더함
			mydeque.push_front(arr[i]);
		}
		// 3. deque 안에서 알맞은 위치를 찾아감
		else if(mydeque.back() >= arr[i]){
			int cnt = 0;
			deque<int>::iterator it = mydeque.end(); it--;
			while(*it >= arr[i]) {
				it--; cnt++;
			}
			it = mydeque.insert(++it, arr[i]); // 현재 it에 1을 더해야 알맞은 위치
			res[i] += cnt;
		}
		// 4. deque의 마지막 원소보다 현재 값이 더 큰 경우 맨 뒤에 삽입
		else mydeque.push_back(arr[i]);
	}
	
	for(int i = 0; i < n; i++){
		cout << res[i] << " ";
	}
		
	return 0;
}

C++코테 준비 같이 해요!

답변 3

김태원

지식공유자

안녕하세요^^

제가 말한 병합정렬스타일은 실제 병합정렬로 푸는 것입니다. 마라톤 문제는 실제 백준에 있는 "달리기"(2517번)문제를 N제한을 작게만든 문제입니다. 님의 코드가 제대로 된 코드라면 백준에서 "달리기"문제로 채점해보시면 됩니다.

아래 코드는 제가 병합정렬로 짠 코드입니다. 스스로 분석해보세요^^

#include<bits/stdc++.h>
using namespace std;
struct Data{
	int idx, speed, rank;	
};

vector<Data> a(500000), tmp(500000);
int res[500000];

void divide(int lt, int rt){
	int mid;
	int p1, p2, p3;
	if(lt<rt){
		mid=(lt+rt)/2;
		divide(lt, mid);
		divide(mid+1, rt);
		p1=lt;
		p2=mid+1;
		p3=lt;
		while(p1<=mid && p2<=rt){
			if(a[p1].speed<a[p2].speed) tmp[p3++]=a[p1++];
			else{
				tmp[p3]=a[p2++];
				tmp[p3].rank+=mid-p1+1;
				p3++;
			}
		}
		while(p1<=mid) tmp[p3++]=a[p1++];
		while(p2<=rt) tmp[p3++]=a[p2++];
		
		for(int i=lt; i<=rt; i++){
			a[i]=tmp[i];
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);
	int n, t;
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>a[i].speed;
		a[i].idx=i;
		a[i].rank=0;	
	} 
	divide(0, n-1);
	for(int i=0; i<n; i++){
		res[a[i].idx]=a[i].rank+1;
	}
	for(int i=0; i<n; i++){
		cout<<res[i]<<"\n";
	}
	return 0;
}

김태원

지식공유자

실전모의고사를 생각은 하고 있는데 어려운 문제를 오프에서 학생들과 호흡하면서 설명하는 것과는 달리 영상으로 설명하는 것은 많이 어렵네요. 사실 조금 찍다가 그만둔 상태입니다. 다시 시작해 보려고 합니다만 선뜻 시작이 잘 안되네요.ㅠㅠ

Eunyoung Roh

질문자

백준에서 채점해 보니 시간 초과가 뜨는 걸 보면 선생님께서 짜신 대로 짜야 할 것 같습니다.
정말로 병합 정렬처럼 푸는군요. 많은 공부가 되었습니다.

혹시 이 강의보다 더 어려운 C++ 알고리즘 강의 출시 계획이 있으신지요?
동영상에서 언급하셨는지 Q&A에서 언급하셨는지 기억이 안 나지만, 모의고사 강의를 찍으시겠다고 하신 것 같아서요.
선생님 강의가 좋아서, 인프런에 올리시면 그것도 결제하려고 합니다.

앞으로도 계속 질문드리겠습니다. 꾸준히 답변 달아 주셔서 감사합니다.

인프런 커뮤니티 질문&답변

26번 : 병합정렬 스타일의 코드