JH 개발 블로그

https://softeer.ai/practice/6250

배열에 점수와 인덱스를 잘 담아서 정렬 하면 되는 문제였다.

1. 배열에 점수와 인덱스를 저장한다.

2. 배열을 내림차순 정렬한다. ( 점수 기준으로 )

3. 내림차순 정렬된 배열의 인덱스를 바탕으로 정답 배열의 인덱스에 rank를 매긴다. (내림차순 배열의 이전 요소가 지금 요소와 같다면 rank 값은 그대로, 아니라면 i+1)  

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 점수, 인덱스를 담을 배열 생성
        // 마지막 행은 total 점수
        int[][][] arr = new int[4][n][2];

        for (int i=0; i<3; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j=0; j<n; j++) {
                int score = Integer.parseInt(st.nextToken());
                // [0]은 점수
                // [1]은 인덱스
                arr[i][j][0] = score;
                arr[i][j][1] = j;

                // 토탈 스코어
                arr[3][j][0] += score;
                arr[3][j][1] = j;
            }
        }


        // 내림차순 정렬
        for (int i=0; i<4; i++) {
            Arrays.sort(arr[i],(a,b) -> b[0] - a[0]);
        }

        // 정답 배열
        int[][] answer = new int[4][n];

        
        for (int i=0; i<4; i++) {

            // 매 대회마다 1로 초기화
            int rank = 1;
            answer[i][arr[i][0][1]] = rank;
            for (int j=1; j<n; j++) {
                // 이전이랑 점수가 다르면 j+1
                if (arr[i][j][0] != arr[i][j-1][0]) {
                    rank = j+1;
                }
                int idx = arr[i][j][1];
                answer[i][idx] = rank;
            }
        }

        for (int i=0; i<4; i++) {
            for (int j=0; j<n; j++) {
                System.out.print(answer[i][j] + " ");
            }
            System.out.println();
        }
    }
}

언어별 시간/메모리

언어시간메모리

JavaScript	1초	1024MB
C	1초	1024MB
C++	1초	1024MB
Java	1초	1024MB
Python	2초	1024MB

대학교 학부생활을 마치고 현대자동차에 프로그래머로 취직한 사회초년생 현빈이는 팀장님에게 보안에 관련한 지식이 하나도 없음을 들키고 말았다. 그래서 현빈이는 업무시간 틈틈이 보안과 관련된 주제들을 공부하고 있다.

오늘 공부할 주제는 암호화 방식중 하나인 Playfair cipher(플레이페어 암호)다. Playfair cipher는 알파벳으로 이루어진 어떤 문자열(평문; plaintext)을 암호화하는 방법으로, 이를 위해 알파벳으로 이루어진 문자열인 키(key)가 필요하다. Playfair cipher는 빈도분석을 어렵게 하기 위해 한번에 두 글자 단위로 암호화를 진행하며, 5×5크기의 표를 사용하기 때문에 알파벳 26개를 모두 담기에는 칸이 한 개 부족해 I와 J를 동일한 것으로 생각한다. 이 문제에서는 편의상 J가 아예 주어지지 않는다.

 

먼저, 주어진 키를 5×5크기의 표로 변환한다. 키를 한 글자씩 보면서 왼쪽 위 칸부터 한줄씩 표를 채운다. 만약 이전에 봤던 알파벳이 한번 더 등장하면 무시하고 다음 글자를 보면 된다. 키를 다 보고도 칸이 남는다면, 아직 등장하지 않은 알파벳을 순서대로 채워넣으면 된다. 예를 들어 키가 PLAYFAIRCIPHERKEY라면 다음과 같이 표가 만들어진다. 굵게 표시된 알파벳이 키를 통해 채워진 알파벳이다.

다음 일은 암호화하려는 메세지를 두 글자씩 나누는 일이다. 예를 들어, HELLOWORLD라는 메세지를 두 글자씩 나눈다면 HE LL OW OR LD가 된다. LL같이 두 글자로 이루어진 쌍이 생기면 중간에 다른 글자를 넣어 쌍을 파괴해줘야 한다. 이렇게 같은 두 글자로 이루어진 쌍이 생기면 그 중 가장 앞에 있는 쌍 사이에 X를 넣고 뒤쪽은 새롭게 쌍을 구성하면 된다. 만약, 쌍이 XX였다면 X를 넣어서는 해결이 안되기 때문에 Q를 넣는 것으로 해결 한다. 이렇게 쌍을 모두 맞추고 마지막에 한 글자가 남는다면 이것도 암호화가 불가능하기 때문에 여기도 X를 덧붙여 강제로 쌍을 맞춰준다. 마지막 남은 한 글자가 X인 경우에는 예외적으로 XX로 쌍을 맞춘다.

그러므로, HELLOWORLD를 두 글자씩 나누는 올바른 방법은 HE LX LO WO RL DX이고, XXYYY를 두 글자씩 나누는 올바른 방법은 XQ XY YX YX가 된다. 마지막으로, 쌍을 만든 두 글자를 암호화하는 일이 남았다. 다음과 같은 세 가지 경우가 있는데, 위에서 만든 5×5표를 통해 설명해본다.

1. 만약, 두 글자가 표에서 같은 행에 존재하면, 오른쪽으로 한 칸 이동한 칸에 적힌 글자로 암호화된다. 예를 들어 HE를 암호화하면 EI가 되고, XX를 암호화하면 ZZ가 된다. 위치가 다섯 번째 열이라면 첫 번째 열로 이동하게 된다.

2. 1.의 경우를 만족하지 않으면서 두 글자가 표에서 같은 열에 존재하면, 아래쪽으로 한 칸 이동한 칸에 적힌 글자로 암호화된다. 예를 들어 LO를 암호화하면 RV가 된다. 위치가 다섯 번째 행이라면 첫 번째 행으로 이동하게 된다.

3. 1, 2의 경우를 만족하지 않으면서, 두 글자가 표에서 서로 다른 행, 열에 존재하면, 두 글자가 위치하는 칸의 열이 서로 교환된 위치에 적힌 글자로 암호화된다. 예를 들어 LX를 암호화하면 YV가 된다.

이 과정에 따르면, HELLOWORLD를 Playfair cipher로 암호화한 결과는 EIYVRVVQBRGW가 된다.

현빈이는 어떤 메세지와 키가 주어졌을 때 주어진 메세지를 Playfair cipher로 암호화하려고 한다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String msg = br.readLine();
        String key = br.readLine();

        // 5x5 배열을 만든다.
        char[][] arr = new char[5][5];

        // 알파벳 리스트를 만든다.
        List<Character> alphabetList = new ArrayList<>();
        for (int i=0; i<26; i++) {
            if ((char) ('A'+i) == 'J') {
                continue;
            }
            alphabetList.add((char)('A'+i));
        }

        int r = 0;
        int c = 0;

        // 알파벳 리스트 안에 key의 알파벳이 존재하면 배열에 넣고, 리스트에선 삭제한다.
        for (int i=0; i<key.length(); i++) {
            char alphabet = key.charAt(i);
            if (alphabetList.contains(alphabet)) {
                arr[r][c] = alphabet;
                alphabetList.remove(Character.valueOf(alphabet));
                c++;
                if (c%5 == 0) {
                    c = 0;
                    r++;
                }
            }
        }

        for (int i=0; i<alphabetList.size(); i++) {
            arr[r][c] = alphabetList.get(i);
            c++;
            if (c%5 == 0) {
                c = 0;
                r++;
            }
        }

        List<String> strList = new ArrayList<>();

        for(int i=0; i<msg.length(); i+=2) {

            if (i == msg.length() -1 ) {
                strList.add(msg.charAt(i) + "X");
                continue;
            }

            if (msg.charAt(i) == msg.charAt(i+1)) {
                if (msg.charAt(i) == 'X') {
                    strList.add("XQ");
                    i--;
                    continue;
                } else {
                    strList.add(msg.charAt(i) + "X");
                    i--;
                    continue;
                }
            } else {
                strList.add(msg.substring(i,i+2));
            }
        }

        StringBuilder answer = new StringBuilder();

        for (String str : strList) {
            char first = str.charAt(0);
            char second = str.charAt(1);

            int nr1 = 0;
            int nc1 = 0;
            int nr2 = 0;
            int nc2 = 0;

            for (int i=0; i<5; i++) {
                for (int j=0; j<5; j++) {
                    if (arr[i][j] == first) {
                        nr1 = i;
                        nc1 = j;
                    }

                    if (arr[i][j] == second) {
                        nr2 = i;
                        nc2 = j;
                    }
                }
            }

            // 같은 행이라면
            if (nr1 == nr2) {
                if (nc1 == 4) {
                    nc1 = 0;
                } else {
                    nc1++;
                }

                if (nc2 == 4) {
                    nc2 = 0;
                } else {
                    nc2++;
                }
                answer.append(arr[nr1][nc1] + "" + arr[nr2][nc2]);
            }
            // 같은 열이라면
            else if (nc1 == nc2) {
                if (nr1 == 4) {
                    nr1 = 0;
                } else {
                    nr1++;
                }

                if (nr2 == 4) {
                    nr2 = 0;
                } else {
                    nr2++;
                }
                answer.append(arr[nr1][nc1] + "" + arr[nr2][nc2]);
            }
            // 둘다 아니라면
            else {
                int temp = nc1;
                nc1 = nc2;
                nc2 = temp;

                answer.append(arr[nr1][nc1] + "" + arr[nr2][nc2]);
            }
        }


        System.out.println(answer);

    }
}

은근 5x5 배열을 채워넣는 부분에서 시간이 오래걸렸다 . 처음엔 set으로 할까 하다가 꼬임

나머지 암호화부분은 단순히 if문으로 처리하면 되는거라 쉬웠음

언어별 시간/메모리

언어시간메모리

JavaScript	1초	1024MB
C	1초	1024MB
C++	1초	1024MB
Java	1초	1024MB
Python	1초	1024MB

Sam은 팀장님으로부터 차량이 이동 가능한 시나리오의 수를 찾으라는 업무 지시를 받았습니다. 이동은 숫자 0과 1로만 이루어져 있는 n x n 크기의 격자 위에서 일어납니다. 숫자 0은 빈 칸을 의미하며, 숫자 1은 해당 칸이 벽으로 막혀 있음을 의미합니다. 아래는 n이 3인 경우의 예시입니다.

 

0 0 0
0 0 0
0 0 1

 

차량은 n x n 격자 내에서 m개의 지점을 순서대로 방문하려고 합니다. 이 때 이동은 항상 상하좌우 중 인접한 칸으로만 이동하되 벽은 지나갈 수 없으며, 한 번 지났던 지점은 다시는 방문해서는 안 됩니다. 이러한 조건 하에서 차량이 이동 가능한 서로 다른 가지 수를 구하는 프로그램을 작성해보세요.

 

방문해야 하는 지점의 첫 지점이 출발점이며, 마지막 지점이 도착점임에 유의합니다.

 

위의 예에서 m = 3, 방문해야 하는 지점이 순서대로 (3행, 1열), (1행, 2열), (2행, 3열)이라면, 다음과 같이 5가지의 시나리오가 가능합니다.

 

1. (3행, 1열) → (3행, 2열) → (2행, 2열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

 

2. (3행, 1열) → (3행, 2열) → (2행, 2열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

 

3. (3행, 1열) → (2행, 1열) → (2행, 2열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

 

4. (3행, 1열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (1행, 3열) → (2행, 3열)

 

5. (3행, 1열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (2행, 2열) → (2행, 3열)

 

import java.io.*;
import java.util.*;

public class Main {

    static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
    static int n,m;
    static int[][] map;
    static boolean[][] visited;
    static List<int[]> checkPoints = new ArrayList<>();
    static int result = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        map = new int[n][n];
        visited = new boolean[n][n];
        
        
        for (int i=0; i<n; i++) {
            input = br.readLine().split(" ");
            for (int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }

        
        for (int i=0; i<m; i++) {
            input = br.readLine().split(" ");
            int r = Integer.parseInt(input[0]) - 1;
            int c = Integer.parseInt(input[1]) - 1;
            checkPoints.add(new int[]{r,c});
        }

        visited[checkPoints.get(0)[0]][checkPoints.get(0)[1]] = true;
        dfs(checkPoints.get(0)[0],checkPoints.get(0)[1], 1);

        System.out.println(result);
    }

    static void dfs(int r, int c, int depth) {
        // 지금 도착한 장소가 체크포인트라면
        if (r == checkPoints.get(depth)[0] && c == checkPoints.get(depth)[1]) {

            // 마지막 체크포인트라면
            if (depth == m - 1) {
                result++;
                return;
            } 
            // 아니라면
            else {
                depth++;
            }
        }

        for (int i=0; i<4; i++) {
            int nr = r + dir[i][0];
            int nc = c + dir[i][1];

            // map 밖으로 나가면 안됨
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;

            // 벽으론 못감
            if (map[nr][nc] == 1) continue;

            // 이미 들린 곳은 못감
            if (visited[nr][nc] == true) continue;

            visited[nr][nc] = true;
            dfs(nr,nc,depth);
            visited[nr][nc] = false;
        }
    }
}

n이 값이 작기 때문에 해당 풀이로 풀었다. 

위 풀이에선 잘못된 순서로 갈 경우에 그것이 잘못된 경로라는걸 인지 못하고 끝까지 탐색한다. 

만약 n이 클 경우엔 문제가 생기지 않을까 ? 그래서 set에 경로를 담아서 현재 경로가 set에 contain 되어있는지 여부를 검사하고, 잘못된 순서일경우 back 하는 로직을 추가하면 좀 더 효율적이지 않을까 생각해본다.. 매번 set을 검사하는거라 결국 거기서 거긴가.. 잘 모르겠다.