출제자: 테스
- 출제 이유
- 다양한 풀이가 나올 수 있는 문제를 내고 싶었다.
- Time complexity: O(n)
- Space complexity: O(1)
처음에 문제를 접했을 때, 딱 떠올랐던 컨셉이 오른쪽으로 원패스로 진행하면서 CPoint 에서 다음 CPoint의 사이 값들만 갱신해주면 된다고 생각했다. 시작하고 나서 첫 CPoint가 나오는 지점까지 기억했다가 해결하기, 새로운 CPoint나오면 이전 값이랑 현재 인덱스 사이에 값들 중에 민 값을 찾아서 해결했다.
최악은 2n 최선은 n이라 일반적인 2n보다 때에 따라 나을 수도 있지만 코드가 복잡하고 한눈에 이해하기 어려운 부분이 아쉬웠다
- Time complexity: O(n)
- Space complexity: O(1)
- 음 양옆에 타깃이 어딨는지를 비교해서 더 작은 값을 알아야하니까 어떻게 해야 할까.. 고민하다 보니 그냥 왼쪽으로 한번, 오른쪽으로 한번씩 iterate하면서 더 작은 값을 넣으면 되겠다는 생각이 들었다.
- 처음엔 왼쪽 오른쪽 iteration한 값들을 따로 array에 저장한 후 최종적으로 더 작은 값으로 합쳐서 return해야할까 싶었는데 생각해보니 그냥 하나의 array에 값을 넣을 때 min 함수에 넣어서 하면 되겠구나 싶어서 따로 공간을 더 쓰지도 않게 되었다.
- 테쓰가 가져온 솔루션도 이와 같은 방식으로 하였다 하니 괜찮게 푼듯 ^.^
class Solution(object):
def shortestToChar(self, S, C):
"""
:type S: str
:type C: str
:rtype: List[int]
"""
forw=[]
cnt=0
for i in range(len(S)):
if S[i]!=C:
forw.append(cnt)
cnt+=1
else:
forw.append(-1)
cnt=0
back=[]
cnt=0
for i in range(len(S)-1, -1, -1):
if S[i]!=C:
back.append(cnt)
cnt+=1
else:
back.append(-1)
cnt=0
ans1=[]
cnt=10000
for f in range(len(forw)-1, -1, -1):
if forw[f]<0:
ans1.append(0)
cnt=0
else:
cnt+=1
ans1.append(cnt)
ans2=[]
cnt=10000
for b in range(len(back)-1, -1, -1):
if back[b]<0:
ans2.append(0)
cnt=0
else:
cnt+=1
ans2.append(cnt)
return [min(list(reversed(ans1))[i], ans2[i]) for i in range(len(ans1))]- Time complexity : O(n)
- Space complexity : O(n)
- 돌아가긴 돌아가지만 풀이가 매우 길고 복잡하다...
- 쓸데없는 부분이 많다. ans1 과 ans2 를 정리하는 코드에서 결국 target 이 되는 char 만 찾고, forward backward 에서 적었던 숫자들은 활용하지 않기때문에 사실상 forward backward 생성 과정은 필요가 없다.
- 위의 코드에서 redundant 한 과정들을 제거하고, min 을 backward loop 내에서 미리 구하는 방식을 취하면 아래와 같이 구할 수 있다.
class Solution(object):
def shortestToChar(self, S, C):
"""
:type S: str
:type C: str
:rtype: List[int]
"""
cnt=10000
forward=[]
for i in range(len(S)):
if S[i]==C:
cnt=0
else:
cnt+=1
forward.append(cnt)
cnt=10000
ans=[]
for i in range(len(S)-1, -1, -1):
if S[i]==C:
cnt=0
else:
cnt+=1
ans.append(min(forward[i], cnt))
return list(reversed(ans))- 코드작성 전에 풀이과정을 다시한번 생각해보고 쓸데없는 과정은 없는지 잘 확인할 필요가 있을 것 같다.
- Time complexity: O(n^2)
- Space complexity: O(n)
- 시간 안에 더 나은 방법을 생각해내지 못 해서 Brute Force에 가깝게 풀었다. 돌아가긴 하지만 좋은 점수를 얻긴 힘들 풀이이다. 자료구조를 거꾸로 순회한다는 생각을 잘 하지 못 하는 것 같다. 뭔가 틀에 갇혀있는 것 같은 느낌이다. 다양한 유형의 문제를 많이 풀어봐야겠다.
- 처음엔 Latte의 풀이처럼 인덱스를 세밀하게 다뤄 최적화하는 방법을 처음에 고민했는데 실패할 것 같아 풀이로 옮기지 못 했다. 이 부분은 많은 연습이 필요할 것 같다.
// 수정된 풀이
public int[] shortestToChar(String S, char C) {
int[] answer = new int[S.length()];
int currentCIndex = -1;
for (int i = 0; i < S.length(); i++) {
if (S.charAt(i) == C) {
currentCIndex = i;
answer[i] = 0;
} else {
if (currentCIndex != -1) {
answer[i] = i - currentCIndex;
} else {
answer[i] = Integer.MAX_VALUE;
}
}
}
currentCIndex = -1;
for (int i = S.length() - 1; i >= 0; i--) {
if (S.charAt(i) == C) {
currentCIndex = i;
} else {
if (currentCIndex != -1) {
answer[i] = Math.min(answer[i], currentCIndex - i);
}
}
}
return answer;
}
class Solution(object):
def shortestToChar(self, S, C):
prev = float('-inf') # 1e9 보다 빠르다.
ans = []
for i, x in enumerate(S):
if x == C:
prev = i
ans += [i - prev] #
prev = float('inf') # 뒤에서 C가 없는 경우를 대비해서 inf로 해야한다.
for i in range(len(S) - 1, -1, -1):
if S[i] == C:
prev = i
ans[i] = min(ans[i], prev - i)
return ans- Time complexity: O(n)
- Space complexity: O(1)
- 이 문제를 풀면서 python 에서는 append보다 그리고 1e9로 설정하는거보다 += [] 와 float('inf')로 대체하는게 시간복잡도면에서 다르다는 것을 알게되었다.