-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
26번 : 병합정렬 스타일의 코드
20.09.17 11:40 작성 조회수 208
0
안녕하세요 선생님. 강의 잘 듣고 있습니다.
아래는 채점기에서 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;
}
답변을 작성해보세요.
2
김태원
지식공유자2020.09.18
안녕하세요^^
제가 말한 병합정렬스타일은 실제 병합정렬로 푸는 것입니다. 마라톤 문제는 실제 백준에 있는 "달리기"(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;
}0
김태원
지식공유자2020.09.20
실전모의고사를 생각은 하고 있는데 어려운 문제를 오프에서 학생들과 호흡하면서 설명하는 것과는 달리 영상으로 설명하는 것은 많이 어렵네요. 사실 조금 찍다가 그만둔 상태입니다. 다시 시작해 보려고 합니다만 선뜻 시작이 잘 안되네요.ㅠㅠ
0
Eunyoung Roh
질문자2020.09.18
백준에서 채점해 보니 시간 초과가 뜨는 걸 보면 선생님께서 짜신 대로 짜야 할 것 같습니다.
정말로 병합 정렬처럼 푸는군요. 많은 공부가 되었습니다.
혹시 이 강의보다 더 어려운 C++ 알고리즘 강의 출시 계획이 있으신지요?
동영상에서 언급하셨는지 Q&A에서 언급하셨는지 기억이 안 나지만, 모의고사 강의를 찍으시겠다고 하신 것 같아서요.
선생님 강의가 좋아서, 인프런에 올리시면 그것도 결제하려고 합니다.
앞으로도 계속 질문드리겠습니다. 꾸준히 답변 달아 주셔서 감사합니다.
답변 3