☌

[DIAMOND] 다이아몬드

개발이야기/알고스팟2022. 1. 6. 21:43

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/DIAMOND

 

algospot.com :: DIAMOND

다이아몬드 문제 정보 문제 ......#............................ ..#.######......................... .##########..........###........... ..#.#########......#######......... ......#............#######......... ....................####.#......... ...

www.algospot.com

 

풀이입니다. 🤔

 

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;
 
public class Main {
    private static final char SHARP = '#';
    private static final char[][] board = new char[50][50];
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int h = scanner.nextInt(), w = 0;
            for (int i = 0; i < h; ++i) {
                String line = scanner.next();
                w = line.length();
                for (int j = 0; j < w; ++j) {
                    board[i][j] = line.charAt(j);
                }
            }
 
            int ret = 0;
            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    ret = Math.max(ret, getMaxDiamondLength(i, j, h, w));
                }
            }
 
            System.out.println(ret);
        }
    }
 
    private static int getMaxDiamondLength(int y, int x, int h, int w) {
        int ret = 0, safety = 0;
        for (int goal = 1; goal <= h; goal += 2) {
            int center = goal / 2;
            for (int distance = safety; distance < goal; ++distance) {
                if (y + distance >= h
                        || !hasLine(y + distance, x, w, (distance > center) ? goal - distance - 1 : distance)) {
                    return ret;
                }
            }
 
            ret = goal;
            safety = center; // 다이아몬드가 있는 것이 증명되었다면, 다음 회차에서 Center 까지는 정확한 # 이 존재함을 보장한다.
        }
        return ret;
    }
 
    private static boolean hasLine(int y, int x, int w, int distance) {
        int startX = x - distance, endX = x + distance;
        if (startX < 0) return false;
        if (endX >= w) return false;
 
        for (int i = startX; i <= endX; ++i) if (board[y][i] != SHARP) return false;
        return true;
    }
}
 cs이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[MVP] Most Valuable Programmer  (0) 2022.01.07
[MISPELL] Mispelling  (0) 2022.01.06
[ENCODING] Encoding  (0) 2022.01.06
[CANDLESTICK] Candlestick Charts  (0) 2022.01.06
[KAKURO1] Kakuro I  (0) 2022.01.06
Posted by N'
,

[ENCODING] Encoding

개발이야기/알고스팟2022. 1. 6. 20:50

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/ENCODING

 

algospot.com :: ENCODING

Encoding 문제 정보 문제 Chip and Dale have devised an encryption method to hide their (written) text messages. They first agree secretly on two numbers that will be used as the number of rows (R) and columns (C) in a matrix. The sender encodes an int

www.algospot.com

 

풀이입니다. 🤔

 

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.*;
 
public class Main {
    private static final char EMPTY = 0;
    private static final Map<Character, String> binaries = new HashMap<>();
    private static final int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 
    static {
        char[] buffer = new char[]{'0', '0', '0', '0', '0'};
 
        // 케이스마다 문자를 이진수로 변환할 시, 중복계산을 없애기 위해 초기화 시 기록을 한다.
        binaries.put(' ', new String(buffer));
        for (char c = 'A'; c <= 'Z'; ++c) {
            int i = buffer.length - 1;
            do {
                if (buffer[i] == '0') {
                    buffer[i] = '1';
                    break;
                }
                else buffer[i--] = '0';
            } while (i >= 0);
 
            binaries.put(c, new String(buffer));
        }
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        char[][] board = new char[20][20];
 
        int cases = scanner.nextInt();
        for (int n = 1; n <= cases; ++n) {
            int r = scanner.nextInt(), c = scanner.nextInt(), y = 0, x = 0, directionIndex = 0;
            String line = scanner.nextLine().trim();
            for (char character : line.toCharArray()) {
                for (char digit : binaries.get(character).toCharArray()) {
                    board[y][x] = digit;
 
                    int[] direction = directions[directionIndex];
                    if (outOfBoard(y + direction[0], r)
                            || outOfBoard(x + direction[1], c)
                            || board[y + direction[0]][x + direction[1]] != EMPTY) {
                        directionIndex = (directionIndex + 1) % directions.length;
                        direction = directions[directionIndex];
                    }
                    y += direction[0];
                    x += direction[1];
                }
            }
 
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < r; ++i) {
                for (int j = 0; j < c; ++j) {
                    builder.append(board[i][j] == EMPTY ? '0' : board[i][j]);
                    board[i][j] = EMPTY;
                }
            }
 
            System.out.printf("%d %s\n", n, builder);
        }
    }
 
    private static boolean outOfBoard(int value, int max) {
        return value < 0 || value >= max;
    }
}
 cs


이 문제는 아래 문제와 짝을 이루는 문제로, 안내에 따라 문자를 Encoding 합니다. 

 

[DECODE] Decoding


주요 살펴볼 사항은 총 두가지입니다. 

 

1. 제한된 이진수 변환을 빠르게 하기 위해, 초기화 과정을 수행했습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
 
public class Main {
   static {
        char[] buffer = new char[]{'0', '0', '0', '0', '0'};
 
        // 케이스마다 문자를 이진수로 변환할 시, 중복계산을 없애기 위해 초기화 시 기록을 한다.
        binaries.put(' ', new String(buffer));
        for (char c = 'A'; c <= 'Z'; ++c) {
            int i = buffer.length - 1;
            do {
                if (buffer[i] == '0') {
                    buffer[i] = '1';
                    break;
                }
                else buffer[i--] = '0';
            } while (i >= 0);
 
            binaries.put(c, new String(buffer));
        }
    }
}
 cs

 

 

2. 나선모양으로 변경하기 위해, 4가지 방향에 대한 상대좌표를 이용하도록 하였습니다.

 

1
    private static final int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 cs

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[MISPELL] Mispelling  (0) 2022.01.06
[DIAMOND] 다이아몬드  (0) 2022.01.06
[CANDLESTICK] Candlestick Charts  (0) 2022.01.06
[KAKURO1] Kakuro I  (0) 2022.01.06
[FESTIVAL] 록 페스티벌  (0) 2022.01.06
Posted by N'
,

[CANDLESTICK] Candlestick Charts

개발이야기/알고스팟2022. 1. 6. 18:49

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/CANDLESTICK

 

algospot.com :: CANDLESTICK

Candlestick Charts 문제 정보 문제 A candlestick chart, often abbreviated to candle chart, is a variation of a bar chart. It is mostly used to describe the price of a stock over time. You are using a simple candle chart which looks like above. Each ba

www.algospot.com

 

풀이입니다. 🤔

 

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
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[][] intervals = new int[2000][2];
 
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int n = scanner.nextInt();
            for (int i = 0; i < n; ++i) {
                intervals[i][0] = scanner.nextInt();
                intervals[i][1] = scanner.nextInt();
            }
 
            int ret = 0;
            for (int i = 0; i < n; ++i) {
                int min = -1, max = Integer.MAX_VALUE;
                for (int day = 0, maxDay = n - i; day < maxDay; ++day) {
                    min = Math.max(min, intervals[i + day][0]);
                    max = Math.min(max, intervals[i + day][1]);
 
                    ret = Math.max(ret, (day + 1) * (max - min));
                }
            }
            System.out.println(ret);
        }
    }
}
 cs

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[DIAMOND] 다이아몬드  (0) 2022.01.06
[ENCODING] Encoding  (0) 2022.01.06
[KAKURO1] Kakuro I  (0) 2022.01.06
[FESTIVAL] 록 페스티벌  (0) 2022.01.06
[NOTE] Note  (0) 2022.01.06
Posted by N'
,
Daum / Designed by i2i Labs

티스토리툴바