보석 쇼핑
링크: https://school.programmers.co.kr/learn/courses/30/lessons/67258#qna
문제분류 : 투 포인터
난이도 : Level 3
결과: 실패
회고
처음부터 투 포인터를 염두에 두고 풀었으나 실패했다...!
투포인터라고 생각한 이유는 너무 간단하다. 완전탐색(O(N^2))으로는 절대 효율성 테스트를 통과 못한다.
답을 찾는데 최적화 알고리즘이 필요하다는 결론을 내렸다.
답으로 원하는 값은 배열의 연속된 인덱스에 관한 것이었기 때문에
선형탐색이 필요하다고 생각했고 여기서 투포인터가 알고리즘이 떠올랐다.
내 나름대로 머리를 잘 써서 간단하게 풀었다고 생각했으나,
내가 푼 방식으로는 놓치는 케이스들이 있었다.
하지만, 이 문제를 틀린 덕분에 실수할만한 포인트를 점검해서 다행이라 생각한다.
이거 완전 럭키보석쇼핑이잖어~ㅋ
내 풀이
문제풀이 아이디어
내가 생각한 방법은 다음과 같다.
1. gems와 Set을 가지고 보석의 종류를 파악한다.
2. gems 배열과 gemType 집합을 가지고 endIdx의 값을 구한다.
이 endIdx는 gems 배열에서 최초로 모든 종류의 보석이 포함되는 인덱스이다.
3. gemMap을 구한다.
gemMap은 gems의 0번부터 endIdx까지 포함된 보석들의 개수를 표현한 맵이다.
이 Map을 가지고 startIdx의 위치를 구할 것이다.
4. startIdx 값을 구한다. for문에서 i를 점점 증가시킨다.
i에 해당하는 gems의 값을 key로 하여 gemMap에서 count를 찾는다.
만일, 찾은 count의 개수에서 -1을 한 값이 0과 같다면,
모든 보석을 포함하지 않기 때문에 그 인덱스는 반드시 포함이 되어야 한다.
따라서 startIdx로 반환한다.
5. startIdx + 1, endIdx + 1을 배열로 만들어 답으로 반환한다.
틀린 이유
처음에는 틀린 이유가 이해가 안갔다. 분명 4개의 예제 케이스를 모두 만족시켰고,
나는 이 방법이 최초의 모든 보석을 포함하고 짧은 길이를 만족할 수 있을거라 생각했기 때문이다.
분명 모든 종류의 보석을 포함하는 인덱스를 찾을 수 있다.
하지만 안타깝게도... 내가 착각한 것이 있었다. 바로 최소 길이조건이다.
예를 들어보자.
위 문제의 첫 번째 예제케이스와 답은 아래와 같다.
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]
정답 : [2, 6] -> [3, 7]분명 내가 작성한 알고리즘으로는 위의 예제는 만족한다. 하지만 아래와 같이 예제를 조금만 수정해보자.
["DIA", "EMERALD", "SAPPHIRE", "DIA", "DIA", "RUBY", "EMERALD", "SAPPHIRE"]
정답 : [4, 7] -> [5, 8]위의 변형된 예제의 답은 [4, 7] (정답처리시 1씩 더한 [5, 8])이다.
하지만 내가 작성한 알고리즘으로는 [1, 5] (정답처리시 1씩 더한 [2, 6])가 나오게 된다.
왜 그런걸까?
최초로 모든 종류의 보석을 포함하는 범위는 [1, 5]이다.
물론 운 좋게 그 이후의 범위에서 모든 보석을 포함하는 배열이 나오고 그 길이가
최초로 등장한 배열보다 길다면 답은 [1, 5]가 맞겠지만,
위에서 변형한 예제의 경우에는 최초로 찾은 답보다 뒤에 나온 범위가 더 짧다.
처음 등장한 범위의 길이는 5이고 그 이후에 등장한 범위의 길이는 4이다.
따라서 길이가 더 짧은 [4, 7]가 되어야 한다...!
즉, 이런 조건이 붙어있을 경우에 모든 케이스를 체크해야 하는데
내가 섣불리 판단하여 틀린 것이다...ㅋㅠ
모범 풀이
문제풀이 아이디어
startIdx와 endIdx는 정답으로 사용할 범위의 값이다.
마찬가지로 몇 종류의 보석이 있는지 파악하기 위해 Set으로 보석의 종류를 만든다.
s와 e는 투 포인터 알고리즘을 위한 포인터들이다.
s는 startIdx 후보에 해당하는 앞쪽 포인터.
e는 endIdx 후보에 해당하는 뒷쪽 포인터이다.
gemCountMap은 s와 e사이에 존재하는 보석의 종류별 개수이다.
여기서 답을 판별하는 코드는 while문 안쪽에 해당한다.
s가 gems 배열의 끝에 도달하기 전까지 반복을 한다.
반복하면서 gemCountMap에 있는 key의 개수가 gemSet에 있는 key와 같은지 판별한다.
개수가 같다면 s와 e에 의해서 만들어진 범위 안에 모든 보석이 포함되었다는 것이다.
여기서 내가 놓친 포인트에 관한 코드가 있다...!
if (e - s < endIdx - startIdx)
즉, 현재 e와 s가 만들어낸 범위가 기존의 답이 될 수 있는 범위보다 짧은지 판별하는 코드이다.
그 아래쪽 코드는 투 포인터로 배열의 모든 범위를 판별하기 위해 처리하는 코드이다.
s의 크기를 늘리면 범위가 좁아진다.
즉, gemCountMap에서 특정 보석의 개수가 1개 빠지게 된다.
반대로 e를 늘리면 범위가 넓어져 특정 보석의 개수가 늘어난다.
이 작업은 gemCountMap에 모든 보석이 포함되지 않은 경우에 처리한다.
단 여기서 e가 gems.length - 1 보다 커지면 안되므로 주의한다.
두 if문에 모두 해당하지 않는 경우는 효율성을 위해 break해준다.
후기
투포인터라 쉬울 줄 알고 후딱 풀었다가 디버깅하는데 시간을 많이 소모했다.. ㅎㅎ;
알고리즘 문제를 풀 때 늘 유의해야하는 사항은 조건이다..!!
제발 예외사항을 가볍게 생각하지 말고 꼼꼼히 보도록 하자.
그리고 웬만하면 투포인터는 선형탐색이라 시간초과 안하니까
케이스 바이 케이스로 다 검사해보도록 하자.
