[BOJ] 백준 2605 줄 세우기

Approach

출처: https://www.acmicpc.net/problem/2605

s

뽑은 번호 i 만큼 앞으로 이동한다고 보면 된다.

Q) 크기 N 공간이 있을 때, 몇번째에 삽입되는 것일까?

A) [N - i - 1] 이다. (0번째 인덱스부터 시작하므로 -1 처리 해준다.)

 

첫 번째 학생이 번호[0] 뽑은 경우

    [ 1 ] → 1 - 0 - 1 = 0번째 삽입

두 번째 학생이 번호[1] 뽑은 경우

    [ 2 1 ]  → 2 - 1 - 1 = 0번째 삽입

세 번째 학생이 번호[1] 뽑은 경우

    [ 2 3 1 ] → 3 - 1 - 1 = 1번째 삽입

네 번째 학생이 번호[3] 뽑은 경우

    [ 4 2 3 1 ] → 4 - 3 - 1 = 0번째 삽입

다섯 번째 학생이 번호[2] 뽑은 경우

    [ 4 2 5 3 1 ] → 5 - 2 - 1 = 2번째 삽입

 

vector 자료 구조를 이용해서 쉽게 처리할 수 있다.

📌 [C++] [STL] Vector 사용 방법

[C++] [STL] Vector 사용 방법

 

C++

#include <iostream>
#include <vector>

using namespace std;

int N, pick;
vector<int> v;

int main()
{
	// freopen("input.txt", "r", stdin);
	
	scanf("%d", &N);
	for (int p=1; p<=N; ++p)
	{
		scanf("%d", &pick);
		v.insert(v.begin() + (p - pick - 1) , p);
	}

	for (auto el : v)
	{
		cout << el << " ";
	}
	cout << endl;	
}

 

Java

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		ArrayList<Integer> list = new ArrayList<>();

		int n = sc.nextInt();
		int arr[] = new int[n];

		for (int i = 0; i < arr.length; i++) {
			arr[i] = sc.nextInt();
			list.add(list.size()-arr[i],i+1);
		}

		int len = list.size();
		for (int i = 0; i < len; i++) {
			System.out.print(list.remove(0) + " ");
		}
	}
}