[leetcode][821] - Shortest Distance to a Character

안녕하세요 Dibrary입니다.

 

이번에는 leetcode의 821번 문제를 정리하겠습니다.

c로 주어진 문자를 기준으로 좌우 거리마다 1씩 증가하되, c문자를 또 만나면 좌우가 대칭으로 숫자가 들어가야 합니다.

 

제일 먼저 든 생각은 이랬습니다.

1. c로 입력된 문자를 뽑아내어서 index를 찾는다.
2. 그 index 주위로 +-를 계산한다.

이렇게 하면 맨 앞부분, 맨 뒷부분은 해결이 되는데, 좌 우가 같은 경우는 도저히 해결이 안 되는 겁니다.

예를 들면, 아래 처럼 한 후에, index에 해당되는 값부터 다음 index까지를 - 해 나갈 생각이었죠,

근데 그러려면 5는 -4를 해야 하고, 4는 -2를 해야하고, 3은 -1을 해야하니까, 규칙성이 없네요?

이래서 이 문제를 풀려고 온갖 방법을 헤메고 다녔답니다. =_=

 

---

해법은 위에서 한 것과 비슷합니다.

1. 한 가지 방향으로 값 처리를 하고,
2. 그 반대 방향으로 다시 값 처리를 합니다.

 

네 우선 결과는 예시 코드와 똑같이 나오네요, 코드를 분석해보겠습니다.

 

잘 보면, 2가지 루프가 위치하고 있습니다.

이게 순서대로 '오른쪽 방향으로 값을 죄다 더해 나가기'를 한 후에
다시 '왼쪽 방향으로 값을 비교해 나가기'를 한 것입니다.

 

1. 왼쪽에서 오른쪽 방향으로 값을 더해 나가기

먼저 중간결과를 보면 초반에는 값들이 dist에서 +1, +2, +3된 값들이 들어가고, c와 같은 문자 위치에서 곧바로 0이 되는 것을 알 수 있습니다. 

dist가 0이 되고 난 이후부터는 0부터 +1, +2.. 이렇게 c로 넣은 문자를 만나기 전까지 계속 증가하죠.

여기까지가 오른쪽으로 값을 처리한 것이고,

 

2. 오른쪽에서 왼쪽 방향으로 값을 비교해 나가기

그 다음 루프에서 왼쪽으로 값을 비교해 나갑니다. for문에서 index는 역순으로 탐색하기 때문에 뒤에서부터 오죠.

여기서 min부분에서 dist값과 중간 결과의 값을 비교합니다.

예를 들면, [0, 1, 2, 3, 4, 0] 이 있을 때, 뒤에서 왼쪽으로 값을 더해 나갈때의 배열은 [0, 4, 3, 2, 1, 0] 이 됩니다.

앞(왼쪽)에서부터 같은 위치를 비교해보면,

1. 맨 처음은 0이 같으니까 패스, 
2. 두 번째는 1과 4중에 1이 작으니까 1을 남김
3. 세 번째는 2와 3중에 2가 작으니까 2를 남김
4. 네 번째는 3과 2중에 2가 작으니까 2를 남김
5. 다섯 번째는 4와 1중에 1이 작으니까 1을 남깁니다.

결국 [0, 1, 2, 2, 1, 0] 으로 완성되는 것이죠.

 

그러면 당연히? 중간 결과에서 무지 큰 값으로 나온 맨 앞의 값들도 똑같죠?

[1000000000,1000000001,1000000002, 0]은 [3,2,1,0]과 비교하게 되는데, 당연히 3,2,1이 작기 때문에

[3,2,1,0] 으로 앞부분이 나오는 것입니다.