๐ ๋ฌธ์
๊ฒ์๊ฐ๋ฐ์์ธ ์ฃ ๋ฅด๋๋ ํฌ๋ ์ธ ์ธํ๋ฝ๊ธฐ ๊ธฐ๊ณ๋ฅผ ๋ชจ๋ฐ์ผ ๊ฒ์์ผ๋ก ๋ง๋ค๋ ค๊ณ ํฉ๋๋ค.
์ฃ ๋ฅด๋๋ ๊ฒ์์ ์ฌ๋ฏธ๋ฅผ ๋์ด๊ธฐ ์ํด ํ๋ฉด ๊ตฌ์ฑ๊ณผ ๊ท์น์ ๋ค์๊ณผ ๊ฐ์ด ๊ฒ์ ๋ก์ง์ ๋ฐ์ํ๋ ค๊ณ ํฉ๋๋ค.
๊ฒ์ ํ๋ฉด์ 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 ๋ฐฐ์ด์ ๊ฐ๋ก ํฌ๊ธฐ ์ดํ์ธ ์์ฐ์์ ๋๋ค.
๐ ํ์ด
- Board๋ฅผ 1์ค์ฉ ํ๋ก ๋ง๋ค์ด์ค๋ค.
- ์ธํ์ ๋ฝ๊ณ ๋๋ฉด ๋ด์ ํต, ์คํ์ ๋ง๋ค์ด์ค๋ค.
- moves ๋ฐฐ์ด์ ๋๋ฉด์ ํด๋น ์ธ๋ฑ์ค์ ๊ฐ์ฅ ์์ ์๋ ์ธํ์ ๊บผ๋ธ๋ค.
- ์คํ์ ๋ด๊ธฐ ์ ์ ๊ฐ์ฅ ์์ ์๋ ์ธํ์ด๋ ๊ฐ์ ์ธํ์ธ์ง ํ์ธํ๋ค.
- ๊ฐ์ ์ธํ์ด๋ฉด +2๋ฅผ ํด์ฃผ๊ณ ์คํ์ ์๋ ์ธํ์ ๋บ๋ค.
- ๊ฐ์ ์ธํ์ด ์๋๋ผ๋ฉด, ๊ทธ๋๋ก ์คํ์ ๋ฃ๋๋ค.
๐ ์ฝ๋
import java.util.*;
import static org.assertj.core.api.Assertions.assertThat;
public class ๋ฌธ์ 1 {
@Test
void test() {
int[][] board = {{0,0,0,0,0},{0,0,1,0,3},{0,2,5,0,1},{4,2,4,4,2},{3,5,1,3,1}};
int[] moves = {1, 5, 3, 5, 1, 2, 1, 4};
assertThat(solution(board, moves)).isEqualTo(4);
}
public int solution(int[][] requestBoard, int[] moves) {
int answer = 0;
List<Queue<Integer>> board = init(requestBoard);
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < moves.length; i++) {
int moveIndex = moves[i] - 1;
Queue<Integer> q = board.get(moveIndex);
if (!q.isEmpty()) {
int doll = q.poll();
if (!stack.isEmpty() && stack.peek() == doll) {
stack.pop();
answer += 2;
} else {
stack.add(doll);
}
}
}
return answer;
}
private List<Queue<Integer>> init(int[][] requestBoard) {
List<Queue<Integer>> result = new ArrayList<>();
for (int j = 0; j < requestBoard.length; j++) {
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < requestBoard.length; i++) {
int doll = requestBoard[i][j];
if (doll != 0) q.add(doll);
}
result.add(q);
}
return result;
}
}
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด์ญ ์ฝ๋ฉ ํ ์คํธ ๋ฌธ์ ํด์ค
“2019๋ ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด์ญ” ๊ณต๊ฐ ์ฑ์ฉ์ ์ํ 1์ฐจ ์ฝ๋ฉ ํ ์คํธ๊ฐ ์ง๋ 2019๋ 11์ 9์ผ ์คํ 2์๋ถํฐ 6์๊น์ง ์ด 4์๊ฐ์ ๊ฑธ์ณ ์งํ๋์์ต๋๋ค. ’19๋ ์ ์ ๊ณต์ฑ 1์ฐจ ์ฝ๋ฉ ํ ์คํธ ์์ 7๋ฌธ์ ๊ฐ ์ถ์ ๋๊ณ 5์๊ฐ์ ํ์ด ์๊ฐ์ด ์ฃผ์ด์ก๋ ๊ฒ๊ณผ๋ ๋ฌ๋ฆฌ ์ด๋ฒ ์ธํด ์ฝ๋ฉ ํ ์คํธ๋ 5๋ฌธ์ ๊ฐ ์ถ์ ๋๊ณ 4์๊ฐ์ ํ์ด ์๊ฐ์ด ์ฃผ์ด์ก์ต๋๋ค. ์ธํด์ ๊ฒฝ์ฐ ์ ์ ๊ณต์ฑ์๋ ๋ฌ๋ฆฌ ์ธํด ๊ณผ์ ์ ํตํด ์ถ๊ฐ […]
tech.kakao.com
'Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๐ 2019 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ๊ณต์ฑ: ํ๋ณดํค (Java) (0) | 2020.05.03 |
---|---|
๐ค 2020 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ๊ณต์ฑ: ์๋ฌผ์ ์ ์ด์ (Java) (0) | 2020.04.28 |
๐ ํ๋ก๊ทธ๋๋จธ์ค: Lv3. ์ ๊ตญ ์ฌ์ฌ (Java) (0) | 2020.04.25 |
๐ ์นด์นด์ค 2019 ๊ฒจ์ธ ์ธํด์ญ: ๋ถ๋ ์ฌ์ฉ์(Lv3) (0) | 2020.04.05 |
๐ ์นด์นด์ค 2019 ๊ฒจ์ธ ์ธํด์ญ: ํฌ๋ ์ธ ์ธํ๋ฝ๊ธฐ ๊ฒ์(Lv2) (0) | 2020.04.01 |
๐จ ์นด์นด์ค 2019 ๊ฒจ์ธ ์ธํด์ญ: ํธํ ๋ฐฉ ๋ฐฐ์ (Lv4) (0) | 2020.04.01 |