[백준/1475번/C++] 방 번호

• 문제

 

• 풀이

#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 차이긴 하지만 이쪽이 더 경량화 되었다. 아이디어를 참고해서 다음 문제 풀이에서는 이 방식으로 풀어봐야겠다.