-
[Algo Rhythm๐บ๐] 2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด์ญ ํฌ๋ ์ธ ์ธํ๋ฝ๊ธฐ ๊ฒ์Algo Rhythm๐บ๐/others 2020. 7. 4. 20:28
๋ฌธ์ ์ค๋ช
๊ฒ์๊ฐ๋ฐ์์ธ ์ฃ ๋ฅด๋๋ ํฌ๋ ์ธ ์ธํ๋ฝ๊ธฐ ๊ธฐ๊ณ๋ฅผ ๋ชจ๋ฐ์ผ ๊ฒ์์ผ๋ก ๋ง๋ค๋ ค๊ณ ํฉ๋๋ค.
์ฃ ๋ฅด๋๋ ๊ฒ์์ ์ฌ๋ฏธ๋ฅผ ๋์ด๊ธฐ ์ํด ํ๋ฉด ๊ตฌ์ฑ๊ณผ ๊ท์น์ ๋ค์๊ณผ ๊ฐ์ด ๊ฒ์ ๋ก์ง์ ๋ฐ์ํ๋ ค๊ณ ํฉ๋๋ค.
๊ฒ์ ํ๋ฉด์ 1 x 1 ํฌ๊ธฐ์ ์นธ๋ค๋ก ์ด๋ฃจ์ด์ง N x N ํฌ๊ธฐ์ ์ ์ฌ๊ฐ ๊ฒฉ์์ด๋ฉฐ ์์ชฝ์๋ ํฌ๋ ์ธ์ด ์๊ณ ์ค๋ฅธ์ชฝ์๋ ๋ฐ๊ตฌ๋๊ฐ ์์ต๋๋ค. (์ ๊ทธ๋ฆผ์ 5 x 5 ํฌ๊ธฐ์ ์์์ ๋๋ค). ๊ฐ ๊ฒฉ์ ์นธ์๋ ๋ค์ํ ์ธํ์ด ๋ค์ด ์์ผ๋ฉฐ ์ธํ์ด ์๋ ์นธ์ ๋น์นธ์ ๋๋ค. ๋ชจ๋ ์ธํ์ 1 x 1 ํฌ๊ธฐ์ ๊ฒฉ์ ํ ์นธ์ ์ฐจ์งํ๋ฉฐ ๊ฒฉ์์ ๊ฐ์ฅ ์๋ ์นธ๋ถํฐ ์ฐจ๊ณก์ฐจ๊ณก ์์ฌ ์์ต๋๋ค. ๊ฒ์ ์ฌ์ฉ์๋ ํฌ๋ ์ธ์ ์ข์ฐ๋ก ์์ง์ฌ์ ๋ฉ์ถ ์์น์์ ๊ฐ์ฅ ์์ ์๋ ์ธํ์ ์ง์ด ์ฌ๋ฆด ์ ์์ต๋๋ค. ์ง์ด ์ฌ๋ฆฐ ์ธํ์ ๋ฐ๊ตฌ๋์ ์์ด๊ฒ ๋๋ ๋ฐ, ์ด๋ ๋ฐ๊ตฌ๋์ ๊ฐ์ฅ ์๋ ์นธ๋ถํฐ ์ธํ์ด ์์๋๋ก ์์ด๊ฒ ๋ฉ๋๋ค. ๋ค์ ๊ทธ๋ฆผ์ [1๋ฒ, 5๋ฒ, 3๋ฒ] ์์น์์ ์์๋๋ก ์ธํ์ ์ง์ด ์ฌ๋ ค ๋ฐ๊ตฌ๋์ ๋ด์ ๋ชจ์ต์ ๋๋ค.
๋ง์ฝ ๊ฐ์ ๋ชจ์์ ์ธํ ๋ ๊ฐ๊ฐ ๋ฐ๊ตฌ๋์ ์ฐ์ํด์ ์์ด๊ฒ ๋๋ฉด ๋ ์ธํ์ ํฐ๋จ๋ ค์ง๋ฉด์ ๋ฐ๊ตฌ๋์์ ์ฌ๋ผ์ง๊ฒ ๋ฉ๋๋ค. ์ ์ํ์์ ์ด์ด์ [5๋ฒ] ์์น์์ ์ธํ์ ์ง์ด ๋ฐ๊ตฌ๋์ ์์ผ๋ฉด ๊ฐ์ ๋ชจ์ ์ธํ ๋ ๊ฐ๊ฐ ์์ด์ง๋๋ค.
ํฌ๋ ์ธ ์๋ ์ ์ธํ์ด ์ง์ด์ง์ง ์๋ ๊ฒฝ์ฐ๋ ์์ผ๋ ๋ง์ฝ ์ธํ์ด ์๋ ๊ณณ์์ ํฌ๋ ์ธ์ ์๋์ํค๋ ๊ฒฝ์ฐ์๋ ์๋ฌด๋ฐ ์ผ๋ ์ผ์ด๋์ง ์์ต๋๋ค. ๋ํ ๋ฐ๊ตฌ๋๋ ๋ชจ๋ ์ธํ์ด ๋ค์ด๊ฐ ์ ์์ ๋งํผ ์ถฉ๋ถํ ํฌ๋ค๊ณ ๊ฐ์ ํฉ๋๋ค. (๊ทธ๋ฆผ์์๋ ํ๋ฉดํ์ ์ ์ฝ์ผ๋ก 5์นธ๋ง์ผ๋ก ํํํ์์)
๊ฒ์ ํ๋ฉด์ ๊ฒฉ์์ ์ํ๊ฐ ๋ด๊ธด 2์ฐจ์ ๋ฐฐ์ด board์ ์ธํ์ ์ง๊ธฐ ์ํด ํฌ๋ ์ธ์ ์๋์ํจ ์์น๊ฐ ๋ด๊ธด ๋ฐฐ์ด moves๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ํฌ๋ ์ธ์ ๋ชจ๋ ์๋์ํจ ํ ํฐํธ๋ ค์ ธ ์ฌ๋ผ์ง ์ธํ์ ๊ฐ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
[์ ํ์ฌํญ]
-
board ๋ฐฐ์ด์ 2์ฐจ์ ๋ฐฐ์ด๋ก ํฌ๊ธฐ๋ 5 x 5 ์ด์ 30 x 30 ์ดํ์ ๋๋ค.
-
board์ ๊ฐ ์นธ์๋ 0 ์ด์ 100 ์ดํ์ธ ์ ์๊ฐ ๋ด๊ฒจ์์ต๋๋ค.
-
0์ ๋น ์นธ์ ๋ํ๋ ๋๋ค.
-
1 ~ 100์ ๊ฐ ์ซ์๋ ๊ฐ๊ธฐ ๋ค๋ฅธ ์ธํ์ ๋ชจ์์ ์๋ฏธํ๋ฉฐ ๊ฐ์ ์ซ์๋ ๊ฐ์ ๋ชจ์์ ์ธํ์ ๋ํ๋ ๋๋ค.
-
moves ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 1 ์ด์ 1,000 ์ดํ์ ๋๋ค.
-
moves ๋ฐฐ์ด ๊ฐ ์์๋ค์ ๊ฐ์ 1 ์ด์์ด๋ฉฐ board ๋ฐฐ์ด์ ๊ฐ๋ก ํฌ๊ธฐ ์ดํ์ธ ์์ฐ์์ ๋๋ค.
์ด๋ป๊ฒ ํ์๋
import java.util.Stack; import java.util.HashMap; class Solution { public int solution(int[][] board, int[] moves) { int answer = 0; // <K, V> -> <# Col, Stack> Stack<Integer> basket = new Stack<>(); HashMap<Integer, Stack<Integer>> grid = new HashMap<Integer, Stack<Integer>>(); // init for(int i = board.length - 1; i >= 0; i--) { for(int j = 0; j < board[i].length; j++) { int col = j + 1; if(board[i][j] != 0) { Integer doll = Integer.valueOf(board[i][j]); if(grid.containsKey(col)) { Stack<Integer> stack = grid.get(col); stack.push(doll); grid.replace(col, stack); } else { Stack<Integer> stack = new Stack<Integer>(); stack.push(doll); grid.put(col, stack); } } } } for(int move : moves) { Stack<Integer> stack = grid.get(move); if(!stack.isEmpty()) { Integer doll = stack.pop(); // remove two dolls if(basket.size() > 0 && basket.peek() == doll) { basket.pop(); answer += 2; } else { basket.push(doll); } } } return answer; } }
์ ์ ๋ ๊ฒ ํ์๋
ํฌ๊ธฐ๊ฐ n X n ์ธ board์ basket์ ํํํ๊ธฐ ์ํ ์๋ฃ๊ตฌ์กฐ๊ฐ ํ์ํ๋ค.
์ธํ์ด ์์ด๋ ๋ชจ์ต์ ๋ณด๋ ์คํ์ด ๋ ์ฌ๋๊ณ ๊ฐ col๋ณ๋ก ์ธํ์ ์์ด๋ ๋ชจ์ต์ ๋ณด๋ ํด์๋งต์ด ๋ ์ฌ๋๋ค. ๊ทธ๋์ key๊ฐ์ด col์ด๊ณ value๊ฐ stack์ธ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํด์ board๋ฅผ ํํํ๋ค.
Basket๋ ์ธํ์ด ์์ด๋ ๊ทธ ๋ชจ์ต์ ๋ณด๊ณ ์คํ์ด ๋ ์ฌ๋๋ค.
์๋ฃ๊ตฌ์กฐ๋ฅผ ์ ํ๊ณ ๋๋ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ๋จํ๋ค.
๋จผ์ ๋งค๊ฐ๋ณ์ ์ค ํ๋์ธ 2์ฐจ์ ๋ฐฐ์ด board๋ฅผ traverseํ๋ฉด์ board๋ฅผ ์ด๊ธฐํํ๋ค.
๊ทธ๋ฆฌ๊ณ ํฌ๋ ์ธ์ด ๋ฉ์ถ๋ ์์น๋ค์ ๋ชจ์๋์ moves๋ฅผ traverseํ๋ฉด์ board์์ ์ธํ์ ๊บผ๋ด basket์ addํ๋ค. ์ด๋ ๋ง์ฝ addํ๋ ค๋ ์ธํ๊ณผ top์ ์๋ ์ธํ์ด ๊ฐ์ผ๋ฉด ์ธํ์ addํ์ง ์๊ณ popํ๋ค. ์ด๊ฒ์ ๊ฐ์ ์ธํ ๋ ๊ฐ๊ฐ ๋ง๋ ํฐ์ก๋ค๋ ๊ฒ์ ์๋ฏธํ๊ธฐ ๋๋ฌธ์ answer๋ฅผ 2 ์ฆ๊ฐํ๋ค.
๋ฌด์์ ๋ฐฐ์ ๋
์ด ๋ฌธ์ ๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ๋ ์ฌ๋ฆด ์ ์๋๊ฐ๋ฅผ ๋ฌป๋ ๋ฌธ์ ์๋ค๊ณ ์๊ฐํ๋ค.
์ด ๋ฌธ์ ๋ฅผ ํตํด ๊ธฐ์ด์ ์ค์์ฑ์ ์ฌํ์ธํ ์ ์์๋ค.
'Algo Rhythm๐บ๐ > others' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
-