Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- javascript
- level 3
- group by
- dfs
- 깊이 우선 탐색
- 소프티어
- softeer
- 너비 우선 탐색
- bfs
- 오블완
- 파이썬
- Lv. 1
- Lv. 0
- 티스토리챌린지
- Dynamic Programming
- 동적계획법
- Python
- 프로그래머스
- Lv. 2
- Java
- Lv. 3
- select
- DP
- SQL 고득점 KIT
- 자바스크립트
- SQL
- C언어
- programmers
- join
- LEVEL 2
Archives
- Today
- Total
몸과 마음이 건전한 SW 개발자
프로그래머스 [Lv. 3] 퍼즐 조각 채우기 {언어 : JavaScript} 본문
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/84021
정답 코드
function solution(game_board, table) {
let answer = 0;
// 체크 맵
let checkMap = new Map();
const setMap = (key) => {
if (checkMap.has(key)) {
checkMap.set(key, checkMap.get(key)+1);
} else {
checkMap.set(key, 1);
}
}
// 길이
const n = game_board.length;
// 방향 범위
const dr = [-1, 1, 0, 0, -1, -1, 1, 1];
const dc = [0, 0, -1, 1, 1, -1, 1, -1];
const isValid = (nr, nc) => {
return 0 <= nr && nr < n && 0 <= nc && nc < n;
};
const eightDirections = (arr, visited, lenA) => {
const newArr = [];
for (const [r, c] of arr) {
let straight = 0;
let left = 0;
let right = 0;
// 0 ~ 3는 같은 방향으로 취급하고
for (let d = 0; d < 4; d++) {
const nr = r + dr[d];
const nc = c + dc[d];
if (isValid(nr, nc) && visited[nr][nc]) {
straight++;
}
}
// 4 ~ 7은 꺾이는 지점으로 한다.
for (let d = 4; d < 8; d++) {
const nr = r + dr[d];
const nc = c + dc[d];
if (isValid(nr, nc) && visited[nr][nc]) {
// 오른쪽
// 같은 행에 정사각형이 있고
if (visited[r][nc]) {
// 오른쪽에 있으며
if (c < nc) {
// 행이 작은 경우 왼쪽
if (r > nr) {
left++;
} else {
right++;
}
} else {
// 왼쪽에 있으며
// 행이 작은 경우 오른쪽
if (r > nr) {
right++;
} else {
left++;
}
}
}
// 왼쪽
// 같은 열에 정사각형이 있고
if (visited[nr][c]) {
// 위에 있고
if (r > nr) {
// 열이 크면 오른쪽
if (c < nc) {
right++;
} else {
left++;
}
} else {
// 아래에 있고
// 열이 크면 왼쪽
if (c < nc) {
left++;
} else {
right++;
}
}
}
}
}
newArr.push([straight, left, right]);
}
newArr.sort(([a, b, c], [d, e, f]) => a - d || b - e || c - f);
return newArr;
}
// bfs
const bfs = (sr, sc, isBlock) => {
const deque = [[sr, sc]];
const rows = new Map();
const cols = new Map();
rows.set(sr, 1);
cols.set(sc, 1);
// 8방향 확인을 위한 visited
const visited = Array.from({length: n}, () => Array.from({length: n}, () => false));
visited[sr][sc] = true;
const keys = [[sr, sc]];
if (isBlock) {
table[sr][sc] = 0; // 빈칸 채워서 더 못찾게 하기
} else {
game_board[sr][sc] = 1; // 빈칸 채워서 더 못찾게 하기
}
let count = 1;
while (deque.length > 0) {
const [r, c] = deque.shift();
for (let d = 0; d < 4; d++) {
const nr = r + dr[d];
const nc = c + dc[d];
let isTrue = false;
if (isValid(nr, nc)) {
if (isBlock && table[nr][nc] === 1) {
table[nr][nc] = 0;
isTrue = true;
} else if (!isBlock && game_board[nr][nc] === 0) {
game_board[nr][nc] = 1;
isTrue = true;
}
}
if (isTrue) {
deque.push([nr, nc]);
keys.push([nr, nc]);
visited[nr][nc] = true;
count++;
if (rows.has(nr)) {
rows.set(nr, rows.get(nr)+1);
} else {
rows.set(nr, 1);
}
if (cols.has(nc)) {
cols.set(nc, cols.get(nc)+1);
} else {
cols.set(nc, 1);
}
}
}
}
const cnt = keys.length;
keys.sort(([a, b], [c, d]) => a - c || d - b);
const newKeys = eightDirections(keys, visited, cnt);
// 행 키
const rowsEntries = [...(rows.entries())].map((e) => e);
rowsEntries.sort(([a, b], [c, e]) => a - c);
const rowsKeys = rowsEntries.map((e) => e[1]);
// 열 키
const colsEntries = [...(cols.entries())].map((e) => e);
colsEntries.sort(([a, b], [c, e]) => a - c);
const colsKeys = colsEntries.map((e) => e[1]);
const cr = [...colsKeys].reverse();
const rr = [...rowsKeys].reverse();
const firstKey = `${count}-${rowsKeys}-${colsKeys}-${newKeys}`;
const secondKey = `${count}-${cr}-${rowsKeys}-${newKeys}`;
const thirdKey = `${count}-${rr}-${cr}-${newKeys}`;
const fourthKey = `${count}-${colsKeys}-${rr}-${newKeys}`;
// set에 넣어야 함
const set = new Set([firstKey, secondKey, thirdKey, fourthKey]);
// 블럭이면 확인하고 있으면 둘 다 -1
if (isBlock) {
// key 둘 중에 하나는 있을 것이다.
if (checkMap.has(firstKey)) {
if (checkMap.get(firstKey) > 0) {
// 둘 중 하나만 탐색해도 있겠지만 둘 다 지워야 한다.
for (const sv of set) {
checkMap.set(sv, checkMap.get(sv)-1);
}
// answer에 count만큼 저장
answer += count;
}
}
} else {
// 빈칸을 체크맵에 저장
for (const sv of set) {
setMap(sv);
};
}
}
// 빈칸 먼저 저장하고
for (let sr = 0; sr < n; sr++) {
for (let sc = 0; sc < n; sc++) {
if (game_board[sr][sc] === 0) {
bfs(sr, sc, false);
}
}
}
// 블록으로 빈칸에 넣을 수 있는지 확인
for (let sr = 0; sr < n; sr++) {
for (let sc = 0; sc < n; sc++) {
if (table[sr][sc] === 1) {
bfs(sr, sc, true);
}
}
}
return answer;
}
풀이 방법
- 방향 탐색은 다들 할 줄 아니 생략하고 map을 왜 사용했는지 적어보려고 한다.
- rows와 cols는 무엇인가
- 빈칸이나 블록을 찾으면 [[1, 2], [3, 4], [5, 6], [nr, nc]] 이런식으로 저장이 된다.
- 여기에 해당하는 행 index는 rows에 키 값으로 들어가고 이후에 같은 행 index가 나오면 +1을 해준다.
- 열도 마찬가지로 해준다.
- 그 후 [key, value] 형태를 요소로 가지는 배열을 만든다.
- const rowsEntries = [...(rows.entries())].map((e) => e);
- 그리고 정렬 하는데 key값을 기준으로 오름차순 정렬한다.
- rowsEntries.sort(([a, b], [c, e]) => a - c);
- 그 후 value로 된 배열을 새로 만든다.
- const rowsKeys = rowsEntries.map((e) => e[1]);
- 열도 마찬가지
- 예를 들어
- game_board = [[0, 0, 0], [0, 1, 1], [1, 1, 1]]일 때
- rows = [3, 1]
- cols = [2, 1, 1]
배열 | [[0, 0, 0], [0, 1, 1], [1, 1, 1]] |
[[1, 1, 0], [0, 0, 0], [1, 1, 1]] |
[[1, 0, 0], [1, 1, 0], [1, 1, 0]] |
[[0, 1, 1], [0, 1, 1], [0, 0, 1]] |
[[0, 0, 0], [0, 1, 1], [1, 1, 1]] |
rows: [3, 1] cols: [2, 1, 1] |
rows: rows.reverse() cols: cols.reverse() |
rows: cols cols: rows.reverse() |
rows: cols.reverse() cols: rows |
[[1, 1, 0], [0, 0, 0], [1, 1, 1]] |
rows: rows.reverse() cols: cols.reverse() |
rows: [1, 3] cols: [1, 1, 2] |
rows: cols.reverse() cols: rows |
rows: cols cols: rows.reverse() |
[[1, 0, 0], [1, 1, 0], [1, 1, 0]] |
rows: cols cols: rows.reverse() |
rows: cols.reverse() cols: rows |
rows: [2, 1, 1] cols: [1, 3] |
rows: rows.reverse() cols: cols.reverse() |
[[0, 1, 1], [0, 1, 1], [0, 0, 1]] |
rows: cols.reverse() cols: rows |
rows: cols cols: rows.reverse() |
rows: rows.reverse() cols: cols.reverse() |
rows: [1, 1, 2] cols: [3, 1] |
- 하지만 이 방법에도 아래 "이전 코드와 문제점"에서 문제가 드러난다.
- 그래서 고안한 방법이 8방향 탐색과 꺾이는 지점 파악이다.
- 블록의 위치를 저장한 배열이 [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1]]일 때
- [0, 0]을 기준으로
- [0, 1]과 [1, 1]은 상하좌우에 속하므로 straight = 2
- [1, 1]은 대각선이고 [0, 1]을 거쳐서 갈 수 있고 직진 우회전이므로 right = 1
- 하지만 [1, 1]을 거쳐서 갈 수도 있으므로 직진 좌회전 left = 1
- [2, 1, 1]로 된 배열을 가진다.
- [0, 0]을 기준으로
- 이를 키로 만들어서 위의 키와 합치면 하나밖에 없는 키가 만들어진다. 아마도...
- 이런식으로 직좌 직우 움직여서 확인하게 된다.
이전 코드와 문제점
- 8방향 탐색과 꺾이는 지점을 포착하고 좌우 어디로 꺾였는지 확인
- 테스트 케이스 10번만 틀림
더보기
function solution(game_board, table) {
const n = table.length;
// 키가 없으면 키는 eightDirections로 만든 newArr로 만든다.
// 계산이 편하게 맨 앞은 count
// 그리고 blank는 [1, 0] block은 [0, 1] 로 선언
// 키가 있으면 각 키에 해당하는 값의 blank와 block의 index에 +1;
const checkMap = new Map();
// bfs
const dr = [-1, 1, 0, 0, -1, -1, 1, 1];
const dc = [0, 0, -1, 1, 1, -1, 1, -1];
const isValid = (nr, nc) => {
return 0 <= nr && nr < n && 0 <= nc && nc < n;
};
const eightDirections = (arr, visited, lenA) => {
const newArr = [];
for (const [r, c] of arr) {
let straight = 0;
let left = 0;
let right = 0;
// 0 ~ 3는 같은 방향으로 취급하고
for (let d = 0; d < 4; d++) {
const nr = r + dr[d];
const nc = c + dc[d];
if (isValid(nr, nc) && visited[nr][nc]) {
straight++;
}
}
// 4 ~ 7은 꺾이는 지점으로 한다.
for (let d = 4; d < 8; d++) {
const nr = r + dr[d];
const nc = c + dc[d];
if (isValid(nr, nc) && visited[nr][nc]) {
// 오른쪽
// 같은 행에 정사각형이 있고
if (visited[r][nc]) {
// 오른쪽에 있으며
if (c < nc) {
// 행이 작은 경우 왼쪽
if (r > nr) {
left++;
} else {
right++;
}
} else {
// 왼쪽에 있으며
// 행이 작은 경우 오른쪽
if (r > nr) {
right++;
} else {
left++;
}
}
}
// 왼쪽
// 같은 열에 정사각형이 있고
if (visited[nr][c]) {
// 위에 있고
if (r > nr) {
// 열이 크면 오른쪽
if (c < nc) {
right++;
} else {
left++;
}
} else {
// 아래에 있고
// 열이 크면 왼쪽
if (c < nc) {
left++;
} else {
right++;
}
}
}
}
}
newArr.push([straight, left, right]);
}
newArr.sort(([a, b, c], [d, e, f]) => a - d || b - e || c - f);
return `${lenA}-${newArr}`;
}
const bfs = (sr, sc, isBlock) => {
const deque = [[sr, sc]];
const keys = [[sr, sc]];
// 8방향 확인을 위한 visited
const visited = Array.from({length: n}, () => Array.from({length: n}, () => false));
visited[sr][sc] = true;
if (isBlock) {
table[sr][sc] = 0; // 빈칸 채워서 더 못찾게 하기
} else {
game_board[sr][sc] = 1; // 빈칸 채워서 더 못찾게 하기
}
while (deque.length > 0) {
const [r, c] = deque.shift();
for (let d = 0; d < 4; d++) {
const nr = r + dr[d];
const nc = c + dc[d];
if (isValid(nr, nc)) {
if (isBlock && table[nr][nc] === 1) {
table[nr][nc] = 0;
deque.push([nr, nc]);
keys.push([nr, nc]);
visited[nr][nc] = true;
} else if (!isBlock && game_board[nr][nc] === 0) {
game_board[nr][nc] = 1;
deque.push([nr, nc]);
keys.push([nr, nc]);
visited[nr][nc] = true;
}
}
}
}
// 저장할 때 정렬해서 넣는다.
// [[3, 2], [1, 3]] 이면
// [[1, 3], [3, 2]]로 정렬한다.
const cnt = keys.length;
keys.sort(([a, b], [c, d]) => a - c || d - b);
const newKeys = eightDirections(keys, visited, cnt);
if (checkMap.has(newKeys)) {
// [0, 0] 앞이 cnt blanks 뒤가 cnt blocks
const checkValue = checkMap.get(newKeys);
if (isBlock) {
checkMap.set(newKeys, [checkValue[0], checkValue[1]+1]);
} else {
checkMap.set(newKeys, [checkValue[0]+1, checkValue[1]]);
}
} else {
if (isBlock) {
checkMap.set(newKeys, [0, 1]);
} else {
checkMap.set(newKeys, [1, 0]);
}
}
}
for (let sr = 0; sr < n; sr++) {
for (let sc = 0; sc < n; sc++) {
if (game_board[sr][sc] === 0) {
bfs(sr, sc, false);
}
if (table[sr][sc] === 1) {
bfs(sr, sc, true);
}
}
}
let answer = 0;
// 계산
let checkMapKeys = checkMap.keys();
for (const cmk of checkMapKeys) {
const count = cmk[0];
const [cntBlanks, cntBlocks] = checkMap.get(cmk);
answer += Math.min(cntBlanks, cntBlocks) * count;
}
return answer;
}
- 행에서 가로로 개수 파악, 열에서 세로로 개수 파악
- 예를 들어 [[0, 1, 1], [0, 0, 1], [0, 1, 1]] 이라는 배열은
- rows : 1, 2, 1
- cols : 3, 1
- 테스트 케이스 10번은 맞으나 3, 7, 13, 22 틀림
- 예상 반례
- game_board = [[0, 1, 1, 1], [0, 0, 1, 1], [1, 0, 0, 1], [1, 1, 0, 1]]
- table = [[0, 0, 1, 0], [0, 1, 1, 0], [1, 1, 0, 0], [1, 0, 0, 0]]
- output = 0
더보기
function solution(game_board, table) {
let answer = 0;
// 체크 맵
let checkMap = new Map();
const setMap = (key) => {
if (checkMap.has(key)) {
checkMap.set(key, checkMap.get(key)+1);
} else {
checkMap.set(key, 1);
}
}
// 길이
const n = game_board.length;
// 방향 범위
const dr = [-1, 1, 0, 0];
const dc = [0, 0, -1, 1];
const isValid = (nr, nc) => {
return 0 <= nr && nr < n && 0 <= nc && nc < n;
};
// bfs
const bfs = (sr, sc, isBlock) => {
const deque = [[sr, sc]];
const rows = new Map();
const cols = new Map();
rows.set(sr, 1);
cols.set(sc, 1);
if (isBlock) {
table[sr][sc] = 0; // 빈칸 채워서 더 못찾게 하기
} else {
game_board[sr][sc] = 1; // 빈칸 채워서 더 못찾게 하기
}
let count = 1;
while (deque.length > 0) {
const [r, c] = deque.shift();
for (let d = 0; d < 4; d++) {
const nr = r + dr[d];
const nc = c + dc[d];
let isTrue = false;
if (isValid(nr, nc)) {
if (isBlock && table[nr][nc] === 1) {
table[nr][nc] = 0;
deque.push([nr, nc]);
isTrue = true;
} else if (!isBlock && game_board[nr][nc] === 0) {
game_board[nr][nc] = 1;
deque.push([nr, nc]);
isTrue = true;
}
}
if (isTrue) {
count++;
if (rows.has(nr)) {
rows.set(nr, rows.get(nr)+1);
} else {
rows.set(nr, 1);
}
if (cols.has(nc)) {
cols.set(nc, cols.get(nc)+1);
} else {
cols.set(nc, 1);
}
}
}
}
// 행 키
const rowsEntries = [...(rows.entries())].map((e) => e);
rowsEntries.sort(([a, b], [c, e]) => a - c);
const rowsKeys = rowsEntries.map((e) => e[1]);
// 열 키
const colsEntries = [...(cols.entries())].map((e) => e);
colsEntries.sort(([a, b], [c, e]) => a - c);
const colsKeys = colsEntries.map((e) => e[1]);
const cr = [...colsKeys].reverse();
const rr = [...rowsKeys].reverse();
const firstKey = `${count}-${rowsKeys}-${colsKeys}`;
const secondKey = `${count}-${cr}-${rowsKeys}`;
const thirdKey = `${count}-${rr}-${cr}`;
const fourthKey = `${count}-${colsKeys}-${rr}`;
// set에 넣어야 함
const set = new Set([firstKey, secondKey, thirdKey, fourthKey]);
// 블럭이면 확인하고 있으면 둘 다 -1
if (isBlock) {
// key 둘 중에 하나는 있을 것이다.
if (checkMap.has(firstKey)) {
if (checkMap.get(firstKey) > 0) {
// 둘 중 하나만 탐색해도 있겠지만 둘 다 지워야 한다.
for (const sv of set) {
checkMap.set(sv, checkMap.get(sv)-1);
}
// answer에 count만큼 저장
answer += count;
}
}
} else {
// 빈칸을 체크맵에 저장
for (const sv of set) {
setMap(sv);
};
}
}
// 빈칸 먼저 저장하고
for (let sr = 0; sr < n; sr++) {
for (let sc = 0; sc < n; sc++) {
if (game_board[sr][sc] === 0) {
bfs(sr, sc, false);
}
}
}
// 블록으로 빈칸에 넣을 수 있는지 확인
for (let sr = 0; sr < n; sr++) {
for (let sc = 0; sc < n; sc++) {
if (table[sr][sc] === 1) {
bfs(sr, sc, true);
}
}
}
return answer;
}
느낀점
- 무슨 홍대병에 걸린 것 마냥 내 방식대로 끝까지 고집해서 풀었다.
- 남들이 푸는 도형 90 180 270도 돌리는 방향으로 풀었으면 3일이라는 시간보다 빠르게 풀었을 것 같다.
- "simple is best" 단순하게 생각해서 도형 돌리는 방법으로 나중에 다시 풀어보면 좋을 것 같다.
'알고리즘 > 풀었지만 다시 보기' 카테고리의 다른 글
백준 SILVER 1 [11052번] 카드 구매하기 {언어 : Python} (0) | 2024.10.10 |
---|---|
프로그래머스 [Lv. 3] [PCCP 기출문제] 4번 / 수레 움직이기 {언어 : Python} (1) | 2024.10.09 |
프로그래머스 [Lv. 2] [PCCP 기출문제] 3번 / 충돌위험 찾기 {언어 : JavaScript} (0) | 2024.09.30 |
프로그래머스 [Lv. 3] n + 1 카드게임 {언어 : JavaScript} (3) | 2024.09.13 |
프로그래머스 [Lv. 3] [PCCP 기출문제] 4번 / 수식 복원하기 {언어 : Python} (1) | 2024.09.12 |