2149. [Python]암호 해독

1. 문제

 

https://www.acmicpc.net/problem/2149

2149번: 암호 해독

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 정렬

 

3. 파이썬 코드

 

# 키를 담을 변수
keyword = input()
# 암호문을 담을 변수
texts = input()
# 키의 길이
keyword_length = len(keyword)
# 암호문의 길이
texts_length = len(texts)
# 암호문의 길이에서 키의 길이를 나눠준 변수 => 리스트 길이때문에
answer_length = texts_length//keyword_length
# 암호문을 길이에 맞도록 잘라서 담을 리스트
texts_list = []
# 들어온 키 값을 인덱스 번호와 함께 저장할 리스트
check_list = []
# 정렬된 순서를 저장할 리스트
answer_list= []
# 인덱스 번호를 저장할 변수
cnt = 0
# 들어온 키값을 인덱스 번호와 리스트에 튜플 형태로 저장함
for i in keyword:
    check_list.append((i,cnt))
    cnt += 1
# 키값을 정렬
check_list.sort()

# 인덱스 순서를 담을 변수
cnt = 0
# sort를 사용하였기 때문에 기존의 문자들의 위치를 모르기 때문에 cnt 변수를 사용하여 몇번위치부터 순서대로 정렬됐는지 answer_list 에 추가해준다.
for i in range(keyword_length):
    for j in range(keyword_length):
        if check_list[j][1] == cnt:
            answer_list.append(j)
            cnt += 1
            break
# answer_length 간격마다 문자를 잘라서 리스트에 저장해준다.
for i in range(keyword_length):
    check = i*answer_length
    texts_list.append(texts[check:check+answer_length])
# 정답을 출력할 변수
answer = ""
# answer_list 에 저장된 인덱스번호 순서대로 answer에 값을 더해준다
for j in range(answer_length):
    for i in range(len(texts_list)):
        answer += texts_list[answer_list[i]][j]

print(answer)

 

4. 문제를 풀고난 후 생각

 

• 처음 문제를 보고 key 값이 주어지고 평문이 주어진 후 그 평문을 암호문으로 변환하는 방식으로 문제를 풀어봤다.
• 내가 푼 예제와 출력 예제 값이 다른 것을 보고 문제의 조건을 다시 살펴보았고, 암호문으로 변환된 값을 key를 통해서 다시 평문으로 출력하는 것이 문제에서 요구한 사항이였다.
• 이를 구현하기 위해서 변환하는 과정을 역산을 진행했지만, 현재 수준에서 생각할 수 있는 직관적으로 코드를 작성했다.
• 문자를 cnt 라는 변수와 함께 인덱스 위치를 튜플로 묶어서 sort를 사용하여 정렬해 주었고, 다시 이 정렬된 리스트를 순회하며 0 ~ N 까지 각각 어디 위치에 존재하는지 리스트에 저장해 주었다.
  => BCA 가 들어올 경우 (B,0) / (C,1) / (A,2) 이런 식으로 튜플로 저장한 다음 sort 를 통해서 (A,2) / (B,0) / (C,1) 이렇게 정렬 된 값을 ( 0 번 인덱스의 현재 위치 / 1번 인덱스의 현재 위치 / 2번 인덱스의 현재 위치 )를 리스트에 저장했다.
• 어떠한 순서로 저장됐는지 리스트를 만들어 두었고 이제 암호문을 word의 길이만큼 나눈 값으로 잘라서 리스트에 넣어줬다.
• 이렇게 잘라진 리스트에서 정렬된 순서대로 리스트의 앞의 값들을 뽑아서 문자열을 더해주면 평문이 완성된다.
• 말로 설명하기엔 복잡한 부분이 많아서 직접 생각해보고 어떤 식으로 변형이 되는지 직접 적어봐야 문제를 푸는데 이해할 수 있을 것 같다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 정렬