• 문제

• 풀이

#include <iostream>
using namespace std;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n = 0;
    cin >> n;

    for (int y = 1; y <= n; y++)
    {
        for (int x = 1; x <= n - y; x++)
        {
            cout << ' ';
        }
        for (int x = 1; x <= 2 * y - 1; x++)
        {
            cout << '*';
        }

        cout << '\n';
    }
}

• 메모

예제 입출력 부분을 살펴보면 세로에 해당하는 y 값은 1씩 증가하며
가로에 해당하는 x의 경우 i번째 줄에서 공백의 개수는 N - i개가 되고, 별의 개수는 2 * i - 1개가 된다.

따라서 입력받은 n까지 y값을 하나씩 증가시키면서 내부에서 2개의 for문을 따로 돌려서 각각 공백과 별을 출력하도록 한다.

입력받은 N을 기준으로 공백과 별을 출력하며 이때 개수는 N에 비례하기 때문에 이 코드의 전체 시간 복잡도는 O(n^2)가 된다.
다만 입력 부분을 보면 N의 최대값이 100 밖에 되지 않기 때문에 n^2가의 시간 복잡도를 가지고 있다해도 그렇게 많은 시간이 소모되진 않는다.

• 문제

• 풀이

#include <iostream>

using namespace std;

long long a;
long long b;

int main()
{
	cin >> a >> b;

	if (a < b)
	{
		swap(a, b);
	}

	if (a == b || b - a == 1)
	{
		cout << 0;
	}
	else
	{
		cout << a - b - 1 << '\n';
		for (long long i = b + 1; i < a; i++)
		{
			cout << i << ' ';
		}
	}

	return 0;
}

• 문제

• 풀이

입력받은 값을 배열에 쭉 저장한 뒤, 두 값이 합쳐졌을 때 x가 되는 경우를 판단해야 하는 문제이다.

뭔가 답이 알듯말듯해서 혼자 고민하다가 다른 분의 풀이(https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x03/solutions/3273.cpp) 를 참고했다. 이미 너무 깔끔한 코드인데 개인적으로 조건문 내부에서 사칙연산을 그대로 넣는 걸 좋아하지 않아서 value 변수로 따로 빼주었다.

#include <iostream>
using namespace std;

int a[1000001] = {};
bool occur[2000001];
int n, x;

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

    int ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> x;

    for (int i = 0; i < n; i++) {
        int value = x - a[i];
        if (value > 0 && occur[value]) ans++;
        occur[a[i]] = true;
    }
    cout << ans;
}

풀이 코드에선 occur 배열을 사용해 이미 등장한 숫자를 기록하고, 이를 통해 각 숫자와 x를 만들 수 있는 수의 존재 여부를 빠르게 확인할 수 있다. 작동 원리는 다음과 같다.

1. 먼저 각 원소 a[i]에 대해 x - a[i]를 계산하여 occur[x - a[i]]의 값을 확인해 해당하는 값이 존재하는지 확인한다.

2. 만약 occur[x - a[i]]가 true이면, 이는 이전에 등장한 수 중 x - a[i]가 존재함을 의미한다. 따라서 a[i]와 x - a[i]의 합이 x가 되는 쌍이 존재하므로, ans를 1 증가시킨다.

3. 이후 occur[a[i]] = true;로 a[i]가 등장했음을 기록해준다.

중복 검사는 occur 배열을 통해 O(1) 시간에 이루어지고, 숫자의 등장 횟수를 따로 기록하였기 때문에 occur[x - a[i]]만 확인하므로 전체 시간 복잡도는 O(n)가 된다.

아이디어가 좋은 풀이라 다음에 비슷한 문제가 또 있으면 이걸 참고해서 혼자 풀어봐야겠다.

• 문제

• 풀이

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	string n = "";
	int arr[10] = { 0, };

	cin >> n;

	for (char c : n)
	{
		arr[c - '0']++;
	}

	arr[6] = (arr[6] + arr[9] + 1) / 2;

	int max = 0;

	for (int i = 0; i < 9; i++)
	{
		if (max < arr[i])
		{
			max = arr[i];
		}
	}

	cout << max << endl;

	return 0;
}

문제를 읽어보면서 2가지를 떠올렸다.

1. 입력받은 값중에 가장 많이 등장한 값의 수가 필요한 세트의 수가 된다.

2. 6과 9는 서로 호환가능하기 때문에 한 세트에 2개까지 사용할 수 있다. 이를 따로 처리해주어야 한다.

따라서 우선 string으로 값을 받아서, 배열의 인덱스를 입력받은 값 - '0'으로 해서 저장해주었다.

문제에서 6과 9는 서로 호환이 가능하다고 했으므로 하나에 몰아서 비교하기 위해 arr[6]에 [9]의 값을 추가해주었다.

이때 홀수개로 값이 떨어지는 경우에는 추가로 한 세트를 더 필요로 하기 때문에 (arr[6] + arr[9] + 1)을 해주고 그 값을 / 2 했다.

이미 arr[9]의 값은 arr[6]에 반영되어 있기 때문에 max 값을 비교할 때는 범위를 0부터 9미만으로 두고 하나씩 값을 순회하며 최종 max 값을 구했다. 이 max 값이 바로 문제에서 요구하는 필요한 세트의 수가 되므로 최종적으로 이 값을 출력해주었다.

• 개선

글을 작성하면서 코드를 다시 보니 max 값을 구할 때 그냥 max 함수를 사용했어도 되었을 것 같아 max 함수 사용에 익숙해질겸 그 부분만 추가로 수정해보았다.

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	string n = "";
	int arr[10] = { 0, };
        int result = 0;

	cin >> n;

	for (char c : n)
	{
		arr[c - '0']++;
	}

	arr[6] = (arr[6] + arr[9] + 1) / 2;

	for (int i = 0; i < 9; i++)
	{
		result = max(result, arr[i]);
	}

	cout << result << endl;

	return 0;
}

• 다른 풀이 (출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x03/solutions/1475.cpp)

// Authored by : OceanShape
// Co-authored by : BaaaaaaaaaaarkingDog, kiiimiiin
// http://boj.kr/a7a4aa95c4ee446990f868f926993161
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int N, a[10] = {}, ans = 0;
  cin >> N;
  
  // 자리수 추출
  while(N){
    a[N%10]++;
    N /= 10;
  }

  for(int i = 0; i < 10; i++){
    if(i == 6 || i == 9) continue;
    ans = max(ans, a[i]);
  }
  // (a[6]+a[9])/2를 올림한 값이 6, 9에 대한 필요한 세트의 수이므로 (a[6]+a[9]+1)/2을 계산
  ans = max(ans, (a[6]+a[9]+1)/2);
  cout << ans;
}

string 대신에 int로 값을 받아 while문 안에서 자리수마다 숫자를 하나씩 떼어내 그것을 인덱스로 사용해 배열에 저장하는 방식이 사용되었다. 우선 max 값을 구하는 동안 인덱스가 6과 9인 경우는 제외 한 뒤, 마지막에 다시 한번 기존의 max값과 6과 9의 필요 세트 수를 비교해서 최종적으로 결정된 값을 출력했다.

코드 길이도 더 간결하고 메모리도 4kb 차이긴 하지만 이쪽이 더 경량화 되었다. 아이디어를 참고해서 다음 문제 풀이에서는 이 방식으로 풀어봐야겠다.