99클럽 코테 스터디
논리적 사고가 필요한 문제이다. 논리적 사고로 중요한 결론을 내려놓고 나면, 코드를 짜는 것 자체는 간단하다.
1번 문제 Orderly Queue : https://leetcode.com/problems/orderly-queue/
출처 : LeetCode
1번 문제 Orderly Queue
풀이 접근
이 문제는 k=1일때와 아닐 때로 나뉜다.
먼저 k=1일 때는, 단순하게 맨앞 글자를 맨뒤로 보내는 작업만 가능하므로, s의 길이만큼의 경우의 수가 있고, 그 중 사전순으로 제일 빠른 단어를 반환하면 된다.
간단하지만, 이 작업 자체도 시간이나 메모리 면에서 최적화하려면 좀 더 고심이 필요할 것 같다. 내 경우에는 시간은 아주 빠르게 나왔지만 메모리는 하위권이다.
그렇다면, k가 2 이상일 때는 어떨까? 맨 앞의 k글자 중 한 글자를 떼서 맨 뒤로 보내는 작업을 무제한으로 하면, 얼마나 정렬할 수 있을까? 모든 경우의 수(26가지 알파벳이 최대 1000개 있으므로 중복순열로 최대 1000!/((38!)^14 * (39!)^12)가지인데, 아무튼 무진장 많다)를 다 만들 수 있나?
정답은...
k>1이면, s의 모든 애너그램(글자 구성이 같고 순서만 바뀐 단어)을 만들 수 있다. (왜?)
모든 애너그램을 만들 수 있다면, 수많은 애너그램을 다 만드는 게 아니고(다 만들면 영겁의 시간이 걸린다), 단어를 글자로 해체해서 알파벳순으로 정렬하고 그대로 다시 단어로 합쳐버리면 답은 오히려 아주 쉽게 만들 수 있다. 답이 그냥 aaaabbbbbbbccddddeffffggghhhii... 이런식으로 만들어지는 것이다.
그렇다면, s의 모든 애너그램을 만들 수 있다는 사실을 어떻게 알 수 있는가? 다 만들어 보면 영겁의 시간이 걸리는데, 안 만들어보고도 논리적으로 알 수 있을까?
인접한 두 알파벳의 순서만 서로 바꿔줄 수 있으면, 모든 알파벳을 정렬할 수 있다(Bubble Sort).
하지만 맨 앞 k개 중 하나만 맨 뒤로 보낼 수 있는데, 이것으로 임의의 인접한 두 알파벳의 순서를 어떻게 바꾸는가?
그 방법도 꽤 간단하다. 아래와 같은 단어가 있다고 하자.
'ㅡㅡㅡbaㅁㅁㅁㅁ' (ㅡ와 ㅁ는 아무 알파벳이다)
b와 a의 순서를 바꿔 ab로 만들고 싶다면?
- 'baㅁㅁㅁㅁㅡㅡㅡ' ba보다 앞에 있는 알파벳들을 맨 앞것부터 순서대로 다 맨 뒤로 옮긴다.
- 'bㅁㅁㅁㅁㅡㅡㅡa' 그러고 a를 b보다 먼저 맨 뒤로 보내고,
- 'ㅁㅁㅁㅁㅡㅡㅡab' 그 다음엔 b를 맨 뒤로 보내고,
- 'ㅡㅡㅡabㅁㅁㅁㅁ' 다시 ba보다 원래 뒤에 있던 알파벳들을 순서대로 맨 뒤로 옮긴다.
- 여기서, ㅡㅡㅡ와 ㅁㅁㅁㅁ의 순서는 유지된다.
즉, k가 2 이상이면, 임의의 두 인접한 알파벳의 순서를 서로 바꿀 수 있다. 작업 횟수는 무제한이므로, Bubble Sort 기법으로 단어 내의 모든 알파벳을 사전순으로 정렬할 수 있게 된다.
각 과정 자체는 그리 어렵지 않지만, 여러 단계를 거쳐서 생각해야 하고 각 단계에 대한 발상이 필요한 문제였다.
코드(Python3, Accepted, 28ms, 17.20MB)
TIL 중에 같은 얘기를 한 적 있는데, Python은 참 편리하다.
string slice도 쉽게 되고, list comprehension도 되고, string에 sorted도 쓸 수 있고(sort를 그냥 하면 안 되고, sorted(단어)로 list를 만들어서 다시 join해야 되긴 한다), string이 든 list에다 대고 냅다 min()함수 넣으면 사전순으로 제일 빠른 단어도 뱉어준다.
k가 2 이상일때는 그냥 단어를 사전순으로 정렬해서 만든 단어를 return한다.
k가 1일 때는 최대 100만 글자(1000글자짜리 단어 1000개)를 검사해야 돼서 약간 신경을 써야 하는데, ss는 단어 s를 두 번 붙인 것이고, 이 ss를 이용해서 리스트 컴프리헨션 한 번으로 쉽게 s를 로테이션으로 돌려서 만들수 있는 단어들을 만들 수 있다. 그리고 이 중 제일 작은(=사전순으로 빠른) 단어를 return하면 된다.
class Solution:
def orderlyQueue(self, s: str, k: int) -> str:
if k > 1:
return ''.join(sorted(s))
n = len(s)
ss = s + s
s_rotation = [ss[i:i+n] for i in range(n)]
return min(s_rotation)