한양대학교 ERICA 알고리즘 연구학회 영과일의 내부 대회 "ZOAC 2019"의 문제 출제 및 검수를 맡게 되었습니다.
그중 A번 문제인 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;
}
'Coding' 카테고리의 다른 글
[BOJ][ZOAC 2019]18244번 - 변형 계단 수 (0) | 2019.12.30 |
---|---|
[BOJ][ZOAC 2019]18243번 - Small World Network (0) | 2019.12.30 |
2018.04.18 1st Semester 한양대 에리카 자료구조 과제 LinkedStack, LinkedQueue (1) | 2018.04.18 |
2018.04.03 1st Semester 한양대 에리카 자료구조 과제 DoublyLinkedList (0) | 2018.04.18 |
2018.03.28 1st Semester 한양대 에리카 자료구조 과제 SinglyLinkedList (0) | 2018.03.29 |