문제 URL : https://programmers.co.kr/learn/courses/30/lessons/84021
코딩테스트 연습 - 3주차
[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0
programmers.co.kr
문제 접근법 :
오른쪽도형을 왼쪽도형에 딱맞는 사이즈로 얼마나 넣을수 있는지 물어보는 문제입니다.
굳이 최대값을 찾으려고 애쓰지마세여
노가다문제를 오랜만에 푸니까 몇시간을 고생해서 풀었고
필요없는 코드를 줄이고 줄였습니다. 블록을 채워야하니 game_board엔 빈블록이 들어아갸할 블록을 찾고
table엔 가지고있는 블록이 어떤것인지 찾아야합니다. 둘다 똑같이 bfs, dfs 둘중하나 선택해서 찾는건 쉽습니다.
문제는 그것을찾아 2차원 배열로 만들어야하는데 처음엔 해당블록을 찾을때 가로세로중 가장 큰길이를 통해
2차원 정사각배열로 만들어 넣었는데 그렇게 하면 회전을해도 같은지 판단하는게 더 까다로워 집니다.
그렇게 한다고 가정하면 중력을 통해 y,x좌표 둘다 좌상단 혹은 우하단쪽으로 해당블럭을 밀면서 회전해야 같은지 판단할수있습니다. 그것때문에 왜틀렸는지 꽤 고생했네요 ㅠ.ㅠ
하지만 이방법까지 할려면 은근 코드가 길고 귀찮아진다 차라리
정사각 배열이아닌 직사각형배열을 만들어 도형이 최대한 정확하고 빈공간이 낭비하지 않도록 만들면 중력은 필요없다.
그럼 직사각배열은 어떻게 만들까? 아래그림과 같이
위와같은 도형이있을때 왼쪽 도형을 오른쪽 배열처럼 옮기고싶다고 하면 우선 행을 y 열을 x좌표라할때
왼쪽 보라색 도형에서 y좌표중 가장 큰것은 3이고 가장 작은것은 2이다 그리고 x좌표중 가장 큰것은4이며 가장 작은 것은 2이다
즉 height =(3-2)+1 =2이며 , width = (4-2)+1 =3 이라는것을 알수있고
길이=가장큰것-가장작은+1 이라는것을 알수있다
그렇다면 저좌표들
(2,3) ->(0,1) 로
(2,4)->(0,2) 로
(3,2) ->(1,0)로
(3,3) ->(1,1)로 어떻게 옮길까?
잘보면 아까 가장큰 y와 x의 가장큰좌표는 (3,4)가 가장작은 좌표는 (2,2)라는것을 알수있다
그렇다면 해당 좌표들을 가장 작은 좌표로 빼보면 어떨까?
(2,3) -(2,2) ->(0,1)
...
(3,3) -(2,2) ->(1,1) 다 잘나온다는것을 알수있습니다.
또한 이도형은 4개라는것을 알기때문에 map으로 key값을 도형의 개수로 직사각형배열을 집어넣어
c++ 백터로 같은 도형인지 쉽게 구분해줄수있습니다.
마지막으로 회전은
직사각형 배열이 n * m사이즈일때 회전을하게되면 m*n 사이즈가 된다는것을 유념하여 값을 집어넣어 구현하고
해당 도형들을 찾아 그사이즈를 answer값에 넣어주고 찾은것을 지워주면서 답을 찾으면되겠습니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vector<int>>
#define vpii vector<pair<int,int>>
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int n;
bool isrange(int y, int x) { return 0 <= y && y < n && 0 <= x && x < n; }
void dfs(int y, int x, int color, vvi& board, vvi& visit, vpii& v) {
if (!isrange(y, x))return;
if (visit[y][x] || board[y][x] != color)return;
visit[y][x] = 1;
//도형들을 찾아 v에 집어넣기
v.push_back({ y,x });
for (int i = 0; i < 4; i++)dfs(y + dy[i], x + dx[i], color, board, visit, v);
}
void rotate(vvi& board) {
//board의 행사이즈과 열사이즈가 바뀜
vvi temp(board[0].size(), vi(board.size()));
for (int i = 0, j2 = board.size() - 1; i < board.size(); i++, j2--) {
for (int j = 0, i2 = 0; j < board[i].size(); j++, i2++) {
temp[i2][j2] = board[i][j];
}
}
board = temp;
}
void makeboard(vpii& v, map<int, vector<vvi>>& block) {
int fy, fx, my, mx;
tie(fy, fx, my, mx) = { v[0].first,v[0].second,v[0].first,v[0].second };
for (int i = 1; i < v.size(); i++) {
fy = max(fy, v[i].first);
fx = max(fx, v[i].second);
my = min(my, v[i].first);
mx = min(mx, v[i].second);
}
int height = fy - my + 1;
int width = fx - mx + 1;
vvi board(height, vi(width));
for (int i = 0; i < v.size(); i++) {
board[v[i].first - my][v[i].second - mx] = 1;
}
block[v.size()].push_back(board);
}
bool issame(vvi& board, vvi& board2) {
for (int i = 0; i < 4; i++) {
if (board == board2)return true;
rotate(board2);
}
return false;
}
int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
int answer = 0;
n = table.size();
vvi visit(n, vi(n));
vvi visit2 = visit;
map<int, vector<vvi>> block, block2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (game_board[i][j] == 0 && visit[i][j] == 0) {
vpii v;
dfs(i, j, 0, game_board, visit, v);
makeboard(v, block);
}
if (table[i][j] && visit2[i][j] == 0) {
vpii v;
dfs(i, j, 1, table, visit2, v);
makeboard(v, block2);
}
}
}
for (auto it : block) {
int size = it.first;
for (vvi v : it.second) {
for (int i = 0; i < block2[size].size(); i++) {
if (issame(v, block2[size][i])) {
block2[size].erase(block2[size].begin() + i);
answer += size;
break;
}
}
}
}
return answer;
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 [3차] 압축(2018 KAKAO BLIND RECRUITMENT) (0) | 2021.08.19 |
|---|---|
| 프로그래머스 [3차]파일명 정렬(2018 KAKAO BLIND RECRUITMENT) (0) | 2021.08.19 |
| 프로그래머스 수식 최대화 (2020 카카오 인턴십) (0) | 2021.08.02 |
| 프로그래머스 문자열 압축(2020 KAKAO BLIND RECRUITMENT) (0) | 2021.08.01 |
| 프로그래머스 메뉴 리뉴얼 (2021 KAKAO BLIND RECRUITMENT) (0) | 2021.08.01 |
