https://school.programmers.co.kr/learn/courses/30/lessons/77886
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
110 옮기기
문제 설명
0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.
x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.
예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 됩니다. 뽑았던 "110"을 x의 맨 앞에 다시 삽입하면 x = "11010" 이 됩니다.
변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
1 ≤ s의 길이 ≤ 1,000,000
1 ≤ s의 각 원소 길이 ≤ 1,000,000
1 ≤ s의 모든 원소의 길이의 합 ≤ 1,000,000
입출력 예
s
["1110","100111100","0111111010"]
result
["1101","100110110","0110110111"]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
from collections import deque
def solution(s):
answer = []
# 각 문자열을 순회하며 변형
for cur in s:
q = deque() # 문자열 처리를 위한 deque
zcnt = 0 # 0의 개수
cnt = 0 # "110"이 삽입된 개수
# 문자열 순회
for i in range(len(cur)):
# "110" 추출
if len(q) > 1 and cur[i] == '0' and q[-2] == '1' and q[-1] == '1':
q.pop()
q.pop()
cnt += 1
continue
# 0 개수 계산
if cur[i] == '0':
zcnt += 1
# 문자열에 추가
q.append(cur[i])
# 변형된 문자열 생성
new_s = ""
while q:
# 0이 없으면서 "110"이 존재
if not zcnt and cnt:
new_s += "110" * cnt
cnt = 0
# 0이 있는 경우
if q[0] == '0':
zcnt -= 1
new_s += q.popleft()
# 남은 "110"이 있는 경우
if cnt:
new_s += "110" * cnt
answer.append(new_s)
return answer
|
cs |
풀이방법
0뒤에 110을 넣는게 유리하다 그래서 110을 모두 추출후 0이 있으면 그뒤에 넣기 아니면 그냥 앞에 넣기 왜냐면
0이 사전적으로 앞서기 때문
'프로그래머스' 카테고리의 다른 글
| [프로그래머스] 광물 캐기 - Python(파이썬) 풀이 (0) | 2023.03.24 |
|---|---|
| [프로그래머스] 리코쳇 로봇 - Python(파이썬) 풀이 (0) | 2023.03.24 |
| [C++] 프로그래머스 월간코드챌린지 스타 수열 level 3 (0) | 2020.11.22 |