문제 설명.
s : string과 k : int가 주어진다.(1 <= len(s) <= 1000)
앞에서 s에서 앞에서 k개 까지의 글자중 하나를 뒤로 보낼 수 있는 연산을 할 수 있을 때 사전적으로 가장 앞에 들어갈 수 있는 단어를 찾는 문제.
example.(연산)
s = 'bcba', k = 2'이라 가정해보자.
이경우 앞의 3글자 'bbc'중 하나를 뒤로 보낼 수 있다.
그리고 한 번 연산했을 때 나올 수 있는 결과는
- 1번째 글자를 뒤로 보내서
'cbab', - 혹은 2번째 글자를 뒤로 보내서
'bbac'가 만들어질 수 있다.
문제 풀이 및 설명.
처음 문제를 보았을 때는 사전적으로 맨 뒤에 있는 글자를 보내면 되겠거니.. 하면서 함수를 짜고, 몇개의 예시와 그 결과를 생각해보았다.
그러나 이 방법은 바로 위 example과 같은 케이스로 인해 매우 잘못된 결과를 뽑아낼 수 밖에 없더라..
때문에 짧게 발상을 돌려볼 수 밖에 없었는데 앞의 k글자가 아닌 그 뒤의 글자의 순서를 바꿀 수 있는 방법은 무엇이 있을까?에 대한 생각이었다.
결과적으로 k != 1이라는 조건에서 항상 뒤의 글자를 바꿀 수 있겠다는 결론이 나오게 되었고, 그걸 그대로 코드로 구현하게 되었다.
- 간단히 바꾸고 싶은 글자열의 첫 글자가 첫 번째에 올 때까지 계속해서 맨 앞의 글자를 뒤로 보내주면 된다.
그리고 k == 1 케이스에 대해서는 어떤 좋은 방법이 떠오르진 않아서 brute force적인 코드를 사용해서 풀었다.
풀이 코드.
class Solution:
def orderlyQueue(self, s: str, k: int) -> str:
if len(s) == 1:
return s
elif k != 1:
return ''.join(sorted(s))
nex = s[1:]+s[0]
mini = s
while nex != s:
if nex<mini:
mini = nex
nex = nex[1:]+nex[0]
return mini잡담.
-
cap이론을 공부하다가 pacelc이론까지 같이 공부하게 되었고, 다시 여기서 다루는 P(partition)에 대해 공부하고 있다가 오랜만에 글을 쓰게 되었다. 스터디 끝나고 프로젝트를 진행중이다 보니 블로그에 의무적으로 글을 쓰는 것이 없어서 아무래도 죽 파고 있게 된다. 혼자 직접 하는 프로젝트에서도 많은 것을 얻어가는 것 같다.
-
오랜만에 무지성으로 달려들면 피를 볼 수 밖에 없을 것 같은, 재미있는 문제였다.
