[baekjoon] 백준 1464번(파이썬): 뒤집기 3

문제

1464번: 뒤집기 3

- 세준이는 어떤 문자열 S를 뒤집으려고 한다.

- 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자.

- i만큼을 뒤집는다는 소리는 그 문자열의 처음부터 정확하게 i개의 문자를 역순으로 뒤집는 것이다.

- 세준이는 1부터 N까지 수를 차례대로 생각한다. 그리고, 뒤집을지 안 뒤집을지 선택할 수 있다.

- 예를 들어, S="BCDAF" 이고, 세준이가 길이 1만큼을 뒤집지 않고, 길이 2만큼도 뒤집지 않고 세준이가 길이 3만큼을 뒤집는다고 하면 문자열은 DCBAF가 된다. 다시 여기서 4만큼 뒤집으면 ABCDF가 된다. 그리고, 마지막으로 길이를 5만큼 뒤집지 않으면 주어진 문자열 S를 사전 순으로 가장 앞서게 만들 수 있다.

- 문자열 S가 주어졌을 때, 위와 같은 뒤집기 방법으로 만들 수 있는 문자열 중 사전 순으로 제일 앞서는 것을 구하는 문제이다.

- 문자열 S가 주어진다. 문자열의 길이는 최대 10,000이다. 알파벳 대문자만 들어온다.

알고리즘

- 문자열을 입력받는다.

- 문자열의 문자를 아스키 코드로 변환하여 순서를 비교하기 편하게 한다.

- 초기 타겟 값을 만들고 계속해서 뒤집을 때 사용할 리스트를 만든다.

- 반복문을 통해 현재 아스키 코드가 타겟보다 크면 타겟을 뒤로 보낸다.

- 타겟을 뒤로 보내는 과정에서 뒤집기를 2번 한다. 예를 들어) 2, 1, 3 일 경우 2, 1을 뒤집어 1, 2, 3을 만들고 전체를 한번 더 뒤집어 3, 2, 1을 만든다. 더 자세한 내용은 밑에 결과에서 확인해보자. 

- 타겟이 더 큰 경우에는 다음 아스키 코드로 타겟을 변경해주고 리스트에 아스키 코드를 추가한다.

- 위 과정을 반복하여 작은 수를 뒤로 보낸다.

- 큰 수 순서대로 만들어진 리스트는 반복문을 통해 작은 수 순서대로 문자열을 더하여 출력한다.

코드

import sys

s = list(str(sys.stdin.readline()))
# \n 제거
s.pop()
ascii_code = []
reverse = []
result = ""

# 문자를 아스키 코드로 변환
for i in s:
    ascii_code.append(ord(i))

# 초기 타겟
target = ascii_code[0]
reverse.append(target)

# 반복문을 통해 작은 수를 뒤로 보낸다.
for i in range(1, len(s)):
    # 타겟과 현재 아스키 코드 비교
    if target < ascii_code[i]:
        # 현재 아스키 코드가 크므로 한번 뒤집어준다.
        reverse.reverse()
        # 현재 아스키 코드를 추가하고 다시 뒤집어 작은 수를 뒤로 보낸다.
        reverse.append(ascii_code[i])
        reverse.reverse()
    else:
        # 타겟이 더 크면 타겟을 현재 아스키 코드로 바꾼다.
        target = ascii_code[i]
        # 현재 아스키 코드를 추가한다.
        reverse.append(ascii_code[i])

# 아스키 코드를 문자로 변환해서 문자열로 만든다.
# 문자열은 다시 뒤집어 줘야하기때문에 뒤집어서 반복한다.
for i in reversed(reverse):
    result += chr(i)

print(result)

결과

위 코드에서 두 번째 반복문 맨 밑에 print(reverse)를 작성하면 매 순간마다 어떤 형태로 뒤집는지 다음 출력 화면과 같이 확인할 수 있다.

<출력화면>

(아스키 코드 A: 65, B: 66, C: 67, D: 68, F: 70) 위 출력 화면을 보게 되면 처음에 C가 타겟 B보다 크기 때문에 reverse 리스트를 한번 뒤집고 C를 추가하여 리스트를 또 뒤집어 67, 66 이 된 것을 확인할 수 있다. 다음으로 D와 비교하게 되고 D도 마찬가지로 타겟 B보다 크기 때문에 reverse 리스트를 한번 뒤집고 D를 추가하여 리스트를 또 뒤집어 68, 67, 66이 된 것을 확인할 수 있다. 그다음으로 A와 비교하게 되고 A는 B보다 작기 때문에 타겟을 A로 바꿔주고 리스트에 A를 추가하여 68, 67, 66, 65가 된 것을 확인할 수 있다. 마지막으로 F와 비교하는데 F는 타겟 A보다 크기 때문에 reverse 리스트를 한번 뒤집고 F를 추가하여 리스트를 또 뒤집어 70, 68, 67, 66, 65가 된 것을 확인할 수 있다. 모든 문자를 확인했기 때문에 마지막 반복문을 통해 문자를 거꾸로 출력하고 출력한 문자를 모두 더해 결과값을 출력한다.  

github

junjange/CodingTest