[BOJ][ZOAC 2019]18238번 - ZOAC 2

한양대학교 ERICA 알고리즘 연구학회 영과일의 내부 대회 "ZOAC 2019"의 문제 출제 및 검수를 맡게 되었습니다.

 

그중 A번 문제인 ZOAC 2에 대한 풀이입니다.

 

목표

ZOAC 2 문제 캡처

문제를 보시면 아시다 싶이 알파벳이 순서대로 써져 있는 원판을 돌리면서 원하는 문장열을 순서대로 가장 빠르게 출력하는데 걸리는 시간을 구하는 문제입니다.

 

먼저, 원판을 돌릴 수 있는 방법이 2가지라는 것을 알 수 있습니다. 한번 돌리기 시작하면 한쪽으로만 돌려야 하기에 (ex. 왼쪽으로 돌렸으면 다음 문자까지 왼쪽으로만 돌려야 한다.) 다음 문자열까지 왼쪽으로만 혹은 오른쪽으로만 돌려야 합니다. 이 돌리는 횟수를 A: 1(27) ~ Z: 26(52)까지 두고 현재 문자에서 다음 문자까지의 거리라고 한다면 거리는 다음과 같이 표현될 수 있습니다.

• abs(다음 문자 - 현재 문자)
• 26 - abs(다음 문자 - 현재 문자)

또는

• 다음 문자 - 현재 문자 (음수이면 +26) 
• 현재 문자 - 다음 문자 (음수이면 +26)

그러므로 해당 2개의 값 중에서 최소 값만 뽑아내어 모든 문자열을 탐색하면 되는 문제입니다.

 

모든 문자열을 탐색하므로 문제의 시간 복잡도는 O(문자열의 길이) == O(N)입니다.

 

코드

Python3 (두 번째 방법)

input = input()

ans = min(abs(ord('A') + 26 - ord(input[0])), ord(input[0]) - ord('A')) # 처음 화살표는 'A'를 가리킨다.
for i in range(len(input)-1) :
	# abs 처리
    left = ord(input[i]) - ord(input[i+1])
    right = ord(input[i+1]) - ord(input[i])
    if left < 0:
        left += 26
    if right < 0:
        right += 26
    ans += min(abs(left), abs(right))
print(ans)

C++ (첫 번째 방법)

#include <bits/stdc++.h>

using namespace std;

int main(){
	string inp;
	cin >> inp;
    int ans = 0;
    inp = 'A' + inp; // 처음 화살표는 'A'를 가리킨다.
    for(int i = 0; i < inp.size()-1; i++){
    	ans += min(abs((inp[i+1] - 'A') - (inp[i] - 'A')), 26 - abs((inp[i+1] - 'A') - (inp[i] - 'A')));
        // 왼쪽, 오른쪽중 최솟값을 더함
    }
    cout << ans << '\n';
    return 0;
}

---