(전공복습) 데이터과학 4. 시각화
차례
백준(BOJ) 1545 안티 팰린드롬 파이썬(Python)
간단한 그리디(Greedy) 구현 문제.
입력이 작아서 그냥 문제에서 요구하는 바를 나이브하게 구현하면 된다.
일단, 테스트 케이스를 보거나 조금만 생각해봐도 사전순으로 가장 앞서는 안티 팰린드롬을 찾으려면 문자를 가능한 만큼 몰아 넣어야 한다는 것을 알 수 있다.
왜냐하면, 너무나 상식적인 이야기지만, 'aaabbb'가 'ababab'보다 앞서지 않겠는가?
즉, 현재 가용한 문자 중 사전순으로 가장 빠른 문자 c가 있다고 할 때, 모든 c가 최대한 앞에 나와야 하고, 결국 그렇다면 c끼리는 가능한 뭉쳐져서 앞에 들어갈 수밖에 없다는 것을 쉽게 알 수 있다.
따라서, 우선 입력을 정렬한다. 정렬 비용은 \(O(N\log N)\)이므로 작은 데이터(\(N \le 50\))에 대해 쉽게 할 수 있다.
이후, 각 문자를 앞에서부터 넣으면 되는데, 문자를 넣을 때마다 배열(리스트)에 그 문자가 들어갈 수 없는 자리를 ban 리스트에 표시한다.
예를 들어, n=6인 문자열에서 ans[0]='a'라면 ans[5]에는 'a'가 올 수 없을 것이다(ban[5] = True).
이를 일반화하면 길이가 n인 문자열에서 ans[k]=c라면 ban[n-1-k] = True라는 얘기가 된다.
이렇게 그 문자가 올 수 없는 위치를 저장한 이후에, 문자를 넣기 전에 그 자리에 해당 문자가 올 수 있는지 확인하면 된다.
문자가 올 수 없다면 한 칸 뒤로 이동해서 해당 자리에는 문자가 올 수 있는지 확인하면 된다.
\(O(N)\)번 확인하므로 전체 반복은 \(O(N^2)\)이 될 것이다.
새로운 문자가 등장하면(입력을 정렬했으므로 같은 문자끼리는 무조건 모여 있다), ban 리스트를 초기화하고 계속 진행한다.
당연하지만, 이미 문자가 들어간 자리를 덮어씌우면 안 되므로 이 역시 확인해야 한다.
만약, 문자가 들어갈 자리를 정할 수 없으면(다시 말해 계속 뒤로 이동하다 문자열 밖으로 나가버리면) 해당 문자열은 안티 팰린드롬으로 만들 수 없는 문자열이므로 -1을 출력하고 끝낸다.
아니면, 비둘기집 원리(Pigeonhole Principle)에 의해, 어떤 문자 c가 \(\frac{N + 1}{2}\)개보다 많으면 안티 팰린드롬이 될 수 없다는 사실을 간단히 확인할 수 있다.
따라서 그러한 경우를 미리 확인해서 -1을 출력하고 끝내도록 하고, 그렇지 않은 경우에 대해서만 진행해도 상관 없을 것이다.
#!python
# s: 정렬된 문자 리스트
# n: 문자열의 길이
# ans: 정답 문자 리스트
# prev: 바로 직전 문자(어차피 정렬된 입력이므로 문자의 개수를 파악하는 데에 사용)
# j: 현재 ans에서 어디를 채울 차례인지
# bFlag: break를 해야 하는(즉 답이 -1인) 여부를 확인하는 flag
s = sorted(input())
n = len(s)
ans = [None] * n
prev = ''
j = 0
bFlag = False
# 정렬된 문자열에 대해 하나씩 순회
for i, c in enumerate(s):
# 새로운 문자가 등장하면 그 문자가 올 수 없는 위치를 저장하는 리스트인 ban을 초기화한다
if c != prev:
ban = [False] * n
# k는 문자 c가 들어가야 하는 위치로, 일단 j부터 시작한다
k = j
# k번 인덱스에 문자가 올 수 없거나, 이미 다른 문자가 채워져 있으면 k += 1
while ban[k] or ans[k] is not None:
k += 1
# k가 문자열 마지막 인덱스를 넘어가면 안티 팰린드롬이 불가능하므로 -1 출력 후 break
if k == n:
print(-1)
bFlag = True
break
if bFlag:
break
# k번 인덱스에 문자 c를 넣는다
ans[k] = c
# 다음 반복에서 이전 문자를 참조할 수 있도록 갱신한다
prev = c
# j == k라면 한번도 위의 while문을 돌지 않은 것
# 즉, 가능한 제일 앞자리에 문자 c를 넣은 것이므로 j를 증가시킨다
# 그렇지 않은 경우 여전히 j번 인덱스가 비어 있으므로 j를 그대로 둔다
if j == k:
j += 1
# k가 절반을 넘어간 경우 ban 리스트를 갱신할 필요가 없다(팰린드롬 여부를 확인할 필요가 없으므로)
# 그렇지 않은 경우는 대칭 위치 인덱스(n - 1 - k)를 사용할 수 없도록 ban 리스트를 갱신
if k >= (n + 1) // 2:
continue
ban[n - 1 - k] = True
else:
# break를 하지 않았다면 정답 문자열을 출력한다
print(*ans, sep='')
2024
맨 위로 이동 ↑2023
백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)
문제 링크 문제 링크
세그먼트 트리
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
벨만-포드 알고리즘
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
다익스트라 알고리즘
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...