오늘 한 내용
- C++ 코드카타
- C++와 Unreal Engine으로 3D 게임 개발 강의 수강
- AI Model 캐릭터 생성
코드카타 문제
프로그래머스 - 롤케이크 자르기 : https://school.programmers.co.kr/learn/courses/30/lessons/43165
간단히 말해서 롤케이크 한 조각마다 토핑이 들어있고, 철수와 동생이 여러 종류의 토핑을 공평하게 먹을 수 있는 방법의 개수를 구하는 문제였다.
일단, "토핑의 종류"에만 관심이 있다는 것으로 보아 set 자료구조를 사용하는 것이 유리해보였다.
그래서 한 번 순회하는 경우마다 set을 구성함으로써, set의 크기가 같으면 경우의 수를 반환하는 방식으로 풀었었다.
그런데 시간 초과가 났다. 그 이유는 최대 케이스가 1,000,000이라서, 한 번 순회(n) x set 구성(n) -> 총 O(N^2)의 시간 복잡도를 지녔기 때문이다.
그래서 다시 생각해보았을 때 아래와 같은 방향으로 접근해보았다.
- 정렬과는 상관 없으니 unordered를 붙여야 함
- 한 쪽이 먼저 롤케이크를 전부 가지고 한 조각씩 나눠줘보는 것
먼저, 한 쪽에서 몰아서 가지고 있는 경우에는 자신이 조각을 몇 개를 가지고 있는지를 특정해야 하므로 map을 선언한다.
앞쪽부터 한 조각씩 잘라서 제공해준다. 여기서는 1을 제공한다. 이때, map의 value도 감소해준다. 이때, set의 크기와 map의 키 개수가 같은지를 매번 확인한다.
다음은 2를 제공해준다. 여기서 map의 value값이 0이면 자신이 지니는 "토핑 0"이 없다는 것이므로 제외해준다. set 크기와 map의 키 개수가 같으므로 count를 1 증가시켜준다.
이러한 방식으로 한 쪽이 롤 케이크를 다 줄 때까지 위의 검사를 진행하면 된다.
유의할 점은 절반까지 주는 것이 아니라 다 줘야 한다는 점이다. 토핑이 1개로만 가득차있으면 롤 케이크 조각 개수와 상관없이 계속 카운트가 된다.
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int solution(vector<int> topping) {
int answer = 0;
unordered_set<int> left;
unordered_map<int, int> right;
for (int n : topping) // 일단 한 쪽에 몰빵
{
right[n]++;
}
for (int n : topping)
{
left.insert(n); // 다른 한 쪽에 한 조각씩 넘겨줌
right[n]--;
if (right[n] == 0) // 해당 토핑이 자신에게 없으면 제거
{
right.erase(n);
}
if (left.size() == right.size())
{
answer++;
}
}
return answer;
}이 문제를 푸는 데에도 시간을 좀 쓰긴 했지만, 사실 오늘 제일 시간을 많이 쓴 건 플랫포머 캐릭터를 생성하기 위해 AI Model 제작에 시간을 많이 투자했던 것 같다.
실패한 내용 밖에 없기도 하고 흐름의 유지를 위해서 플랫포머 프로젝트 정리할 때 언급할 예정이다.
