문제 설명

압축

신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.

어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.

LZW 압축은 다음 과정을 거친다.

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
5. 단계 2로 돌아간다.

압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자.

색인 번호 1 2 3 ... 24 25 26

예를 들어 입력으로 KAKAO가 들어온다고 하자.

1. 현재 사전에는 KAKAO의 첫 글자 K는 등록되어 있으나, 두 번째 글자까지인 KA는 없으므로, 첫 글자 K에 해당하는 색인 번호 11을 출력하고, 다음 글자인 A를 포함한 KA를 사전에 27 번째로 등록한다.
2. 두 번째 글자 A는 사전에 있으나, 세 번째 글자까지인 AK는 사전에 없으므로, A의 색인 번호 1을 출력하고, AK를 사전에 28 번째로 등록한다.
3. 세 번째 글자에서 시작하는 KA가 사전에 있으므로, KA에 해당하는 색인 번호 27을 출력하고, 다음 글자 O를 포함한 KAO를 29 번째로 등록한다.
4. 마지막으로 처리되지 않은 글자 O에 해당하는 색인 번호 15를 출력한다.

현재 입력(w) 다음 글자(c) 출력 사전 추가(w+c)

이 과정을 거쳐 다섯 글자의 문장 KAKAO가 4개의 색인 번호 [11, 1, 27, 15]로 압축된다.

입력으로 TOBEORNOTTOBEORTOBEORNOT가 들어오면 다음과 같이 압축이 진행된다.

현재 입력(w) 다음 글자(c) 출력 사전 추가(w+c)

입력 형식

입력으로 영문 대문자로만 이뤄진 문자열 msg가 주어진다. msg의 길이는 1 글자 이상, 1000 글자 이하이다.

출력 형식

주어진 문자열을 압축한 후의 사전 색인 번호를 배열로 출력하라.

입출력 예제

msg answer

package LV2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class H17684 {
        public int[] solution(String msg) {
            Map<String, Integer> dict = new HashMap<>();
            List<Integer> result = new ArrayList<>();

            // 사전 초기화: A-Z까지의 모든 단어를 사전에 추가
            for(int i = 0; i < 26; i++) {
                dict.put(String.valueOf((char)('A' + i)), i + 1);
            }

            int dictSize = 27;  // 사전에 추가될 새로운 단어의 색인 번호
            int msgLength = msg.length();  // 입력된 메시지의 길이

            // 메시지를 순차적으로 확인
            for(int i = 0; i < msgLength; ) {
                String w = "";  // 현재 확인하고 있는 단어
                // 사전에 있는 단어인지 확인하며 메시지를 읽음
                while(i < msgLength && dict.containsKey(w + msg.charAt(i))) {
                    w += msg.charAt(i);
                    i++;
                }

                // 사전에 없는 단어를 찾아낸 경우 그 단어의 색인 번호를 결과에 추가
                result.add(dict.get(w));

                // 사전에 새로운 단어로 추가
                if(i < msgLength) {
                    dict.put(w + msg.charAt(i), dictSize++);
                }
            }

            // 결과를 배열로 변환하여 반환
            int[] answer = new int[result.size()];
            for(int i = 0; i < result.size(); i++) {
                answer[i] = result.get(i);
            }

            return answer;
        }
    }

A-Z까지의 모든 단어를 사전에 추가하고, 입력된 문자열을 순차적으로 확인하며 사전에 없는 단어를 찾아낼 때까지 반복한다.

사전에 없는 단어를 찾으면 그 단어의 색인 번호를 결과에 추가하고, 사전에 새로운 단어로 추가한다.

이 과정을 문자열의 끝까지 반복하고, 모든 과정이 끝나면 결과를 배열로 변환하여 반환한다.

문제 설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/dc3a1b49-13d3-4047-b6f8-6cc40b2702a7/최단거리1_sxuruo.png

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.

아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/9d909e5a-ca95-4088-9df9-d84cb804b2b0/최단거리2_hnjd3b.png

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/4b7cd629-a3c2-4e02-b748-a707211131de/최단거리3_ntxygd.png

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/d963b4bd-12e5-45da-9ca7-549e453d58a9/최단거리4_of9xfg.png

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

입출력 예

maps answer

입출력 예 설명

입출력 예 #1

주어진 데이터는 다음과 같습니다.

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/6db71f7f-58d3-4623-9fab-7cd99fa863a5/최단거리6_lgjvrb.png

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/d223d017-b3e2-4772-9045-a565133d45ff/최단거리2_hnjd3b (1).png

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2

문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

package LV2;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class H1844 {
    // 상, 하, 좌, 우로 이동하기 위한 델타 배열
    private final int[] dx = {-1, 1, 0, 0};
    private final int[] dy = {0, 0, -1, 1};

    public int solution(int[][] maps) {
        int n = maps.length; // 맵의 세로 크기
        int m = maps[0].length; // 맵의 가로 크기
        int[][] dist = new int[n][m]; // 시작 위치부터 각 위치까지의 최단 거리를 저장할 배열

        // dist 배열을 모두 -1로 초기화 (아직 방문하지 않은 위치를 의미)
        for (int[] row : dist) {
            Arrays.fill(row, -1);
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0}); // 시작 위치를 큐에 넣는다
        dist[0][0] = 1; // 시작 위치의 거리는 1

        // BFS 탐색 시작
        while (!queue.isEmpty()) {
            int[] cur = queue.poll(); // 현재 위치를 큐에서 꺼낸다
            for (int dir = 0; dir < 4; dir++) { // 상하좌우 4방향으로 이동
                int nx = cur[0] + dx[dir];
                int ny = cur[1] + dy[dir];
                // 맵의 범위를 벗어나거나 벽이 있는 경우 이동할 수 없음
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || maps[nx][ny] == 0) {
                    continue;
                }
                // 아직 방문하지 않은 위치인 경우
                if (dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[cur[0]][cur[1]] + 1; // 현재 위치의 거리 + 1
                    queue.offer(new int[]{nx, ny}); // 큐에 새로운 위치를 추가
                }
            }
        }

        // 도착지까지의 최단 거리를 반환. 도달할 수 없는 경우 -1을 반환
        return dist[n-1][m-1];
    }
}

그래프 탐색 문제로, 너비 우선 탐색(BFS) 알고리즘을 사용하여 해결할 수 있다. BFS는 시작 노드부터 가장 가까운 노드를 우선하여 그래프를 탐색하는 알고리즘이며, 이 문제에서는 시작 위치부터 목적지까지 가장 짧은 경로를 찾는 데 사용할 수 있다.

주어진 2차원 맵에서 이동 가능한 방향은 동, 서, 남, 북으로, 현재 위치에서 이동할 수 있는 위치를 큐에 넣어 탐색을 진행한다. 이 때, 맵의 범위를 벗어나거나 벽이 있는 곳(0)으로는 이동할 수 없다.

너비 우선 탐색(BFS) 알고리즘을 이용하여 주어진 맵에서 시작 위치(0, 0)부터 각 위치까지의 최단 거리를 구하고, 그 중 도착지(n-1, m-1)까지의 최단 거리를 반환

문제 설명

오픈채팅방

카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.

신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다.

"[닉네임]님이 들어왔습니다."

채팅방에서 누군가 나가면 다음 메시지가 출력된다.

"[닉네임]님이 나갔습니다."

채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.

• 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.
• 채팅방에서 닉네임을 변경한다.

닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.

예를 들어, 채팅방에 "Muzi"와 "Prodo"라는 닉네임을 사용하는 사람이 순서대로 들어오면 채팅방에는 다음과 같이 메시지가 출력된다.

"Muzi님이 들어왔습니다."

"Prodo님이 들어왔습니다."

채팅방에 있던 사람이 나가면 채팅방에는 다음과 같이 메시지가 남는다.

"Muzi님이 들어왔습니다."

"Prodo님이 들어왔습니다."

"Muzi님이 나갔습니다."

Muzi가 나간후 다시 들어올 때, Prodo 라는 닉네임으로 들어올 경우 기존에 채팅방에 남아있던 Muzi도 Prodo로 다음과 같이 변경된다.

"Prodo님이 들어왔습니다."

"Prodo님이 들어왔습니다."

"Prodo님이 나갔습니다."

"Prodo님이 들어왔습니다."

채팅방은 중복 닉네임을 허용하기 때문에, 현재 채팅방에는 Prodo라는 닉네임을 사용하는 사람이 두 명이 있다. 이제, 채팅방에 두 번째로 들어왔던 Prodo가 Ryan으로 닉네임을 변경하면 채팅방 메시지는 다음과 같이 변경된다.

"Prodo님이 들어왔습니다."

"Ryan님이 들어왔습니다."

"Prodo님이 나갔습니다."

"Prodo님이 들어왔습니다."

채팅방에 들어오고 나가거나, 닉네임을 변경한 기록이 담긴 문자열 배열 record가 매개변수로 주어질 때, 모든 기록이 처리된 후, 최종적으로 방을 개설한 사람이 보게 되는 메시지를 문자열 배열 형태로 return 하도록 solution 함수를 완성하라.

제한사항

• record는 다음과 같은 문자열이 담긴 배열이며, 길이는 1 이상 100,000 이하이다.
• 다음은 record에 담긴 문자열에 대한 설명이다.
  • 모든 유저는 [유저 아이디]로 구분한다.
  • [유저 아이디] 사용자가 [닉네임]으로 채팅방에 입장 - "Enter [유저 아이디] [닉네임]" (ex. "Enter uid1234 Muzi")
  • [유저 아이디] 사용자가 채팅방에서 퇴장 - "Leave [유저 아이디]" (ex. "Leave uid1234")
  • [유저 아이디] 사용자가 닉네임을 [닉네임]으로 변경 - "Change [유저 아이디] [닉네임]" (ex. "Change uid1234 Muzi")
  • 첫 단어는 Enter, Leave, Change 중 하나이다.
  • 각 단어는 공백으로 구분되어 있으며, 알파벳 대문자, 소문자, 숫자로만 이루어져있다.
  • 유저 아이디와 닉네임은 알파벳 대문자, 소문자를 구별한다.
  • 유저 아이디와 닉네임의 길이는 1 이상 10 이하이다.
  • 채팅방에서 나간 유저가 닉네임을 변경하는 등 잘못 된 입력은 주어지지 않는다.

입출력 예

record result

입출력 예 설명

입출력 예 #1

문제의 설명과 같다.

package LV2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class H42888 {
    public String[] solution(String[] record) {
        Map<String, String> nicknameMap = new HashMap<>(); // 유저 아이디를 키로, 해당 유저의 최종 닉네임을 값으로 하는 맵을 생성한다.
        List<String[]> commandList = new ArrayList<>(); // 각 커맨드와 유저 아이디를 저장하는 리스트를 생성한다.

        for (String r : record) { // record 배열을 순회한다.
            String[] splitR = r.split(" "); // 공백을 기준으로 문자열을 분리한다.
            String command = splitR[0]; // 첫 번째 요소는 커맨드이다.
            String uid = splitR[1]; // 두 번째 요소는 유저 아이디이다.

            // Enter와 Change 커맨드 모두 닉네임을 변경하는 커맨드이다.
            if (command.equals("Enter") || command.equals("Change")) {
                String nickname = splitR[2]; // 세 번째 요소는 닉네임이다.
                nicknameMap.put(uid, nickname); // 유저 아이디를 키로, 닉네임을 값으로 해서 맵에 저장한다.
            }

            // Enter와 Leave 커맨드에 대한 정보를 리스트에 저장한다.
            if (command.equals("Enter") || command.equals("Leave")) {
                commandList.add(new String[] {command, uid}); // 커맨드와 유저 아이디를 배열에 담아 리스트에 추가한다.
            }
        }

        String[] answer = new String[commandList.size()]; // 결과를 저장할 문자열 배열을 생성합니다. 크기는 commandList의 크기와 같다.
        for (int i = 0; i < commandList.size(); i++) { // commandList를 순회한다.
            String command = commandList.get(i)[0]; // i번째 요소의 첫 번째 값을 커맨드로 가져온다.
            String uid = commandList.get(i)[1]; // i번째 요소의 두 번째 값을 유저 아이디로 가져온다.
            String nickname = nicknameMap.get(uid); // 유저 아이디를 키로 해서 닉네임 맵에서 닉네임을 가져온다.

            // 커맨드에 따라서 메시지를 생성하고, 결과 배열에 저장한다.
            if (command.equals("Enter")) {
                answer[i] = nickname + "님이 들어왔습니다.";
            } else if (command.equals("Leave")) {
                answer[i] = nickname + "님이 나갔습니다.";
            }
        }
        return answer; // 결과 배열을 반환한다.
    }
}

유저 아이디에 대응하는 최종 닉네임을 **nicknameMap**에 저장하고, **Enter**와 Leave 커맨드와 그에 따른 유저 아이디를 **commandList**에 저장한다. 이후 **commandList**를 순회하면서, 각 유저의 마지막 닉네임과 커맨드에 따라 메시지를 생성하여 반환