문제 : https://programmers.co.kr/learn/courses/30/lessons/77886
자세한 문제 구성은 위의 링크를 참조바란다.
Problem Point
x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.
문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.
간단히 말해서 문자열 안에서 110을 모두 뽑아내고 숫자를 최대한 크게 만드는 방향으로 만드는 것이 포인트 이다.
1 ≤ s의 길이 ≤ 1,000,000
풀이
맨 처음에 접근하였을때는 110을 뽑아내고 나서 그 뒤에 0과 앞에 11이 다시 만나서 뽑아내는 과정을 110을 찾지 못할때까지 반복하여 찾는 방향으로 생각하였다. 하지만 이런 방향은 O(N^2)이며 시간초과가 날 것이라고 생각하였다. 따라서 선형적인 방법으로 접근을 해야 했고 그 중 스택을 사용하여 O(N) 시간에 접근하는 방법을 생각해 냈다.
위의 사진을 보고 잠시 했갈렸다. 숫자를 최대한 크게 만들기 위해서는 11 앞에 110 이 와야 했지만 사진에서는 뒤로 가는 모습을 보여줬기 때문이다. 하지만 자세히 보면 110을 뒤로 옮긴 것이 아닌 11 앞에 보내도 같은 숫자임을 알 수 있다.
여기서 드는 생각이 왜 111이 아니고 11 앞에 와야 하냐고 생각 할수 있는데 11이 나올 수 있는 경우의 수가 110 과 111이기 때문에 적어도 11앞으로 옮기게 되면 숫자가 작아지는 경우는 없다. 따라서 숫자 11앞에 110을 넣는 방향으로 생각하였다.
위 사진은 예시에서 110을 제외한 나머지 숫자들이다. 이제 11이 있는 경우는 해결되었으나 문자 안에 자체가 110이 없는 경우에 대해서 생각해야 했고 list안에 1만 있는 경우에는 맨 앞에 붙이는 것과 0이 있는 경우에는 마지막 0뒤에 붙여야 했다. 따라서 코드를 보면 문자열을 역순으로 돌면서 마지막 0의 index값을 찾아 안에 삽입하는 방식으로 구현하였다.
최종풀이
def mv(temp):
stack = []
more = ['1', '1', '0']
cnt = 0
for i in temp:
if i == '0' and stack[-2:] == ['1', '1']:
cnt += 1
stack.pop()
stack.pop()
else:
stack.append(i)
cnt2 = 0
stack_len = len(stack)
answer = []
if cnt != 0:
for i in stack:
if i == '1' and cnt2+1 < stack_len and stack[cnt2+1] == '1':
answer = stack[:cnt2] + cnt*more + stack[cnt2:]
answer = "".join(answer)
break
cnt2 += 1
if not answer:
if '0' in stack:
cnt3 = 0
for i in stack[::-1]:
if i == '0':
answer = stack[:stack_len-cnt3] + \
cnt*more + stack[stack_len-cnt3:]
answer = "".join(answer)
break
cnt3 += 1
else:
answer = cnt*more+stack
answer = "".join(answer)
return answer
else:
return temp
def solution(s):
answer = [mv(i) for i in s]
return answer