1.알파벳 기준 절반이상이면 왼쪽으로 이동하는것이 이득, 아니라면 오른쪽으로 이동하는것이 이득
2.커서도 동일하게 길이의 절반이상이면 왼쪽으로 이동하는 것이 이득, 아니라면 오른쪽으로 이동
이렇게 생각하고 min으로 A부터 움직였을 때와 Z부터 움직였을 때의 최소값을 구한다.
그리고 커서를 움직이는 것을 생각해보면
왼쪽으로 움직일때와 오른족으로 움직일때의 최솟값을 계산하면 된다.
#include <string>
#include <algorithm>
using namespace std;
//알파벳 기준 절반이상이면 왼쪽으로 이동하는것이 이득, 아니라면 오른쪽으로 이동하는것이 이득
//커서도 동일하게 길이의 절반이상이면 왼쪽으로 이동하는 것이 이득, 아니라면 오른쪽으로 이동
int solution(string name) {
int n = name.length();
int answer = 0;
// 각 알파벳을 바꾸는 데 필요한 조작 횟수를 합산
for (int i = 0; i < n; ++i) {
answer += min(name[i] - 'A', 'Z' - name[i] + 1);
}
// 커서 이동의 최소 조작 횟수를 구함
int move = n - 1;
for (int i = 0; i < n; ++i) {
int next = i + 1;
while (next < n && name[next] == 'A') { //A건너뛰기
++next;
}
move = min(move, i + n - next + min(i, n - next)); //왼쪽으로 갈때, 오른쪽으로 갈때 비교
}
return answer + move;
}
// Fill out your copyright notice in the Description page of Project Settings.
#pragma once
#include "CoreMinimal.h"
#include "GameFramework/Actor.h"
#include "Item.generated.h"
UCLASS()
class SLASH_API AItem : public AActor
{
GENERATED_BODY()
public:
// Sets default values for this actor's properties
AItem();
protected:
// Called when the game starts or when spawned
virtual void BeginPlay() override;
public:
// Called every frame
virtual void Tick(float DeltaTime) override;
};
리플랙션 코드와 액터의 기능을 쓸 수 있게하는 헤더 파일들과 AActor를 상속받고 있는 모습을 볼 수 있다.
Item.cpp
// Fill out your copyright notice in the Description page of Project Settings.
#include "Items/Item.h"
// Sets default values
AItem::AItem()
{
// Set this actor to call Tick() every frame. You can turn this off to improve performance if you don't need it.
PrimaryActorTick.bCanEverTick = true; //매틱마다 실행되도록
}
// Called when the game starts or when spawned
void AItem::BeginPlay()
{
Super::BeginPlay();
}
// Called every frame
void AItem::Tick(float DeltaTime)
{
Super::Tick(DeltaTime);
}
Actor 쪽에서 무언가 구현할 것을 대비하여 부모쪽의 BeginPlay를 실행하기위해 Super::로 실행한다.
이제 만든 클래스를 바탕으로 블루프린트를 만들어보자
모든 액터는 초기에 DefaultSceneRoot라는 Component를 가지고 있다.
모든 블루프린트에는 이벤트 그래프가 있는데 이것은 블루프린트를 통해 코드의 흐름을 작성하고 실행시킬 수 있는 도구이다.
예를 들면 Begin Play 이벤트 즉 시작할 때 String을 화면에 띄우는 기능을 블루프린트를 통해 구현할 수 있는 것이다.
그리고 다음은 Construction Script이다
이것은 게임이 시작되기 전에 실행되며 블루프린트의 속성이 바뀔 때 실행된다.
그리고 만약 이 함수가 실행되는 곳, 즉 액터와 너무 멀리있다면 실행결과가 화면에 보이지 않는다
이제 이것을 C++를 통해 구현해보자
// Called when the game starts or when spawned
void AItem::BeginPlay()
{
Super::BeginPlay();
UE_LOG(LogTemp,Warning,TEXT("Begin Play called!"));
}
최소성 : 여러 속성을 조합해 만든 키가 유일성을 가질 때, 한 속성을 제외해도 유일성이 유지되면 최소성을 만족하지 않는다.
어떻게 검사할까 찾아보다가 비트마스크 방법으로 조합과 유일성 최소성 검사를 하는게 직관적이라는 것을 알게 되었다.
조합
각 열을 하나의 비트로 나타내면, 비트마스크의 각 비트는 열의 포함 여부를 나타낼 수 있다.
예를 들어, 열이 3개인 경우:
000: 아무 열도 포함하지 않음
001: 첫 번째 열만 포함
010: 두 번째 열만 포함
011: 첫 번째와 두 번째 열 포함
100: 세 번째 열만 포함
101: 첫 번째와 세 번째 열 포함
110: 두 번째와 세 번째 열 포함
111: 모든 열 포함
이런식으로 표현할 수 있다.
이 방법을 통해 조합을 생성하려면 2^열의 수로 순회하면 된다.
조합
// 모든 가능한 속성 조합을 생성
for (int comb = 1; comb < (1 << columns); comb++) {
// 유일성과 최소성 검사
if (isUnique(relation, columns, comb) && isMinimal(comb, candidateKeys)) {
// 유일성과 최소성을 만족하는 경우 후보키로 추가
candidateKeys.push_back(comb);
}
}
유일성 검사
유일성 검사또한 비트마스크를 통해 열 포함여부를 검사해준다.
// 유일성을 검사하는 함수
bool isUnique(vector<vector<string>>& relation, int columns, int comb) {
set<string> uniqueCheck;
for (int i = 0; i < relation.size(); i++) {
string key = "";
for (int j = 0; j < columns; j++) {
// comb의 각 비트를 확인하여 해당 열을 포함하는지 검사
if (comb & (1 << j)) {
key += relation[i][j] + " ";
}
}
// 유일성 검사: 이미 존재하는 키라면 false 반환
if (uniqueCheck.find(key) != uniqueCheck.end()) {
return false;
}
uniqueCheck.insert(key);
}
return true;
}
이때 직접적인 검사는 if (comb & (1 << j)) 부분에서 이루어진다.
comb & (1 << j) 이 부분에서 어떻게 계산이 이루어지는지는 예시를 통해 알아보자
comb의 j번째 비트가 1인지 검사하려면, 1 << j를 사용하여 j번째 비트만 1인 숫자를 만든다.
comb & (1 << j)를 수행하면, comb의 j번째 비트가 1일 때만 결과가 1이 됩니다. 그렇지 않으면 결과가 0이 된다.
comb = 5 (0101)
열의 개수 columns = 4
j = 0:
1 << 0는 0001
comb & 0001은 0101 & 0001이므로 결과는 0001 (참)
j= 1:
1 << 1은 0010
comb & 0010은 0101 & 0010이므로 결과는 0000 (거짓)
j = 2:
1 << 2은 0100
comb & 0100은 0101 & 0100이므로 결과는 0100 (참)
j = 3:
1 << 3은 1000
comb & 1000은 0101 & 1000이므로 결과는 0000 (거짓)
j = 0과 j = 2에서 조건이 참이므로, 첫 번째와 세 번째 열의 값이 key에 추가
최소성 검사
기존 후보키로 만들어진 것이 현재 조합의 부분집합에 포함된다면 후보키가 아니다.
// 최소성을 검사하는 함수
bool isMinimal(int comb, vector<int>& candidateKeys) {
// 기존의 후보키들에 대해 검사
for (int key : candidateKeys) {
// 기존의 후보키가 현재 조합에 포함되는지 검사
if ((comb & key) == key) {
// 기존 후보키가 현재 조합의 부분집합이면 최소성 만족하지 않음
return false;
}
}
// 모든 기존 후보키가 현재 조합의 부분집합이 아니면 최소성 만족
return true;
}
전체코드
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
// 유일성을 검사하는 함수
bool isUnique(vector<vector<string>>& relation, int columns, int comb) {
set<string> uniqueCheck;
// 각 튜플(행)에 대해 검사
for (int i = 0; i < relation.size(); i++) {
string key = "";
// comb의 각 비트를 확인하여 해당 열을 포함하는지 검사
for (int j = 0; j < columns; j++) {
if (comb & (1 << j)) {
// comb의 j번째 비트가 1이면 해당 열을 key에 추가
key += relation[i][j] + " ";
}
}
// 유일성 검사: 이미 존재하는 키라면 false 반환
if (uniqueCheck.find(key) != uniqueCheck.end()) {
return false;
}
// 새로운 키를 set에 추가
uniqueCheck.insert(key);
}
// 모든 튜플에 대해 유일성을 만족하면 true 반환
return true;
}
// 최소성을 검사하는 함수
bool isMinimal(int comb, vector<int>& candidateKeys) {
// 기존의 후보키들에 대해 검사
for (int key : candidateKeys) {
// 기존의 후보키가 현재 조합에 포함되는지 검사
if ((comb & key) == key) {
// 기존 후보키가 현재 조합의 부분집합이면 최소성 만족하지 않음
return false;
}
}
// 모든 기존 후보키가 현재 조합의 부분집합이 아니면 최소성 만족
return true;
}
int solution(vector<vector<string>> relation) {
int rows = relation.size(); // 튜플(행)의 개수
int columns = relation[0].size(); // 속성(열)의 개수
vector<int> candidateKeys; // 후보키를 저장할 벡터
// 모든 가능한 속성 조합을 생성
for (int comb = 1; comb < (1 << columns); comb++) {
// 유일성과 최소성 검사
if (isUnique(relation, columns, comb) && isMinimal(comb, candidateKeys)) {
// 유일성과 최소성을 만족하는 경우 후보키로 추가
candidateKeys.push_back(comb);
}
}
// 후보키의 개수 반환
return candidateKeys.size();
}
int main() {
vector<vector<string>> relation = {
{"100", "ryan", "music", "2"},
{"200", "apeach", "math", "2"},
{"300", "tube", "computer", "3"},
{"400", "con", "computer", "4"},
{"500", "muzi", "music", "3"},
{"600", "apeach", "music", "2"}
};
cout << solution(relation) << endl; // 출력: 2
return 0;
}
