링크

110 옮기기

난이도

  • 프로그래머스 난이도 3
    • 풀고나니 왜 어렵게 했나 생각함

문제요약

  • 1,0으로 이뤄진 문자열에서 110을 추출하여 최대한 낮은 숫자를 만들기
    • 사전순으로 앞 = 낮은 숫자
    • 1,0을 2진수로 생각하면 안됨

접근

  • 110제거후 110을 어디에 삽입할지 계산
    • 처음에 replace를 사용했다가 시간 초과로 stack을 이용
    • 110의 삽입 위치를 처음에 잘못 생각해서 오래 걸림
      • 110을 제거한 후, 제일 뒤쪽 0에 넣으면됨
  • 110 제거에 사용한 stack
    • replace를 사용하면 간단하게 110들을 제거할 수 있다.
      • 110 제거후에 다시 replace를 while를 통해 반복하여 재귀적으로 110을 제거 가능
      • 하지만 시간 초과가 나타난다.
    • 해결하는데 사용한 stack은 주어진 문자열을 한번 훑기만 하면 110을 지울 수 있다.

테스트케이스 추가

  • [“110”] - [“110”]
  • [“111111110000”] - [“110110110110”]
  • [“0000000111111111110”] - [“0000000110111111111”]
  • [“000000”] - [“000000”]
  • [“11111111”] - [“11111111”]
  • [“01000100011110”] - [“01000100011011”]
  • [“100010100000010000110”] - [“100010100000010000110”]

간단 알고리즘

  • 110 제거하기(stack)
    • stack변수 선언, 문자열로 저장하기 위해 stack = ""로 초기화
    • 1을 만났을때
      • stack에 추가
    • 0을 만났을때
      • stack의 개숫가 2보다 클경우 시작
      • stack의 뒤에서 두개의 요소가 1이면
        • stack 뒤의 요소 2개 삭제
      • 아니면 stack에 추가
    • 위의 과정을 거치면 문자열에서 모든 110이 제거가 된다.
  • 마지막 0 찾기 insertInde
    • stack의 요소를 한번 훑어서 마지막 0의 인덱스를 찾는다.
      • 만약 시간초과가 난다면 위의 110을 제거하기에서 stack에 0을 넣고나서 stack의 크기를 insertIndex로 저장한다.
  • 110 넣기
    • 110이 몇개 있는지 확인하기는 110 제거하기에서 stack 뒤의 요소 2개 삭제할때 count해주면 110의 갯수를 알 수 있다.
    • stack의 insertIndex위치에 110을 지워진 갯수만큼 추가하면 끝

후기

  • 왜인지 오래걸림
  • stack을 써야하는것은 replace를 안해야 한다는 것을 파악하고 나서 바로 생각났다.
  • 하지만 110을 어디다 넣어야 하는지 초반에 이상하게 생각해서 오래 걸림.
    • 0이 처음에 끝나는 지점, 010이 나오는 지점 등 잘못 생각하고 기본 실행했을때 테스트케이스만 고려했다
  • 테스트 케이스가 생각한거 처럼 다양하지 않아서 예외 찾느라 오래 걸림