백준 2605 - 줄 세우기

문제링크

• 백준 2605

문제 접근

• 자리를 바꿔 한자리씩 밀어내는 부분을 직접 구현해보고자 했다.
• pair<int, int> 자료형과 벡터 컨테이너를 활용하여 pair 의 첫번째 원소는 인덱스를, 두번째 원소는 들어온 순서를 나타낸다.
• 내가 들어온 순서의 인덱스 값이 idx 라면, 번호를 뽑아 앞으로 갈 수 있는 인덱스 범위는 (idx-idx = 0) 부터 (idx - 0 = idx) 이다. 이동해야하는 인덱스 값을 구한 뒤 해당 인덱스부터 배열의 끝까지 원소들의 인덱스를 1씩 증가시킨다.
• 현재 들어온 순서의 인덱스에 위에서 구한 인덱스 값을 저장한다.

의사코드(pseudo-code)

# define function
- void changePlace(const int& tmp, const int& i, vector<pair<int, int>>& l)
	- for k=tmp to i-1:
		- l[k].first += 1

- bool cmp(const pair<int, int>& l1, const pair<int, int>& l2)
	- return l1.first < l2.first

# main
- cin >> N
- for i=0 to N-1:
	- pair<int, int> p = make_pair(i, i + 1)
	- l.push_back(p)
	- cin >> num
	- tmp = i - num
	- changePlace(tmp, i, l)
	- l[i].first = tmp
	- sort(l.begin(), l.end(), cmp)
- for i=0 to N-1:
	- cout << l[i].val << " "

소스코드 및 분석

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void changePlace(const int& tmp, const int& i, vector<pair<int, int>>& l) {
	for (int k = tmp; k < i; k++)
		l[k].first++;
}

bool cmp(const pair<int, int>& l1, const pair<int, int>& l2) {
	return l1.first < l2.first;
}

int main()
{
	int N;
	cin >> N;
	vector<pair<int, int>> l;
	for (int i = 0; i < N; i++) {
		pair<int, int> p = make_pair(i, i + 1);
		l.push_back(p);
		int num;
		cin >> num;
		int tmp = i - num;
		changePlace(tmp, i, l);
		l[i].first = tmp;
		sort(l.begin(), l.end(), cmp);
	}
	for (int i = 0; i < N; i++)
		cout << l[i].second << " ";
}

• 원소들의 순서는 새로운 원소가 들어올 때마다 변화가 일어난다고 가정할 수 있다.(물론 순서에 변화가 없는 경우도 있지만 일반적이지 않다.) 따라서 매번 새로운 기준에 맞춰서 정렬을 해줘야하고 algorithm 헤더파일에 sort 정렬함수로 활용하여 매 반복문마다 오름차순으로 정렬했다.
• changePlace 함수는 원소들의 인덱스를 조정해주는 함수로 구현은 간단하다. 변수 tmp 에는 이동해야할 인덱스값을 계산하고 해당 인덱스부터 뒤로 한칸씩 밀어낸다.
• 밀어내기가 끝나고 나면 새로 들어온 원소의 인덱스값을 지정해준다.

다른 풀이

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int> sarr(n);
	for (int i = 0; i < n; i++) {
		sarr[i] = i + 1; // 처음에는 학생들을 원래 위치에 넣어둔다.
		int tmp;
		cin >> tmp;
		int nidx = i - tmp; // 이동해야 하는 인덱스를 계산한다.
		if (nidx < i) { // tmp!=0 인 경우 항상 앞으로 이동한다.
			for (int idx = i-1; idx >=nidx; idx--) {
				sarr[idx+1] = sarr[idx]; // 이동하면서 nidx 이후 학생들을 한칸씩 민다.
			}
		}
		sarr[nidx] = i + 1;
	}
	for (auto ele : sarr)
		cout << ele << " ";
	cout << endl;
}