Codeforces Round #604 (Div. 2)
문제 링크 : https://codeforces.com/contest/1265 A. Beautiful String 문제 요약 '?'을 'a', 'b', 'c' 중 하나로 치환하여 인접한 두 문자가 같지 않도록 만들 수 있는지 확인하고, 가능하면 그 값을 출력하는 문제이다. 접근 방법 문자열이 A[1]부터 A[N]까지 있다고 하면(N은 입력받은 문자열의 길이), A[0]과 A[N+1]에는 더미 문자를 미리 삽입하면 A[1]과 A[N]에서도 양 옆의 문자열을 확인하면 되므로 따로 처리를 할 필요가 없어진다고 생각하였다. 시간복잡도 이미 입력 받은 값이 불가능한 값인지 체크하는 부분이 O(n)이고, 값을 생성하는 부분이 O(n)이므로 총 O(n)이 걸린다고 생각한다. #include #include using..
알고리즘
2019. 12. 15. 14:38