•
문제 링크 : leetcode.com
•
문제 설명 : I / D 구성된 문자열이 주어진다. 해당 문자열을 사용하여, 조건에 맞는 순열이 담긴 리스트를 반환하면 된다.
•
풀이 방법
◦
문제가 간단해보였지만, 번역으로는 이해가 안되어서 문제에 대한 설명만 찾아보았다.
▪
s[0] == I 이면 arr[0] < arr[1] 다음 원소보다 작아야 합니다.
▪
s[1] == D 이면 arr[1] > arr[2] 다음 원소보다 커야 합니다.
▪
위 내용을 보니 무슨 문제인지 이해가 가서 바로 풀어보았다.
•
시간복잡도 :
•
성공 코드
class Solution:
def diStringMatch(self, s: str) -> List[int]:
max_cursor = len(s)
min_cursor = 0
result = []
# 문자에 따라 min_cursor, max_cursor를 조절하면서 결과를 만든다.
# 마지막 문자도 처리하기 위해 s + s[-1]을 사용한다.
for ch in (s + s[-1]):
# 다음 수가 더 클 수 있도록 넣을 수 있는 가장 작은 수를 넣는다.
if ch == 'I':
result.append(min_cursor)
min_cursor += 1
# 다음 수가 더 작을 수 있도록 넣을 수 있는 가장 큰 수를 넣는다.
elif ch == 'D':
result.append(max_cursor)
max_cursor -= 1
return result
Python
복사