배열 삽입

#include <iostream>
#include <string>

using namespace std;
#define MAXVAR 10000

struct Array {
	void at(int i);
	void set(int i, int X);
	void add(int i, int X);
	int array[MAXVAR] = { 0, };
};

void Array::at(int i)
{
	if (array[i] == 0)
		cout << 0 << "\n";
	else
		cout << array[i] << "\n";
}

void Array::set(int i, int X)
{
	if (array[i] == 0)
	{
		if (array[0] == 0)
			array[0] = X;
		cout << 0 << "\n";
	}
	else
		array[i] = X;
}

void Array::add(int i, int X)
{
	int num = i;
	if (array[num] == 0)
	{
		while (array[num] == 0)
			--num;
		array[num + 1] = X;
	}
	else
	{
		int j;
		for (j = 0; array[j] != 0 && j < MAXVAR - 1; j++);
		for (; j  > i; j--)
		{
			array[j] = array[j - 1];
		}
		array[i] = X;
	}
}

int main()
{
	Array ar;
	int m;
	cin >> m;
	string str;
	
	for (int i = 0; i < m; i++)
	{
		cin >> str;
		int idx;
		cin >> idx;
		if (str == "at")
		{
			ar.at(idx);
		}
		else if (str == "set")
		{
			int X;
			cin >> X;
			ar.set(idx, X);
		}
		else if (str == "add")
		{
			int X;
			cin >> X;
			ar.add(idx, X);
		}
	}
	return 0;

}

문제
양의 정수를 원소로 가지는 배열을 이용하여 다음의 명령어들을 처리하는 프로그램을 작성하시오.
(단 배열의 원소들은 반드시 배열 내 index 0부터 연속해서 저장 되야 한다
(주어진 배열의 크기는 [10000] / 배열 전체 0으로 초기화 / 배열 내 0은 원소가 아니다)
명령어는 다음과 같이 총 3가지이다.
 at(i): 배열의 인덱스 i에 저장된 양의 정수를 출력. 만약 원소가 없는 인덱스 i값이 주어지면 0을 출력
 set(i, X): 배열의 인덱스 i에 저장된 양의 정수를 X값으로 덮어씌운다. 만약 원소가 없는 인덱스 i값이 주어지면 0을 출력
 add(i, X): 배열의 인덱스 i보다 크거나 같은 곳에 저장된 값을 +1 칸씩 이동시키고 인덱스 i에 양의 정수 X를 삽입. 만약 원소가 없는 인덱스 i값이 주어지면 마지막 원소가 있는 바로 다음 인덱스에 양의 정수 X를 삽입 (원소가 없을 경우 첫 번째 인덱스에 삽입)
입력
첫번째 줄에 명령어의 수 M (1 ≤ M ≤ 10 0 00) 이 주어진다 두 번째 줄부터 M 개의 줄에는 명령어가 하
나씩 주어진다 (1 ≤ X ≤ 10 0 00) (0≤ i 1 0, 000) ( 배열 사이즈 N=10 0 0 0)
출력
출력해야하는 명령어가 주어질 때마다 그 결과를 한 줄씩 출력한다

STL사용하면 안되구요
코드는 짜긴 짰는데 돌아가긴 돌아갑니다.
근데 너무 복잡하게 한거 같아서 간단하게 고칠수 있는지 알고 싶습니다.
또 array[j] = array[j - 1]; 부분에서 배열 사이즈를 초과하는지 오류문구가 생깁니다.
그래서 일부러 j < MAXVAR - 1 조건을 넣었는데 이렇게 하면 안되는 건가요?
도움 부탁드립니다.

안녕하세요!

항상 열심히 과제하시느라 고생하시네요 ㅎㅎㅎ

하나씩 같이 봅시다 ㅎㅎㅎ

void Array::at(int i)
{
	if (array[i] == 0)
		cout << 0 << "\n";
	else
		cout << array[i] << "\n";
}

보시면 아시겠지만 값은 양의 정수이거나 0이죠? 그러면 condition statement 없이 그냥 해당 인덱스의 배열 값을 출력해도 되겠죠?

void Array::set(int i, int X)
{
	if (array[i] == 0)
	{
		if (array[0] == 0)
			array[0] = X;
		cout << 0 << "\n";
	}
	else
		array[i] = X;
}

그런데 일단 문제에서 array[0] 을 수정하라는 부분은 없잖아요. 수정하지 마시고 0 출력하세요.

자 이부분이 관건인거 같은데. 크게 2가지로 나눌 수 있죠. (넣을 수 없을땐 어떻게 해야하는지 정의되지 않았다니…ㄷㄷ)

  1. i 보다 크거나 같은 곳에 저장된 값을 이동시킨 후 중간에 삽입.
  2. 비어있는 공간이면 마지막에 삽입.
void Array::add(int i, int X)
{
	int num = i;
	if (array[num] == 0)
	{
		while (array[num] == 0)
			--num;
		array[num + 1] = X;
	}
	else
	{
		int j;
		for (j = 0; array[j] != 0 && j < MAXVAR - 1; j++);
		for (; j  > i; j--)
		{
			array[j] = array[j - 1];
		}
		array[i] = X;
	}
}

한가지 팁을 알려드리면.

현재 배열에서 어디까지 값이 입력되어있는지를 나타낼 변수를 하나 정의하세요.
편의상 int len이라고 하겠습니다.
예를들어 배열에 3가지 값, 즉 인덱스가 0,1,2에 해당하는 곳에 값이 입력되어있다면
이 변수는 3이라는 값을 갖는거죠.

  1. 비어있는 공간이면 마지막에 삽입.

그렇다면 그 변수를 이용하여 이건 어떻게 해결할 수 있을까요?
만약 len보다 크거나 같은 값이 add의 인덱스로 들어온다면
번거롭게 찾을 필요없이 array[len] 에 값을 대입하고, 변수를 1증가시키면 됩니다.

이해되시나요?

  1. i 보다 크거나 같은 곳에 저장된 값을 이동시킨 후 중간에 삽입.

이건 어떻게 해야할까요?

len - 1 부터 주어진 i까지 변수를 각각 한칸씩 앞으로 이동하면 되겠죠?

for (int j = len; j < i; ++j)
    array[j] = array[j - 1]

대충 이렇게 되겠죠? 물론 옮긴 후 len값을 1 증가시키는걸 잊지마시고요.
그리고 len이 MAXVAR과 같을 때, 즉 배열이 꽉차있을때 더 넣을 수 없잖아요.
그때는 다르게 처리해줘야 합니다.

마지막으로 한번 set 함수로 돌아가보죠.

마찬가지로 i값이 len값보다 작아야 array[i]에 0이 아닌
유효한 값이 들어가있다는 걸 바로 알 수 있겠죠?

그러면 굳이 배열값을 비교할 필요없이 len과 비교해도 되겠죠?

도움이 되었으면 좋겠네요. ^^
건승하세요~

4 Likes

와 친절한 답변 감사합니다.
말씀해주신대로 코딩하니 간단하게 되네요.
자료구조 벡터도 배웠는데 사이즈를 변수로 두면 안되는줄 알고 코딩한건데 조건이 없으니깐 해도 되는 것이군요.
답변해주셔서 다시한번 감사합니다.

1 Like