🙇‍♀️[Silver II] 한 줄로 서기 - 1138

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

구현

제출 일자

2024년 2월 29일 16:16:40

문제 설명

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

🚀풀이

it문제푸는 강의에서 Inversion Sequence 문제와 완전히 동일했다.

선택 정렬을 응용해서 푸는 문제로 input와 output 배열 두 개를 만들어서 풀었다.

int n;
int is[11], os[11];

void solve()
{
    // 입력값 받기
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> is[i];
	}

    // 마지막부터 순회한다.
	for (int i = n; i >= 1; --i)
	{
		int val = is[i];
        // is의 값 만큼 앞쪽으로 이동시킨다.
		for (int j = i; j < i + val; ++j)
		{
			os[j] = os[j + 1];
		}
        // i값을 마지막 위치에 넣는다.
		os[i + val] = i;
	}

    // 정답 출력
	for (int i = 1; i < 11; ++i)
	{
		if (os[i] == 0)
			break;
		cout << os[i] << " ";
	}
}

image

실버2 문젠데 레이팅을 안준다.. 1점도 안주는건 좀 너무하네..

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int n;
int is[11], os[11];

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> is[i];
	}

	for (int i = n; i >= 1; --i)
	{
		int val = is[i];
		for (int j = i; j < i + val; ++j)
		{
			os[j] = os[j + 1];
		}
		os[i + val] = i;
	}

	for (int i = 1; i < 11; ++i)
	{
		if (os[i] == 0)
			break;
		cout << os[i] << " ";
	}
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고