두 부품의 기둥 면을 마주하여 조립하면, 완벽히 일치(기둥 사이에 틈새가 존재하지 않는)하는 육면체 완성품을 얻을 수 있다.
이렇게 조립한 육면체의 높이는 8이 된다. 이때 이 육면체 완성품은 재사용될 수 있으므로, 절약되는 비용은 육면체의 높이 8만큼이다.
밑면의 [가로 x 세로] 넓이가 각각 [4 x 4]인 블록 부품이 30,000개 주어질 때, 절약되는 완성품들의 총 합이 최대가 되도록 하자.
※ 한개의 완성품은 항상 두개의 블럭으로 구성된다.
▶ 절약되는 완성품들의 총 합의 최대값을 반환하는 makeBlock() 함수를 작성하라.
일일이 두개씩 골라서 다 비교하면 4x4 x 30000 x 29999 = 16*9*10^8
절약되는 값이 최대가 되게 하려면 음 기둥 높이가 2,3,5,8 가 있으면 어차피 높이 합은다 똑같으니까 누구랑 결합하느냐가 중요한건 아닌거 같고 그냥 결합할 수 있으면 결합하면 되는건가? 근데 a b c d면
a는 b,c랑 결합되고 c,d가 되면 a,d도 결합되는거 잔아. 왜냐면 a가 홈이 c랑 맞는데 c가 d랑 맞으면 a도 d랑 맞는거지....
1. 음 결국에는 일단 결합할 수 있는지 확인하는게 필요하다.
이 부분은 4번 회전해보고 둘이 결합 가능한지 (더한 높이들이 같은지 확인해보면 된다.)
2. 그리고 결합은 그냥하면된다. 근데 최적화하기 위해서 생각해야 하는것이 생각났다.
3. abcdef 있을때
a가 bdf랑 결합 불가다. c,e랑 결합(결합 할 수 있으면 끝내는게 맞는지 아니면 쭉 해봐?).
그러면 음 bdf는 해볼 것도 없이 c,e랑은 결합이 안된다
음 즉 결합 쌍이 나오면 다른 결합 불가놈들도 결합 가능한 놈이랑 해볼 것도 없이 결합 불가인데.
음ㅋㅋ 이게 문제 푸는데 의미가 있나? 그냥 결합쌍 찾으면 그 두개는 아예 배제하면 뭐 다시 확인할 것도 없잔아.
3은 별로 최적화할게 없는건가.
그럼 1에서 최적화를 해보면...
전부 돌리고 전부 매치되는지 확인하기 전에 확인할 수 있는 방법이 있나. 굳이 ....?
음 왠지 빠르게 하는걸 생각하다가 해쉬를 이용한 방법을 계속생각했다.
3 2 2 2
1 2 2 3
1 3 1 3
2 2 3 1 이면
1: 4개
2: 7개
3: 5개
6(0,0) 6(0,1) 6(0,2) 5(0,3)
5(1,0) 6(1,1) 6(1,2) 7(1,3)
5(2,0) 7(2,1) 5(2,2) 7(2,3)
7(3,0) 5(3,1) 6(3,2) 6(3,3) 이걸 90도 회전해야 하는데 전에 해봤는데 음 다시 보니까 모르겠다.
0,0->0,3
0,1->1,3
1,1->1,2
3,0->0,0
3,1->1,0
i,j -> j,4-1-i
5: 5개
6: 7개
7: 4개
음 일단 475 , 574 개씩 갯수만 맞으면 되는거 아닌가? 아 아니구나 위치도 맞아야되지.
근데 4개는 4개 끼리 5는 5끼리 해서 457 457만이 매칭가능하다 일단은.
즉 갯수만 세면 일단 가능성 높은거 끼리 확인할 수 있을듯!.!!
1. 숫자 3개의 갯수가 같아야 한다.
2. 같은 갯수인 높이끼리 더하면 셋이 같아야 한다. 같은 해쉬인덱스를 가지면 같은 애들이긴해 일단은.
2-1. 근데 여기서 링크드 리스트에서 두놈씩 비교해야 되는건가?
3. 이제 회전으로 위치도 같은지 확인하면 된다. -> 좀더 효율적으로 확인 가능할듯 위치만 확인하면 되니까.
457개면 4,5개의 위치끼리만 일치해도 7개인 위치는 당연히 일치할 수 밖에 없는거다.
3-1. 일치하면 어떻게해? 두개를 링크드 리스트에서 제거하고, saved 절약된 값을 더해주고.
음 그런데 위치를 저장하기가 어렵다. ㅋㅋ 위치를 어떻게 저장하고 확인하지.??? 저장은 해도 회전이 너무 어려운데.
걍 이부분은 패스 못하겠어.
해쉬 맵으로 저장한다.
//세개 숫자 쌍이니까 1000보다 작다.
hash[1000] ;
#include<iostream>
using namespace std;
struct Block{
//해당 높이가 몇개 있는지.
int block_height[10] = { 0 };
//해당 높이가 뭐있는지 3개.
int height[3] = { 0 };
int index;
int arr[4][4];
Block * prev= NULL,*next=NULL;
};
class BlocksHash {
private:
Block * head[1000] = { NULL };
Block * tail[1000] = { NULL };
int Size[1000] = { 0 };
int saved = 0;
public:
//해당 모듈을 해쉬맵에 넣는다. 그런데 해쉬 인덱스가 오름차순으로 정렬해야 한다.
void push(int module[][4]);
//해당 인덱스의 리스트에서 첫째로는 3개높이의 갯수가 일치하는지 확인하고
//일치하면 2개씩 비교(isMatch)한다.
void compareList(int index);
//두 블록안의 각 블록들의 위치들이 갯수에 맞게 일치하는지 확인한다.
//위치에 따른 구현은 내가 못하겠어서 그냥 회전해서 전체를 비교하는 식으로 해야
//될거 같다.
//근데 모듈을 여기 넣어도 되는건가....
int isMatch(Block *a, Block*b);
//해당 블록 해쉬맵에서 제거.
void pop(Block*a);
//모듈을 90도 회전한다.
void rotate90(int module[][4]);
};
BlocksHash hash;
//이 부분 구현이 어렵다.. pop 했을때 연속성있게 두개를 비교하기가
void BlocksHash::compareList(int index) {
Block* cur,*other;
cur = head[index];
other = head[index];
while (cur->next != NULL) {
while (other->next != NULL) {
if (cur != other) {
if (int tmp =isMatch(cur, other)) {
Block*tmp1, *tmp2;
tmp1 = cur->next;
tmp2 = other->next;
pop(cur);
pop(other);
cur = tmp1;
other = tmp2;
this->saved += tmp;
break;
}
else {
other = other->next;
}
}
}
cur = cur->next;
}
}
void BlocksHash::push(int module[][4]) {
int index;
Block* node = new Block();
//일단 인덱스를 구해야지.
//1~457 일 수 있다.
int nums[10] = { 0 };
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
nums[module[i][j]] ++;
}
}
int exp= 1;
int cnt = 0;
for (int i = 0; i < 10; i++) {
if (nums[i] != 0 && cnt <3) {
index += nums[i] * exp;
exp *= 10;
node->height[cnt] = nums[i];
cnt++;
}
}
for (int i = 0; i < 4; i++) {
for(int j=0;j<4;j++){
node->arr[i][j] = module[i][j];
}
}
//해당 인덱스에 원소가 없어.
if (head[index] == NULL) {
head[index] = node;
tail[index] = node;
}
//있다.
else {
node->prev = tail[index];
tail[index]->next = node;
tail[index] = node;
}
}
void BlocksHash::pop(Block*a) {
//맨 앞은 아니다.
if (a->prev != NULL) {
//맨 뒤는 아니다.
if (a->next != NULL) {
a->prev->next = a->next;
a->next->prev = a->prev;
}
else {
a->prev->next = NULL;
tail[a->index] = a->prev;
}
}
//맨 앞에 있는놈
else {
head[a->index] = a->next;
a->next->prev = NULL;
}
delete a;
}
int dir_x[4] = { 0,1,0,-1 };
int dir_y[4] = { 1,0,-1,0 };
void BlocksHash::rotate90(int module[][4]) {
int arr[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
arr[j][3 - i] = module[i][j];
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
module[i][j] = arr[i][j];
}
}
}
int BlocksHash::isMatch(Block *a, Block*b) {
bool match = true;
//index가 같은건 이미 compareList함수에서 보장한다.
for (int k = 0; k < 4; k++) {
match = true;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (a->arr[i][j] != b->arr[i][j]) {
match = false;
break;
}
}
if (match == false) {
break;
}
if (match == true && i == 3) {
return a->arr[0][0] + b->arr[0][0];
}
}
rotate90(a->arr);
}
}
int makeBlock(int module[][4][4])
{
;
}
내가 못하는 문제는 무엇일까?
음 이유를 분석해 보자.
내 생각에는
1. 문제를 내가 구현 가능한 수준에서 설계를 못한다.
1-1. 그렇게 설계하면 구현을 못함 내가.
1-2. 생각은 맞는데 구현을 못하는건지 구현 계획 자체가 비효율적인건지....
-> 약간 이 둘을 타협하는 방법이 자주 답인거 같다.....
링크드리스트 순회하면서 노드 삭제하는건 좀 어렵다고 생각되서 그냥 flag를 주어서 체크한 놈이면 다시 확인 안하도록 했다.
음 결국 구현했는데 왜 틀리는거야~
에러 내가 찾긴 했는데 그래도...
#include<iostream>
using namespace std;
#define MAX 30000
#define NULL 0
struct Block{
//해당 높이가 몇개 있는지.
int block_height[10] = { 0 };
//해당 높이가 뭐있는지 3개.
int height[3] = { 0 };
int blockIndex;
int hashIndex;
bool checked = false;
Block * prev= NULL,*next=NULL;
};
class BlocksHash {
private:
//14 1 1
//2 4 10
//1411
Block * head[1500] = { NULL };
Block * tail[1500] = { NULL };
int Size[1500] = { 0 };
int saved = 0;
public:
//해당 모듈을 해쉬에 넣는다.
void push(int index, int module[][4][4]);
//해당 인덱스의 리스트에서 첫째로는 3개높이의 갯수가 일치하는지 확인하고
//일치하면 2개씩 비교(isMatch)한다.
void compareList(int hashIndex,int module[][4][4]);
//두 블록안의 각 블록들의 위치들이 갯수에 맞게 일치하는지 확인한다.
//위치에 따른 구현은 내가 못하겠어서 그냥 회전해서 전체를 비교하는 식으로 해야
//될거 같다.
//근데 모듈을 여기 넣어도 되는건가....
int isMatch(Block *a, Block*b,int module[][4][4]);
//해당 블록 해쉬맵에서 제거.
void pop(Block*a);
//모듈을 90도 회전한다.
void rotate90(int blockIndex,int module[][4][4]);
int getSaved();
};
int BlocksHash:: getSaved() {
return saved;
}
BlocksHash hashmap;
//이 부분 구현이 어렵다.. pop 했을때 연속성있게 두개를 비교하기가
void BlocksHash::compareList(int hashIndex, int module[][4][4]) {
Block* cur,*other;
if( head[hashIndex] != NULL ) {
cur = head[hashIndex];
other = head[hashIndex];
while (cur != NULL) {
if (cur->checked == false) {
while (other != NULL) {
if (cur != other && other->checked == false) {
if (int tmp = isMatch(cur, other, module)) {
cur->checked = true;
other->checked = true;
this->saved += tmp;
break;
}
}
other = other->next;
}//while
}
cur = cur->next;
}//while
}//if
}
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void sort(int arr[]) {
if (arr[0] > arr[1]) {
swap(&arr[0], &arr[1]);
}
if (arr[1] > arr[2]) {
swap(&arr[1], &arr[2]);
}
if (arr[0] > arr[1]) {
swap(&arr[0], &arr[1]);
}
}
void BlocksHash::push(int blockIndex, int module[][4][4]) {
Block* node = new Block();
//일단 인덱스를 구해야지.
//1~457 일 수 있다.
int nums[10] = { 0 };
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
nums[module[blockIndex][i][j]] ++;
}
}
int exp = 1;
int cnt = 0;
int index = 0;
int arr[3] = { 0 };
//인덱스가 오름차순으로 만들어지는게 아니다 655처럼.656
for (int i = 0; i < 10; i++) {
if (nums[i] != 0 && cnt <3) {
arr[cnt] = nums[i];
cnt++;
}
}
sort(arr);
for (int i = 0; i < 3; i++) {
index += arr[i] * exp;
exp *= 10;
}
node->blockIndex = blockIndex;
node->hashIndex = index;
Size[index]++;
//해당 인덱스에 원소가 없어.
if (head[index] == NULL) {
head[index] = node;
tail[index] = node;
}
//있다.
else {
node->prev = tail[index];
tail[index]->next = node;
tail[index] = node;
}
}
void BlocksHash::pop(Block*a) {
//맨 앞은 아니다.
if (a->prev != NULL) {
//맨 뒤는 아니다.
if (a->next != NULL) {
a->prev->next = a->next;
a->next->prev = a->prev;
}
else {
a->prev->next = NULL;
tail[a->hashIndex] = a->prev;
}
}
//맨 앞에 있는놈
else {
head[a->hashIndex] = a->next;
a->next->prev = NULL;
}
delete a;
}
int dir_x[4] = { 0,1,0,-1 };
int dir_y[4] = { 1,0,-1,0 };
void BlocksHash::rotate90(int index,int module[][4][4]) {
int arr[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
arr[j][3 - i] = module[index][i][j];
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
module[index][i][j] = arr[i][j];
}
}
}
void printArr(int index, int module[][4][4]) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cout << module[index][i][j]<<" ";
}
cout << "\n";
}
cout << "\n";
}
//왜 a,b의 블록인덱스가 같은게 이 함수로 들어오지
int BlocksHash::isMatch(Block *a, Block*b,int module[][4][4]) {
bool match = true;
int aIndex = a->blockIndex;
int bIndex = b->blockIndex;
//index가 같은건 이미 compareList함수에서 보장한다.
for (int k = 0; k < 4; k++) {
match = true;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (module[aIndex][i][j] != module[bIndex][i][j]) {
match = false;
break;
}
}
if (match == false) {
break;
}
if (match == true && i == 3) {
printArr(aIndex, module);
printArr(bIndex, module);
return module[aIndex][0][0] + module[bIndex][0][0];
}
}
// printArr(aIndex, module);
rotate90(aIndex,module);
// printArr(aIndex, module);
}
return 0;
}
int makeBlock(int module[][4][4])
{
for (int i = 0; i < MAX; i++) {
hashmap.push(i, module);
}
for (int i = 0; i < 1500; i++) {
hashmap.compareList(i, module);
}
return hashmap.getSaved();
}
다른 분이 블로그에 올린 해설을 보고 있다.
일단 내가 잘 못한게 같은 모양 블록 중에 높이가 긴거 끼리 먼저 매칭 시켜야 되는데 3개 면 높이 긴 2개를 해줘야 되잔아. 나는 정렬없이 그냥 아무거나 더했다.
'알고리즘 문제 풀기' 카테고리의 다른 글
| 백준 - 11004번 K번째 수 (0) | 2020.01.16 |
|---|---|
| 프로그래머스 - 완전탐색 : 모의고사 ,소수 찾기,숫자 야구 (0) | 2020.01.16 |
| 프로그래머스 - 정렬 : K번째 수, 가장 큰 수, H index (0) | 2020.01.13 |
| swexpertacademy - 1768. 숫자야구게임 (0) | 2020.01.08 |
| swexpertacademy - 9088. 다이아몬드,8998. 세운이는 내일 할거야, 8993. 하지 추측 (0) | 2020.01.06 |