0x02.배열

정의와 성질

배열 - 메모리 상에 원소를 연속하게 배치한 자료구조

배열의 성질

1. o(1)에 K번째 원소를 확인/변경 가능

2. 추가적으로 소모되는 메모리의 양이 거의 없음

3. Cache hit rate가 높음

4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

하지만 임의의 위치에 원소를 추가 제거는 O(N) 그 이후로 한칸 미루거나 당겨야하기 때문

insert함수와 erase 함수 구현

void insert(int idx, int num, int arr[], int& len) {

	for (int i = len; i > idx; i--)
	{
		arr[i] = arr[i - 1];
	}
	arr[idx] = num;
	len++;
}

void erase(int idx, int arr[], int& len) {
	len--;
	for (int i = idx; i < len; i++)
	{
		arr[i] = arr[i + 1];
	}
	
}

사용팁

memset은 은 실수할 여지가 많음

for문은 투박하긴하지만 틀리지않음

fill 방식이 간결하고 좋음

• fill(arr,arr+len,0); *

벡터

for(int e : v1)
cout << e << ' ';
벡터의 모든 원소를 순회할때 범위 기반 for문을 사용 할수있음

연습문제

연습문제의 핵심은 정보를 저장하는 배열을 만드는것 이를 통해 이중 for문을 통해 해결해야할 문제들을 단일 for문으로 해결가능

문제

10808.알파벳 문제

#include <bits/stdc++.h>
using namespace std;

int arr[26];

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string s;

	cin >> s;

	for (char c : s)
	{
		arr[c - 'a']++;
	}
	for (int num : arr)
	{
		cout << num << ' ';
	}
}

연습문제에서 배운 방식으로 알파벳의 갯수만큼 26크기의 배열을 선언하고 알파벳이 나올때마다 count를 올려주면 쉽게 문제를 해결할수있다.

10807. 개수 세기

#include <bits/stdc++.h>
using namespace std;

int arr[201];

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,num;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> num;
		arr[num + 100]++;
	}

	cin >> num;

	cout << arr[num + 100];
}

이또한 숫자를 입력받고 배열의 값을 늘려주면된다 포인트는 입력되는값이 양수만있는것이 아닌 음수도있기때문에 +100을 해서 배열에 넣어주는것이다.

2577 . 숫자의 갯수

#include <bits/stdc++.h>
using namespace std;

int arr[10];

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int a, b, c;
	long long res;

	cin >> a >> b >> c;
	res = a * b * c;

	while (res > 0)
	{
		arr[res % 10]++;
		res /= 10;
	}

	for (int a : arr)
	{
		cout << a << '\n';
	}
}

%10 연산을 통해 끝자리 해당하는 배열의 값을 증가시키고 0이될때까지 10으로 나눠주는 방식으로 모든 자릿수의 숫자를 카운트한다.

11328 - Strfry

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int cnt;
	int arr_A[26];
	int arr_B[26];

	cin >> cnt;
	while (cnt--)
	{
		string a, b;
		string c = "Possible\n";
		cin >> a >> b;
		fill(arr_A, arr_A + 26, 0);
		fill(arr_B, arr_B + 26, 0);
		for (int i = 0; i < a.length(); i++)
		{
			arr_A[a[i] - 'a']++;
		}
		for (int i = 0; i < b.length(); i++)
		{
			arr_B[b[i] - 'a']++;
		}
		for (int i = 0; i < 26; i++)
		{
			if (arr_A[i] != arr_B[i])
			{
				c = "Impossible\n";
			}
		}
		cout << c;
	}
}

각 문자열을 구성하는 알파벳을 카운트해서 비교후 가능한지를 출력해준다.

13300 . 방배정

#include <bits/stdc++.h>
using namespace std;

int Room[2][7];

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, k,ans = 0;

	cin >> n >> k;;

	for (int i = 0; i < n; i++)
	{
		int man,grade;

		cin >> man >> grade;

		Room[man][grade]++;
	}

	for (int i = 0; i < 2; i++)
	{
		for (int j = 1; j <= 6; j++)
		{
			while (Room[i][j] > 0)
			{
				ans++;
				Room[i][j] -= k;
			}
		}
	}

	cout << ans;
}

Room 2차원 배열에 성과 학년에 맞게 인원수를 체크해준뒤 한방의 정원수 K를 0보다 클때 동안 빼주면서 방수를 구해주면된다.

1475 . 방번호

#include <bits/stdc++.h>
using namespace std;

int number[10];

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,imax = 0;
	cin >> n;

	if (n == 0)
	{
		imax = 1;
	}


	while (n > 0)
	{
		number[n % 10]++;
		n /= 10;
	}

	imax = max(imax,(int)ceil(float((number[6] + number[9])) / 2.0));

	for (int i = 0; i < 10; i++)
	{
		if (i == 6 || i == 9)
		{
			continue;
		}
		if (imax < number[i])
		{
			imax = number[i];
		}
	}
	

	cout << imax;
}

1,000,000 이하의 숫자에 사용된 숫자의 갯수를 구하는 문제이다 중요한점은 6과 9를 한세트처럼 묶어서 사용할수있다는 점이다 우선 입력이 0인경우 를 예외처리 해주고 6과 9를 더해 2로나누어 최대값과 비교후 넣어준다 ( 만약 0일경우 이미 0만 한번 사용되어 1이라 1이 정답이 되어야함) 그 이후 숫자를 셀때 6과 9는 넘겨준다.

1919 . 에너그럼 만들기

#include <bits/stdc++.h>
using namespace std;

int alpha1[26];
int alpha2[26];


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string str1, str2;

	int ans = 0;

	cin >> str1 >> str2;

	for (char c : str1 )
	{
		alpha1[c - 'a']++;
	}

	for (char c : str2)
	{
		alpha2[c - 'a']++;

	}

	for (int i = 0; i < 26; i++)
	{
		ans += abs(alpha1[i] - alpha2[i]);
	}

	cout << ans;
}

두 문자열의 다른 알파벳갯수를 알아내면 몇글자를 제거했을때 에너그램을 만들수있는지 알수있다.
두 문자열의 알파벳을 분석하고 빼준후 절대값을 취해 차이를 총합하면 답을 구할수있다.

3273 . 두 수의 합

#include <bits/stdc++.h>
using namespace std;


map<int,int> bnumber;

int inumber[1000001];


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,ans = 0,k;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> inumber[i];
		bnumber.emplace(inumber[i], i);
	}
	cin >> k;
	for (int i = 0; i < n; i++)
	{
		
		if (bnumber.find(k-inumber[i]) != bnumber.end() && i > bnumber.find(k - inumber[i])->second)
			ans++;
	}

	cout << ans;
}

들어온 순서를 저장하기위해 맵 STL 을 사용했습니다.

수열의 길이 n을 입력받은뒤 반복문을 통해 <숫자,들어온선> 를 맵으로 저장합니다

다음 k를 입력받고 inumber를 앞에서부터 탐색하며 map에 k에서 inumber[i] 를 뺀 값이 있는지 확인한뒤 이값이 들어온 순서가 현재 보고있는 i보다 큰지 검사한후 맞다면 정답을 1늘려줍니다.

느낀점

거의 모든 문제의 기초가 되는 배열 문제들을 풀어봤습니다. 처음 시작하는 부분이라 어려운 문제보다는 기초를 다지는 문제들이여서 무난하게 해결할수있었습니다.