2D Array ๋ค๋ฃจ๊ธฐ
์ด ๊ธ์ ๊ณจ๋ ๋๋น ์ฝ๋ฉ ํ ์คํธ ํฉ๊ฒฉ์ ๋๊ธฐ ํ์ด์ฌ ํธ์ 5์ฅ ์จ๋จธ๋ฆฌ์ ๋๋ค.
- 2์ฐจ์ ๋ฐฐ์ด์ 1์ฐจ์ ๋ฐฐ์ด์ ํ์ฅํ ๊ฒ์ด๋ค. 1์ฐจ์ ๋ฐฐ์ด์ ํ์ฅํ๋ค๋ ๊ฒ์ 2์ฐจ์ ๋ฐฐ์ด๋ 1์ฐจ์๊ณต๊ฐ์ ์ ์ฅํ๊ณ ๋ฉ๋ชจ๋ฆฌ์ ์ฐ์์ ์ผ๋ก ํ ๋นํ๋ค๊ณ ๋ณผ ์ ์๋ค.
- ์ฆ ์ฐจ์๊ณผ๋ ๋ฌด๊ดํ๊ฒ ์ฐ์์ ์ผ๋ก ํ ๋น๋๋ค.
- ๋ฐฐ์ด์ ๋ค๋ฃฐ ๋ ํ ๋นํ ์ ์๋ ๋ฉ๋ชจ๋ฆฌ์ ํฌ๊ธฐ๋ฅผ ํ์ธํ๋๊ฒ ์ข์๋ฐ, 2์ฐจ์ ๋ฐฐ์ด์ ๊ฒฝ์ฐ 3000*3000 ํฌ๊ธฐ๋ฅผ ์ต๋๋ก ์๊ฐํ๋ค. (์ด์์ฒด์ ์ ๋ฐ๋ผ ๋ค๋ฅด๊ธฐ๋ํ๋ค.) (1์ฐจ์์ ์ต๋ 1000๋ง๊ฐ)
- ์ฐจ์์ ์๊ด์์ด ๋ฐฐ์ด์์ ๋ฐ์ดํฐ ์ฝ์ ์ด ๋ฐฐ์ด์ ๋ง์ง๋ง์ด ์๋ ์ค๊ฐ์ ์ฝ์ ํด์ผ ํ๋ค๋ฉด, ์ฝ์ ํ ์ธ๋ฑ์ค ๋ถํฐ ์ค๋ฅธ์ชฝ์ผ๋ก ์ธ๋ฑ์ค๋ค์ ํ์นธ์ฉ ๋ค๋ก ๋ฐ๋ ค์ค์ผ ํ๋ฏ๋ก ์๊ฐ๋ณต์ก๋์์ ์๊ฐ์ด๊ณผ๋ฅผ ๊ณ ๋ คํ๋๊ฒ ์ข๋ค.
2D array ๋ฌธ์ ๋ค๋ค๋ณด๊ธฐ
1. ํ๋ ฌ์ ๊ณฑ์
์ถ์ฒ : https://school.programmers.co.kr/learn/courses/30/lessons/12949
๋ฌธ์ ์ค๋ช
2์ฐจ์ ํ๋ ฌ arr1๊ณผ arr2๋ฅผ ์ ๋ ฅ๋ฐ์, arr1์ arr2๋ฅผ ๊ณฑํ ๊ฒฐ๊ณผ๋ฅผ ๋ฐํํ๋ ํจ์, solution์ ์์ฑํด์ฃผ์ธ์.
์ ํ ์กฐ๊ฑด
- ํ๋ ฌ arr1, arr2์ ํ๊ณผ ์ด์ ๊ธธ์ด๋ 2 ์ด์ 100 ์ดํ์ ๋๋ค.
- ํ๋ ฌ arr1, arr2์ ์์๋ -10 ์ด์ 20 ์ดํ์ธ ์์ฐ์์ ๋๋ค.
- ๊ณฑํ ์ ์๋ ๋ฐฐ์ด๋ง ์ฃผ์ด์ง๋๋ค.
์ ์ถ๋ ฅ ์
arr1 | arr2 | return |
---|---|---|
[[1, 4], [3, 2], [4, 1]] | [[3, 3], [3, 3]] | [[15, 15], [15, 15], [15, 15]] |
[[2, 3, 2], [4, 2, 4], [3, 1, 4]] | [[5, 4, 3], [2, 4, 1], [3, 1, 1]] | [[22, 22, 11], [36, 28,18], [29, 20, 14]] |
๋ฌธ์ ํ์ด
- ์ด ๋ฌธ์ ์ ํต์ฌ์ ํ๋ ฌ์ ๊ณฑ์ ๊ณต์์ ์์์ผ ํ๋ค.
- ๋ํ๋ ฌ์ ๊ณฑํ๋ ค๋ฉด ์ด๋ฐ ๊ท์น์ ๋ฐ๋ผ์ผ ํ๋ค.
- ํ๋ ฌ A์ ํ๊ณผ ํ๋ ฌ B์ ์ด์ ๊ธธ์ด๋ ๊ฐ์์ผ ํฉ๋๋ค.
- ๊ฒฐ๊ณผ ํ๋ ฌ์ ํฌ๊ธฐ๋ ํ๋ ฌ A์ ํ์ ์์ ํ๋ ฌ B์ ์ด์ ์๊ฐ ๋ฉ๋๋ค.
๋ฐฉ๋ฒ1. ๋ด๊ฐ ํผ ๋ฐฉ๋ฒ :
- ํ๋์ row๋ฅผ ๊ฐ์ก๋ค๋ฉด, ๋ด๋ถ for๋ฌธ์ ์ด์ฉํด ๋ค๋ฅธ 2์ฐจ์ ๋ฐฐ์ด์ column์ ์์ ๊ฐ์ ธ์ ์๋ก ๊ณ์ฐํ๋ ๋ฐฉ๋ฒ์ด๋ค.
function solution(arr1, arr2) {
// arr1์ row, arr2์ col ๊ธธ์ด๋ก answer ๋ฐฐ์ด ๋ง๋ค๊ธฐ
let answer = Array.from({ length: arr1.length }, () =>
Array(arr2[0].length).fill(0)
);
// arr1์ row, arr2์ col ๊ธธ์ด๋งํผ ๋ฐ๋ณต๋ฌธ ๋๋ฆฌ๊ธฐ
for (let row = 0; row < arr1.length; row++) {
for (let col = 0; col < arr2[0].length; col++) {
let rowArr = arr1[row];
let colArr = getCols(arr2, col); //col ์ด ์ผ์นํ๋ arr2์ ์ด์ ๊ฐ์ ธ์ด.
answer[row][col] = calculate(rowArr, colArr);
}
}
return answer;
}
function calculate(row, col) {
let sum = 0;
for (let i = 0; i < row.length; i++) {
sum += row[i] * col[i];
}
return sum;
}
function getCols(arr, col) {
let result = [];
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr[0].length; j++) {
if (j === col) {
result.push(arr[i][j]);
}
}
}
return result;
}
์๊ฐ๋ณต์ก๋ ๋ถ์ :
answer
๋ฐฐ์ด ์์ฑ:
answer
๋ฐฐ์ด์n x m
ํฌ๊ธฐ์ 2์ฐจ์ ๋ฐฐ์ด์ ์์ฑํ๋ฏ๋ก ์๊ฐ ๋ณต์ก๋๋ O(nm) ์ด๋ค.
- ์ด์ค ๋ฐ๋ณต๋ฌธ:
for (let row = 0; row < arr1.length; row++)
์for (let col = 0; col < arr2[0].length; col++)
์ด์ค ๋ฐ๋ณต๋ฌธ์ ์ฌ์ฉํ์ฌ ๊ฐ ์์๋ฅผ ๊ณ์ฐ.arr1
์ ํ์ ์๋ฅผn
์ด๋ผ๊ณ ํ๊ณ ,arr2
์ ์ด์ ์๋ฅผm
์ด๋ผ๊ณ ํ ๋, ์ด์ค ๋ฐ๋ณต๋ฌธ์ ์๊ฐ ๋ณต์ก๋๋ O(nm).
getCols
ํจ์:getCols
ํจ์๋arr2
์์ ํน์ column์ ๊ฐ์ ๊ฐ์ ธ์ค๊ธฐ ์ํด ์ฌ์ฉ.arr2
์ ํ์ ์๋ฅผn
์ด๋ผ๊ณ ํ๊ณ ,arr2
์ ์ด์ ์๋ฅผm
์ด๋ผ๊ณ ํ ๋,getCols
ํจ์์ ์๊ฐ ๋ณต์ก๋๋ O(nm).calculate
ํจ์:calculate
ํจ์๋ row, col ์ด ๋ง๋ฌ์ ๋ ๊ณ์ฐ์ ํ๋ค. O(n) ์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
์ด ์๊ฐ ๋ณต์ก๋๋ O(nmk)
๋ฐฉ๋ฒ2.
row1 ๊ณผ ๊ณ์ฐ๋ col1์ ๊ฐ์ ธ์ค๋๊ฒ ์๋, for๋ฌธ ๋ด์์ ๋ฐ๋ก O(n)๊ณ์ฐ. ์์ ๋ฌธ์ ํด๊ฒฐ ์ ๊ทผ์ ๊ฐ์ง๋ง, ์ฝ๋ ํํ๋ง ๋ค๋ฅด๋ค.
์ฌ๊ธฐ์์ k
๋ ํ๊ณผ ์ด์ด ๋ง๋ ๊ฐ์ ๋์ํ์ฌ ๊ณ์ฐํ๊ฒ ๋ ํ์๋ฅผ ๋ํ๋ธ๋ค.
์๊ฐ๋ณต์ก๋๋ 3์ค for๋ฌธ์ผ๋ก ์ด ๋ฐฉ๋ฒ๋ ์ฒซ๋ฒ์งธ ๋ฐฉ๋ฒ๊ณผ ๋์ผํ๊ฒ O(n*m*k)
์๊ฐ๋ณต์ก๋์ด๋ค. ์ด๋ฅผ ์ข ๋ ์ ํํ๊ฒ ๋ณด์๋ฉด,
์ฌ์ค k๋ row ๊ธธ์ด col๊ธธ์ด์๋ ๋๋ฑํ๋ค๊ณ ๋ณผ ์ ์์ผ๋ฏ๋ก O(k^3)
์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค. (=๋ฐฉ๋ฒ1๋ ๋ง์ฐฌ๊ฐ์ง์ด๋ค)
function solution(arr1, arr2){
let rows=arr1.length;
let cols = arr2[0].length;
let result = Array.from({length: rows},()=> Array.from({length: cols},()=> 0))
for(let row=0; row<rows; row++){
for(let col=0; col<cols; col++){
for(let k=0; k<rows[0].length; k++ ){
result[row][col] += arr1[row][k] * arr[k][col]
}
}
}
return result;
}
2. ๋ฐฉ๋ฌธ๊ธธ์ด
์ถ์ฒ : https://school.programmers.co.kr/learn/courses/30/lessons/49994
4๊ฐ์ง ๋ช ๋ น์ด๋ฅผ ํตํด ์์ง์ด๋ ค ํฉ๋๋ค. ๋ช ๋ น์ด๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- U: ์์ชฝ์ผ๋ก ํ ์นธ ๊ฐ๊ธฐ
- D: ์๋์ชฝ์ผ๋ก ํ ์นธ ๊ฐ๊ธฐ
- R: ์ค๋ฅธ์ชฝ์ผ๋ก ํ ์นธ ๊ฐ๊ธฐ
- L: ์ผ์ชฝ์ผ๋ก ํ ์นธ ๊ฐ๊ธฐ
์บ๋ฆญํฐ๋ ์ขํํ๋ฉด์ (0, 0) ์์น์์ ์์ํฉ๋๋ค. ์ขํํ๋ฉด์ ๊ฒฝ๊ณ๋ ์ผ์ชฝ ์(-5, 5), ์ผ์ชฝ ์๋(-5, -5), ์ค๋ฅธ์ชฝ ์(5, 5), ์ค๋ฅธ์ชฝ ์๋(5, -5)๋ก ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
์บ๋ฆญํฐ๊ฐ ์ฒ์ ๊ฑธ์ด๋ณธ ๊ธธ์ ๊ธธ์ด๋ฅผ ๊ตฌํด์ผ ํ๋ค.
์ ์ถ๋ ฅ ์
dirs | answer |
---|---|
"ULURRDLLU" | 7 |
"LULLLLLLU" | 7 |
์ด ๋ฌธ์ ๋ ๋๊ฐ์ง ํต์ฌํฌ์ธํธ๊ฐ์๋ค.
- ์ค๋ณต ๊ฒฝ๋ก ์ฒ๋ฆฌ ๋ฐฉ๋ฒ
- ์ขํ์ ๊ฒฝ๊ณ๊ฐ -5 ๋ถํฐ 5๊น์ง์ ๊ฒฝ๊ณ๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
๋จผ์ ์ค๋ณต ๊ฒฝ๋ก ์ฒ๋ฆฌ ๋ฐฉ๋ฒ์ ๋ณด์๋ฉด, ์ค๋ณต ๊ฒฝ๋ก๋ ๋๊ฐ์ง ๊ฒฝ์ฐ๊ฐ ์๋ค.
- aโb, bโa ์ ๊ฒฝ๋ก์ธ๊ฒฝ์ฐ ์ค๋ณต์ผ๋ก ๊ฐ์ฃผํ๊ณ , ์ฒ์ ๋ฐฉ๋ฌธํ ๊ธธ์ด์ ํฌํจํ์ง ์๋๋ค.
- aโb, aโb ๋๊ฐ์ ์ถ๋ฐ์ ๊ณผ ๋์ฐฉ์ ์ ๋๋ฒ ์ด์ ๋ฐฉ๋ฌธํ๋ ๊ฒฝ์ฐ์๋ ๋น์ฐํ ์ค๋ณต์ด๋ฏ๋ก ์ฒ์ ๋ฐฉ๋ฌธํ ๊ธธ์ด์ ํฌํจํ์ง ์๋๋ค.
์ค๋ณต ๊ฒฝ๋ก๋ฅผ ์ฒ๋ฆฌํ๊ธฐ ์ํด ์ข์ ์๋ฃ๊ตฌ์กฐ๋ Set ์ด๋ค.
์ 1 ๋ฒ์ ๊ฒฝ์ฐ, ์ฒ์ ๋ฐฉ๋ฌธํ์ ๋ ์ถ๋ฐ์ขํ->๋์ฐฉ์ขํ, ๋์ฐฉ์ขํ->์ถ๋ฐ์ขํ๋ก ๋๊ฐ์ง ๊ฒฝ์ฐ๋ฅผ ๋ชจ๋ set์ ๋ฃ๋๋ค. ๊ทธ ์ด์ ๋ ๋ค์์ ๋ฐ๋๋ฐฉํฅ์ ๊ฒฝ๋ก๊ฐ ์๋ค๋ฉด ์ด๋ฏธ set์ ์๊ธฐ๋๋ฌธ์ ์ค๋ณต์ผ๋ก ๊ฐ์ฃผํ๊ณ ์ฒ์ ๊ฑธ์ด ๋ณธ ๊ธธ์ด์ ํฌํจํ์ง ์์ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค.
์ 2 ๋ฒ์ ๊ฒฝ์ฐ, set ํจ์๋ฅผ ์ฌ์ฉํ์ฌ ์ ์ด์ ์ค๋ณต๋ ๊ฒ์ ํฌํจํ์ง ์๊ณ ๋ฐฐ์ ํ๋ค.
์ขํ์ ๊ฒฝ๊ณ์ฒ๋ฆฌ
- ์ฃผ์ด์ง ๊ทธ๋ฆผ์์ผ๋ก๋ (0,0)์์ ์์ํ์ฌ -5์ 5์ฌ์ด์ ์ ์ฌ๊ฐํ ๋ฒ์์์ ์์ง์ธ๋ค.
- ๋๊ฐ์ ๊ฒฝ์ฐ๋ ํญ์ ์ผ์ชฝ์๋จ ๋์ (0,0)์ผ๋ก ์์ํ๋ ๊ฒ์ ์ต์ํ์ฌ ์์์ขํ๋ฅผ ์ ์ด์ (5,5) ๋ก ๋๋ค.
- ๋ฒ์๋ (0,10)์ผ๋ก ๋๋ค. (๊ฐ์ธ์ ์ธ ์๊ฐ์ผ๋ก๋ x,y์ขํ๋ฅผ ์์๋ก ๋๋๊ฒ ๋ฌธ์ ํ ๋ ์ค์์ ์ํ์ ์ค์ฌ์ค๋ค.)
์ ์ฒด์ ์ธ ๋ฌธ์ ์ ๊ทผ๋ฒ
1. (5,5) ์์ ์ฃผ์ด์ง ๋ช ๋ น๋ฌธ์ ํตํด ๋ฐฉํฅ์ ์ค์ ํ๊ณ 1์นธ ์์ง์ธ๋ค.
2. ์ด๋ํ ๋ค์ ์ขํ๊ฐ ์ฃผ์ด์ง ์ขํํ๋ฉด์ ๋ฒ์์ ์ ํจํ์ง ๊ฒ์ฌํ๋ค.
2-1. ๋ง์ฝ ์ ํจํ์ง ์๋ค๋ฉด, ์์ง์ผ ํ์๊ฐ ์๋ค.
2-2. ๋ง์ฝ ์ ํจํ๋ค๋ฉด, ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ฅผ ํ๋ค
3. ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ฅผ ํ๊ธฐ ์ , ํ์ฌ ๋ฐฉ๋ฌธํ ๊ณณ์ด ์ด๋ฏธ ๋ฐฉ๋ฌธํ๋ ๊ฒฝ๋ก์ธ์ง ๋จผ์ ํ์ธํ๋ค.
3-1. set์ ์๋ฃ๊ตฌ์กฐ๋ฅผ ํตํด O(1)์ ๋ณต์ก๋๋ก ๋ฐฉ๋ฌธ์ฒ๋ฆฌ์ ๋น์ฉ์ ๋ง์ด ๋ค์ด์ง ์๊ณ ํ์ธํ ์ ์๋ค. ์ด๋ฏธ set์ ์๋ค๋ฉด, ๋์ด์ ๋ฐฉ๋ฌธ์ฒ๋ฆฌํ ํ์๊ฐ ์๋ค.
3-2. ๋ง์ฝ ์ฒ์ ๋ฐฉ๋ฌธํ ๊ณณ์ด๋ผ๋ฉด(set์ ์๋ ๊ฒฝ์ฐ), (์ถ๋ฐ ์ขํ,๋์ฐฉ์ขํ )(๋์ฐฉ์ขํ,์ถ๋ฐ์ขํ)๋ฅผ ์ถ๊ฐํ๋ค.
3.3 ์ฒ์ ๊ฐ๋ณธ ๊ธธ์ด์ +1์ถ๊ฐํ๋ค.
4. ๋ง์ง๋ง ๋ฐฉํฅ ์ง์๋ฌธ์ ๋๋ด๊ณ ๋์, ์ด ๋ฐฉ๋ฌธ ํ ๊ธธ์ด๋ฅผ ๋ฆฌํดํ๋ค. ๋๋ set ์์ ์ด๋ฏธ ํ๊ฒฝ๋ก์ ๋๊ฐ์ง์ ๊ฒฝ์ฐ๋ฅผ ๋ค ๋ด๊ณ ์์ผ๋, set์ ์ฌ์ด์ฆ์์/2ํ ๊ฐ์ ๋ฆฌํดํ๋ ๋ฐฉ๋ฒ๋ ์๋ค.
function solution(dirs){
let current = [5, 5];
let count =0;
for (const dir of dirs) {
const index = direction[dir];
const nx = current[0] + dx[index];
const ny = current[1] + dy[index];
if (nx < 0 || ny < 0 || nx > 10 || ny > 10) continue;
//check if visited
const visitedX = nx;
const visitedY = ny;
if (!visited[visitedX][visitedY]) {
visited[visitedX][visitedY] = `${current[0]}${current[1]}`;
visited[current[0]][current[1]] = `${visitedX}${visitedY}`;
count += 1;
current = [nx, ny];
continue;
}
if (
visited[visitedX][visitedY].indexOf(`${current[0]}${current[1]}`) !== -1 ||
visited[current[0]][current[1]].indexOf(`${visitedX}${visitedY}`) !== -1
){
current = [nx, ny];
continue;
}
current = [nx, ny];
count += 1;
}
return count;
}
์ด ๋ฌธ์ ์ ์๊ฐ๋ณต์ก๋๋ ์ฃผ์ด์ง ๋ฐฉํฅ ๋ช ๋ น๋ฌธ์ ๊ธธ์ด ๋งํผ๋ง ์ํํ๋ฏ๋ก O(dirs.length) ๊ฐ ๋๋ค.
์ด๋ฒ ์ฃผ ํ๊ณ
- 2D array๋ ํ๋ก ํธ์์ ๊ตฌํ์ผ๋ก ์๋นํ ๋ง์ด ์ฐ์ด๋๋ฐ ์๊ฐ๋ณด๋ค ์ฝ๊ฒ ํ์ง ๋ชปํ๋ ๊ฒ ๊ฐ๋ค.(์ข ๋ ์ฐ์ตํ์)
- ์ฑ ์ ๋ฌธ์ ์ธ์๋ ์คํฐ๋์์ leetcode ๋ฌธ์ ๋ค๋ ์ถ๊ฐ์ ์ผ๋ก ํธ๋๋ฐ ์๊ฐ๋ณด๋ค ๋ฐฐ์ด์ ๋ฌธ์ ์์ ๊ณต๊ฐ๋ณต์ก๋๋ฅผ ์ต์ ํํ๋ ๋ฌธ์ ๋ค์ด ํฅ๋ฏธ๋ก์ ๋ค.