[백준] 2714 문자를 받은 승환이 (Baekjoon Problem 2714: Seunghwan Received Message)

문제 출처

[문제 요약]

승환이는 규현이에게 메시지를 받는다. 그런데 그냥 받는게 아닌 비밀 규칙을 적용해서 받는다.

 

우선 문자 메시지에 들어가는 글자는 알파벳 대문자와 공백으로 이루어져 있다.

글자는 아래처럼 십진수로 바꾼후 5자리 이진수로 바꾼다.

공백 = 0, A = 1, B = 2, ..., Y = 25, Z = 26

 

바뀐 이진수들은 시계방향의 소용돌이 패턴으로 행렬에 저장한다.

 

첫 줄에는 해석해야하는 행렬의 개수 (n) 를 받고 그 개수만큼 행렬을 입력을 받는다.

행렬의 행과 열, 그리고 소용돌이 패턴으로 저장된 행렬을 행 우선으로 한 줄로 읽은 것을 입력으로 받는다.

출력으로는 메시지를 프린트하면 된다.

 

추가적으로 행렬에서 남는칸은 0으로 채우고 만일 해석한 메시지의 끝에 공백이 있으면 공백은 제외하고 프린트 해야한다.

 

예를 들어 규현이가 보내는 메시지가 "ACM"이고, 행렬의 크기가 R=4, C=4라고 하면 아래처럼 메시지가 완성된다.

A = 00001, C = 00011, M = 01101

 

[풀이]

문제에 적힌대로 코드를 짜면 되는데 소용돌이 패턴을 만드는게 일이다.

코드로도 다소 복잡하게 되어서 이것보다 더 좋은 방식을 생각한다면 업데이트 할것 같다.

 

[row나 column index중 무엇을 어느쪽으로 바꿀지 정하는 변수: flag / direction]

우선 flag를 하나 정한다. 이건 row index를 바꿀지 column index를 바꿀지 결정하는 변수이다.

그리고 r_dir과 c_dir을 하나 만든다 (dir: direction (방향)의 약자). 이건 index를 바꿀때 어느 방향으로 바꿀지 결정하는 변수이다.

 

flag가 1이면 row index를 바꾸는거고 -1이면 column index를 바꾸는것이다.

r_dir도 1일때는 index를 1 더하고, r_dir가 -1일때는 index를 1 빼준다.

마찬가지로 c_dir도 1일때는 index를 1 더하고, r_dir가 -1일때는 index를 1 빼준다.

 

[행렬 소용돌이의 시작과 끝을 결정하는 변수: start / end]

어느 방향으로 바꿀지를 결정하는 함수에는 추가적으로 4개의 변수가 더 쓰인다.

index가 행렬의 끝에 다다르는걸 판별하기 위한 변수들이다.

여기서 숙지해야할 점은 r_start는 현재 가장 작은 index인 0보다 1 작다는것이고

r_end는 현재 가장 큰 index인 row_length (R-1) 보다 1 크다는 점이다. column도 마찬가지이다.

r_start는 -1, r_end는 R (row의 크기)

c_start도 -1, c_end는 C (column의 크기)

 

예를 들어 시작할때 column의 방향으로 index를 하나씩 더해주다가 index가 c_end - 1 (이 상황에서는 C-1가 되면)

• flag를 -1로 바꾸어 주어 row index를 바꾸는걸로 한다.
• c_dir 역시 -1로 바꾸어 추후 column index를 바꿀때 index를 하나씩 빼도록 한다.

방향 변환을 요약하면

• column index가 c_end에 다다르면 flag = -1 (row 방향), c_dir을 -1로 바꾼다.
• row index가 r_end에 다다르면 flag = 1 (column 방향), r_dir을 -1로 바꾼다.
• column index가 c_start에 다다르면 flag = -1 (row 방향), c_dir를 1로 바꾼다.
• row index가 r_start에 다다르면 flag = 1 (column 방향), r_dir을 1로 바꾼다.

[행렬 소용돌이의 크기가 작아짐에 따라 바뀌는 start / end]

마지막으로 r_start, r_end, c_start, c_end의 크기도 바꿔주어야 한다.

대신 바꾸는 타이밍이 중요한데 column의 index가 c_end - 1 에 다다른다고 해도, row가 r_end에 다다를때까지 유지시켜야한다.

하나 예시를 들기 위해 아래 그림을 다시 보자.

초반부에 column index가 c_end에 다다르기까지 r은 항상 0이다. r_start의 크기를 하나 더해준다. 그림을 참고하면 c_end가 c-1에 다다랐을때 이후로는 r이 0이 될 필요가 없어진다.

 

리밋 (start, end) 변화를 시계방향으로 요약하면

• column index가 c_end에 다다르면 r_start를 1 더해준다.
• row index가 r_end에 다다르면 c_end를 1 빼준다.
• column index가 c_start에 다다르면 r_end를 1 빼준다.
• row index가 r_start에 다다르면 c_start를 1 더해준다.

[유의할 점]

방향을 바꾸어주는것, 방향을 바꾸는 index의 경계의 값을 언제 바꾸는지 설계하는게 가장 주의할 점이다.

 

그 외의 주의할 점들은 아래 사항 정도인것 같다.

• binary가 string형태로 되어있어 bin() 함수를 쓰지 못하고 그냥 5-digit binary를 int로 바꾸는 함수를 따로 만들어야 함
  • 나중에 확인해보니 int 함수에 base도 같이 주면 바로 바뀐다 (*참고).
• 메시지를 다 넣은 후의 행렬의 빈공간은 0으로 채워 넣기 때문에 채워 넣은 0과 공백은 무시해야한다는 점
• 프린트는 나중에 한번에 몰아서 해야하는 점

*string to binary

int('1111', 2)
15

[파이썬 3 코드]

# alp = A to Z, 0 for space
# convert into 5-digit binary number

def return_idx(r_idx, c_idx, flag, r_dir, c_dir):
    if flag == 1 and r_dir == 1:
        r_idx += 1
    elif flag == 1 and r_dir == -1:
        r_idx -= 1
    elif flag == -1 and c_dir == 1:
        c_idx += 1
    else: # flag == -1 and c_dir == -1:
        c_idx -= 1

    return r_idx, c_idx


def check_edge(r_idx, c_idx, flag, r_dir, c_dir, r_str, c_str, r_end, c_end):
    # 방향을 트는것
    if r_idx == r_end:
        c_end -= 1
        flag = -1
        r_dir = -1
        r_idx -= 1
        # index 변화
        r_idx, c_idx = return_idx(r_idx, c_idx, flag, r_dir, c_dir)
    elif r_idx == r_str:
        c_str += 1
        flag = -1
        r_dir = 1
        r_idx += 1
        # index 변화
        r_idx, c_idx = return_idx(r_idx, c_idx, flag, r_dir, c_dir)
    elif c_idx == c_end:
        r_str += 1
        flag = 1
        c_dir = -1
        c_idx -= 1
        # index 변화
        r_idx, c_idx = return_idx(r_idx, c_idx, flag, r_dir, c_dir)
    elif c_idx == c_str:
        r_end -= 1
        flag = 1
        c_dir = 1
        c_idx += 1
        # index 변화
        r_idx, c_idx = return_idx(r_idx, c_idx, flag, r_dir, c_dir)
    

    return r_idx, c_idx, flag, r_dir, c_dir, r_str, c_str, r_end, c_end
        

def reorder(r, c, strnum):
    lst = []
    idx = c
    # 소용돌이 matrix 형태로 저장.
    # 다만 nested list는 아니고 column이 문자열인 형태
    for i in range(r):
        if i != r - 1:
            lst.append(strnum[idx-c:idx])
        else:
            lst.append(strnum[idx-c:])
        idx += c

    orig_lst = []
    # 변수들 설정
    r_idx = 0
    c_idx = 0
    flag = -1 # row_order = 1, column_order = -1
    r_dir = 1 # right = 1, left = -1
    c_dir = 1

    r_str = -1
    r_end = r
    c_str = -1
    c_end = c
    while len(orig_lst) != len(strnum):
        orig_lst.append(lst[r_idx][c_idx])
        # if flag == 1:
        #     return_r_idx
        # else:
        #     return_c_idx
        r_idx, c_idx = return_idx(r_idx, c_idx, flag, r_dir, c_dir)
    
        r_idx, c_idx, flag, r_dir, c_dir, r_str, c_str, r_end, c_end = check_edge(r_idx, c_idx, flag, r_dir, c_dir, r_str, c_str, r_end, c_end)

    # join the orig_lst into correct order strnum
    return "".join(orig_lst)


def conv_strbin_to_int(digit5, n=5):
    # 5자리 binary 수 -> 정수
    sum = 0
    to_add = 1
    for i in reversed(range(n)):
        if digit5[i] == '1':
            sum += to_add
        to_add = to_add << 1

    return sum


def conv_int_to_char(num):
    # 정수 -> 대문자 및 공백
    # (ascii code에서 대문자 A가 65여서 모든 알파벳 수에다 64 더해주는것.)
    if num == 0:
        return " "
    else:
        return chr(num + 64)
    

def conv_ascii(orig_str: str, n = 5):
    # 소용돌이를 풀어둔 binary 형태의 문자열 -> 메시지로 변환
    count = n
    res_str = []
    while len(orig_str) > count:
        _int = conv_strbin_to_int(orig_str[count-n:count])
        _char = conv_int_to_char(_int)
        count += n
        
        res_str.append(_char)

    if count == len(orig_str):
        l_int = conv_strbin_to_int(orig_str[count-n:])
        l_char = conv_int_to_char(l_int)
        res_str.append(l_char)

    return "".join(res_str)

def trim_end(res_str: str):
    # 메시지의 공백을 삭제하는 함수
    cut_idx = -1
    for i in range(len(res_str)-1, 0, -1):
        if res_str[i] != " ":
            break
        else:
            cut_idx = i

    if cut_idx == -1:
        return res_str
    else:
        return res_str[:cut_idx]


if __name__ == "__main__":
    # test case t
    num = int(input())

    msg_lst = []
    
    for i in range(num):
        r, c, str_num = input().split()
        r = int(r)
        c = int(c)
        orig_str = reorder(r, c, str_num) # 이진수로 된 문자열 string
        message = conv_ascii(orig_str) # 원래 문자열 리스트
        trimmed = trim_end(message)
        msg_lst.append(trimmed)

    for msg in msg_lst:
        print(msg)