23.04.05 파이썬 코딩 퀴즈#209 110 옮기기(프로그래머스 스쿨)

이번 문제는 110 옮기기 이다.

0과 1로만 구성된 문자열 x 에서 '110'을 뽑아 임의의 위치에 다시 삽입한다. 이때 사전순으로 가장 앞에 오는 문자열을 배열에 담아 return 해야 한다.

입출력 예 를 보면서 구체적으로 어떻게 접근해야 할지 고민해 보자.

먼저 s[0] '1110' 이다.

110을 뽑고나면 1이 남는다. 그리고 1의 앞에 110을 붙이면 1101 이다. 문자열 '1101'은 '1110'보다 사전순으로 앞이다.

다음 s[1] 은 '100111100' 이다. 해당 문자열에서 110은 하나만 존재한다.

110을 뽑고나면 '100110'이다. 이제 문자열의 삽입 위치를 찾아야 한다.

사전적으로 먼저 나와야 하기에 0보다 앞에는 삽입할 수 없다. 앞쪽에 100을 제외하고 그 뒤로부터 하나씩 삽입해 보면

'100110110', '100111010','10011110','110110110' 4개의 위치에 삽입 가능하다.

이 중 사전순으로 가장 앞에 오는 문자열은 '100110110' 이다. 다시 110을 빼서 삽입 가능하지만, '100110110' 보다 사전순으로 앞에 오는 단어를 만들 수는 없다.

s[2]는 위 그림을 통해 이해해야 한다. 처음 110을 빼서 제일 앞의 0 뒤에 붙여 0110111110 을 만든다.

그 다음 제일 마지막의 110을 때어 2번째 0 뒤에 붙여준다.

 

예제를 통해 발견한 규칙은 다음과 같다.

1. '110'을 추출하고 남은 문자열은 붙여준다

2. '0'과 '1'이 존재한다면 그 사이에 '110'을 삽입한다.

3. 새롭게 완성된 문자열에 110이 존재하는지 확인하고, 2번 과정을 반복한다. 단 이미 삽입된 위치는 건너띈다.

4. 3번 과정을 반복한다.

 

이때 2번 규칙에 약간의 의문이 생긴다. 왜 굳이 '0'과 '1'사이에 넣어야 할까?

다른 예를 들어 살펴보자

 

전달받은 s의 요소가 '0011010' 이라고 가정해보자.

먼저 '110'을 추출하면 '0010'이 남는다. 사전순으로 먼저 위치하기 위한 조건을 알아보자.

위의 규칙2번대로 0과 1 사이에 110을 넣으면 '0011010'이 된다. 변화가 없다. 그렇다면 사전순으로 먼저오는 문자열은 없다는 의미일까?

다시 '110'을 추출하여 이번엔 남은 문자열의 마지막 '0'에 넣어보자. '0010110'이 된다. 

'0010110'은 '0011010'보다 사전순으로 앞에 온다. 그 이유는 '0010'이 '0011'보다 앞서기 때문이다.

 

다시 규칙을 만들어보자.

1. '110'을 추출하고 남은 문자열은 붙여준다

2. 남은 문자열에서 제일 마지막'0'을 찾아 그 뒤에 추출한 '110'을 연속하여 붙여준다.

3. 새롭게 생성된 문자열을 다시 확인하고 '110'을 모두 추출하고 2번 과정을 반복한다.

4. 새롭게 생성된 문자열과 이전 문자열이 같다면, 해당 문자열을 answer 에 추가하고 종료한다.

 

이제 이 규칙을 이용하여 코드를 작성해 보자.

크게 코드 자체는 어렵지 않다. 

다만 해당 코드는 시간제한에 걸린다.

이래저래 머리를 굴려봐도... 위 코드를 가지곤 시간 초과를 해결할 방법이 생각나진 않는다.

어쩔 수 없이 다른 사람의 풀이를 참고해야 했다....(이놈의 비전공자의 머리란...)

 

방법은 의외로 간단했다. 바로 stack 을 이용하여, 해당 문자열을 쌓아두고, 위와 동일한 방법으로 문자열을 재구성해 주어야 한다.

그렇게 다시 작성한 코드

먼저 각 요소별로 stack[]에 분리하여 저장하게 되는데 이때 '1','1','0' 이 나오면 제거하고 cnt 값을 1 증가 시켜 준다.

그렇게 쌓인 stack과 cnt 를 이용하여 문자열을 다시 temp에 역순으로 넣어주게 된다.

먼저 stack을 확인하고, '1' 인 경우라면 먼저 넣어준다. (역순이기 때문에 끝에서 부터 쌓인다)

그 다음 0 이 나온 순간 break로 해당 while문을 탈출한다.

그 다음은 '110'을 temp에 역순으로 넣어준다.

그리고 다시 stack에 남은 요소들을 역순으로 넣어주면 된다.

그렇게 완성된 temp를 answer에 다시 역정렬하여 넣어주면 완성...

 

전체적으로 시간초과였던 마지막 4개의 테케를 제외하고는 처음 코드가 더 빨랐다. 하지만 그 길이가 길어질수록 아래 코드가 더 빨랐다.

시간복잡도에 대해 좀 더 공부해 봐야 알겠지만, 상황에 맞는 코드구현이 가장 우선이다.