강의로 돌아가기
접근 방법입니다
[Only One Max]
핵심은 끝까지 남기려는 풍선을 기준으로 좌,우 구간의 최소값을 구했을때(leftMin, rightMin),
터트리려는 풍선의 값은 두 최소값 보다 크지 않아야합니다.
한번은 작은 풍선을 터트릴 수 있기 때문에 터트리려는 풍선이
좌,우 최소값중 하나 보다는 클 수 있어도, 둘 보다 커버리면 남길 수 없습니다.
Only one max = 큰 수는 하나 까지만 허용
좌에서 우로 최소값을 갱신하며 배열에 넣고, 우에서 좌로 동일하게 해주고
마지막에 두 최소값 보다 크지않나 보면서 확인해줍니다. 그래서 O(3n)의 방법으로 푸는 방법입니다.
나아가서 두 최소값 중 큰것보다 작기만 하면 되기 때문에 O(n)까지 줄일 수 있습니다.
-
터뜨리려는 풍선이 아니라 남기려는 풍선 아닌가요?
허정현―2020.10.22 22:30
-
3n이 아니라 n으로 푸는 것에 대해서 좀 더 자세한 설명을 들을 수 있을까요?
허정현―2020.10.22 22:55
-
감사합니다 수정했습니다. 예로 [5, 7, 1 ,8, 9] leftMin=5이고 rightMin=9로 시작합니다. rightMin이 leftMin보다 크므로 9 전값인 8과 9를 비교합니다. 8은 9보다 작으므로 무조건 끝까지 남을 수 있고, 동시에 오른쪽 탐색한 구간의 최소값(rightMin)이 됩니다. 더 진행하면 그 다음 5와 8을 비교하고 8이 더 크므로 8과 전값인 1을 비교합니다. 1이 더 작으므로 1은 끝까지 남을 수 있고 오른쪽구간의 최소값은 1이됩니다. -> 5 와 1비교. 5가 크므로 5와 5의 다음 값인 7비교 -> 이 때 7 > 5인데 이는 최소값들 중 큰값보다 큰값이기 때문에 절대 남길 수 없게 됩니다. 말이 길어졌는데 결국 max(leftMin, rightMin) 값과 그 옆에 값을 비교하며 최소값을 갱신해줍니다.
Jay-lol―2020.10.23 02:44
-
이 문제는 구현 문제인가요? 알고리즘 분류가 어떻게 될지 궁금합니다.
이제운―2020.10.29 23:08
-
투 포인터로 볼 수 있겠네요.. 저는 잘 이해가 안되서.. 세그먼트 트리로 풀었습니다.
박재병―2021.04.09 17:54
-
감사합니당!!
lucyy―2021.06.22 10:24
-
와,,,,진짜 감사합니다!!!!!!!!
hongsub95―2021.08.25 21:00
2 개의 답변
힌트 감사합니다. 뭔가 갈피를 못잡았는데 덕분에 잡을 수 있었습니다.
가르침을 바탕으로.. 자바 코드 올립니다.
class Solution {
public int solution(int[] a) {
int answer = 1;
int n = a.length;
int l = 0, r = n-1;
int lMin = a[l];
int rMin = a[r];
while (l < r) {
if (lMin > rMin) {
l++;
if (a[l] < lMin) {
answer++;
} else { //a[l] > lMin && a[l] > rMin
//nothing to do
}
lMin = Math.min(lMin, a[l]);
} else { //lMin < rMin
r--;
if (a[r] < rMin) {
answer++;
} else { //a[r] > rMin && a[r] > lMin
//nothing to do
}
rMin = Math.min(rMin, a[r]);
}
}
return answer;
}
}
답변 쓰기