๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Algorithm

๐Ÿ— ์นด์นด์˜ค 2019 ๊ฒจ์šธ ์ธํ„ด์‹ญ: ํฌ๋ ˆ์ธ ์ธํ˜•๋ฝ‘๊ธฐ ๊ฒŒ์ž„(Lv2)

๐Ÿ“Œ ๋ฌธ์ œ

๊ฒŒ์ž„๊ฐœ๋ฐœ์ž์ธ ์ฃ ๋ฅด๋””๋Š” ํฌ๋ ˆ์ธ ์ธํ˜•๋ฝ‘๊ธฐ ๊ธฐ๊ณ„๋ฅผ ๋ชจ๋ฐ”์ผ ๊ฒŒ์ž„์œผ๋กœ ๋งŒ๋“ค๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.
์ฃ ๋ฅด๋””๋Š” ๊ฒŒ์ž„์˜ ์žฌ๋ฏธ๋ฅผ ๋†’์ด๊ธฐ ์œ„ํ•ด ํ™”๋ฉด ๊ตฌ์„ฑ๊ณผ ๊ทœ์น™์„ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ฒŒ์ž„ ๋กœ์ง์— ๋ฐ˜์˜ํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

๊ฒŒ์ž„ ํ™”๋ฉด์€ 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 ๋ฐฐ์—ด์˜ ๊ฐ€๋กœ ํฌ๊ธฐ ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

๐Ÿ“Œ ํ’€์ด

  1. Board๋ฅผ 1์ค„์”ฉ ํ๋กœ ๋งŒ๋“ค์–ด์ค€๋‹ค.
  2. ์ธํ˜•์„ ๋ฝ‘๊ณ  ๋‚˜๋ฉด ๋‹ด์„ ํ†ต, ์Šคํƒ์„ ๋งŒ๋“ค์–ด์ค€๋‹ค.
  3. moves ๋ฐฐ์—ด์„ ๋Œ๋ฉด์„œ ํ•ด๋‹น ์ธ๋ฑ์Šค์— ๊ฐ€์žฅ ์œ„์— ์žˆ๋Š” ์ธํ˜•์„ ๊บผ๋‚ธ๋‹ค.
  4. ์Šคํƒ์— ๋‹ด๊ธฐ ์ „์— ๊ฐ€์žฅ ์œ„์— ์žˆ๋Š” ์ธํ˜•์ด๋ž‘ ๊ฐ™์€ ์ธํ˜•์ธ์ง€ ํ™•์ธํ•œ๋‹ค.
  5. ๊ฐ™์€ ์ธํ˜•์ด๋ฉด +2๋ฅผ ํ•ด์ฃผ๊ณ  ์Šคํƒ์— ์žˆ๋Š” ์ธํ˜•์„ ๋บ€๋‹ค.
  6. ๊ฐ™์€ ์ธํ˜•์ด ์•„๋‹ˆ๋ผ๋ฉด, ๊ทธ๋Œ€๋กœ ์Šคํƒ์— ๋„ฃ๋Š”๋‹ค.

๐Ÿ“Œ ์ฝ”๋“œ

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