https://leetcode.com/problems/longest-increasing-subsequence/
Given an integer array nums, return the length of the longest strictly increasing
subsequence.
배열에 존재하는 가장 긴 오름차순의 길이(문자가 연속하지 않아도 좋다)를 구하는 문제다
예시로 제공한 int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 }; 에서는
2, 3, 7, 101 순으로 4개가 가장 길다
이런식으로 구한다
가장 먼저 생각난 방법은
맨 앞인 10에서 시작하여
1바퀴 돌면서
10보다 큰 것들의 개수를 세서 저장하고
그 다음인 9에서 이걸 반복
이런식으로 2중 for문에서 선택정렬하듯이 풀면 되겠다
안쪽 for문이 끝났을 때 나온 길이와 전체 최댓값을 비교하여
큰것으로 갱신하면 될 것 같은데?
일단 작성해봤다
static public int LengthOfLIS(int[] nums)
{
//int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
//int[] nums = { 0, 1, 0, 3, 2, 3 };
// array에서 i번째에서 시작한 것의 가장 큰 길이 구하기
int max = 1;
int tempMax = 1;
int comp = 0; // 비교할 상수
for (int i = 0; i < nums.Length; i++)
{
comp = nums[i];
tempMax = 1; //
for (int j = i + 1; j < nums.Length; j++)
{
if (nums[j] > comp)
{
tempMax++;
comp = nums[j];
}
}
// 내부 for문 1회 순회하면 오름차순인 tempMax 길이가 정해진다
// max와 tempMax를 비교하여 큰 값의 승리
max = tempMax > max? tempMax: max;
}
return max;
}
이건 위의 예시는 통과하는데
아래의 예시를 통과하지 못한다
3에서 2로 작아질때 그냥 넘어가기때문에 0, 1, 3 일때 3으로 계산하지만
실제 최댓값은 0, 1, 2, 3 일때 4이기 때문이다
값이 무작정 커지기만 해서는 안된다
한번 지나간 후에도 뒤의 값에 영향을 줄 수 있어야 한다
3이 2를 만났을 때 지금은 3이 숫자도 크고, 3이 포함된 0, 1, 3의 길이인 3이 더 크지만
2가 포함된 0, 1, 2 뒤에 더 많은 오름차순이 나올 수 있는 가능성이 있기 때문에
3이 2와 만날 때 오름차순의 길이는 확정이 되면 안된다
최댓값은 배열의 마지막을 순회하는 순간에 정해져야 한다
첫번째 생각: 최댓값을 이용한다
오름차순으로 나오는 문자열의 최댓값은 최대 길이를 결정하는 중요한 요소이다
반대로 뒤에서부터 내림차순으로 세면 어떨까?
아쉽게도 뒤에서부터 세면 0, 1로 가는 증가구간이 있다
이런 방식으로는 힘들겠다
이때
84번과 733에서 스택에 저장을 했던 사실이 생각났다
이번에도 스택을 이용하면 되지 않을까?
한번 지나가더라도 값이 저장되어있으니 나중에 빼서 사용할 수 있다
두번째 생각: 스택을 이용한다
push조건과 pop 조건을 생각하자
최종 남아있는 개수를 가장 긴 길이라고 하면 되지 않을까?
맨 처음 시작하는 0을 push
1은 0보다 크니까 push (top은 1이다)
0은 top보다 작으니까
지금 넣을 수와 이전에 넣은 것들 중 지금 넣을 수보다 "큰" 것들의 "index"를 pop하고, 그 개수를 기록한다
(84, 733번처럼 index를 push한다)
그런데 이미 들어 있는 0과 같은수니까 push를 못하는데
그러면 크거나 같은수를 모두 pop하나? 그런데 같은수를 pop하고 다시 같은수를 넣어봤자 의미가 없다
그래서 생각했다
pop의 조건: 스택에 있는 숫자가 현재 인덱스의 숫자보다 큰 숫자인 동시에, pop을 하고 empty가 되면 안된다
그러면
0, 1이 저장되어있다가 0을 만나도 pop하지 않을 것이고,
0 , 1, 3이 저장되어 있다가 2를 만나면 2보다 큰 3을 pop하더라도
그 다음 현재 인덱스를 push하면
0, 1, 2가 되어 그 뒤에 만나는 3을 저장해서
문자열이 끝났거나, 아니면 그것보다 더 작은 수를 만나서 pop할 때
스택안의 개수를 봐서 기존의 개수 max값과 비교할 수 있다
이런식으로 하면 될 것같은데
3은 top보다 크니까 push
그래서 한번 만들었다
테스트해보자
static public int LengthOfLIS(int[] nums)
{
//int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
//int[] nums = { 0, 1, 0, 3, 2, 3 };
Stack<int> idxStack = new Stack<int>();
int max = 0;
int tmpMax = 0;
for (int i = 0; i < nums.Length; i++)
{
while (idxStack.Count > 0 && nums[idxStack.Peek()] > nums[i])
{
max = idxStack.Count; // 뽑기 전 최대 개수를 저장
idxStack.Pop();
}
idxStack.Push(i);
tmpMax = idxStack.Count;
max = tmpMax > max ? tmpMax : max;
}
return max;
}
하지만 문제가 있었다
0, 1 까지 하면 스택에는 0, 1이 들어있다
하지만 다음에 0을 만나면 1을 pop해버린다
1의 pop을 막아야 하는데
이를 위해 최솟값을 저장했다
pop조건: 스택이 비어있지 않고, 스택의 top보다 작은 값이며, 스택에 저장된 최솟값보다는 커야한다
그러면 0, 1 뒤에 0을 뺄 수 없으니 지나가고 3 추가한 뒤에 2를 만나면 3을 빼고 2, 3, 추가해서 0, 1, 2, 3 되니까
그럴싸 한 것 같다
하지만 이런 극단적인 예시를 생각해봤을 때 스택은 안된다는걸 알게 되었다
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5, 11, 12
답은 당연하게도 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 해서 12가 되겠지만
위의 스택으로 하면 10 뒤에 5를 만나면, 5가 남을때까지 뽑고 push를 하므로
1, 2, 3, 4, 5, 5 가 되어버린다
그 뒤에 11, 12가 들어와도 길이 12에는 한참 못미친다
스택이 아닌 다른 방법이 필요하다
뽑지 않고, 원래 상태를 유지하면서 확인할 수 있어야 한다
갑자기 수학 공부할 때 중복조합을 조합으로 바꾸는 방법이 생각났다
예를 들어 0부터 4 사이에서 중복을 허락하여 순서 상관없이 4개를 뽑는 방법이다
4H4 였지만 이건 7C4와 같았다
모든 경우를 나열하면 0, 0, 0, 0 부터 4, 4, 4, 4 인데
각 자리에 +0, +1, +2, +3 으로
모든 경우를 "오름차순"으로 다르게 만들 수 있었다
이것을 응용하면 원래 있는 것들을 뽑지 않고도 가능하지 않을까??
세번째 생각:
for문에서 1번 순회하며, 뒤로 가면서 증가하는 모양? 을 만든다?
10에서 시작하는 최대 길이는 2
9에서 시작하는 최대 길이는 2
2에서 시작하는 최대 길이는 4
5에서 시작하는 최대 길이는 3
3에서 시작하는 최대 길이는 3
7에서 시작하는 최대 길이는 2
101에서 시작하는 최대 길이는 1
18에서 시작하는 최대 길이는 1
이걸 이용해서 오름차순을 만들 수 있다면 좋을 것 같다
오름차순이면 좋겠는데...
현재 for문이 오른쪽으로 순회를 하니까
순회결과 오름차순이 되면서, 최대길이를 표현할 수 있으면 좋겠다
2중 for문으로 만들어서
i = 0일 때 (값이 10일 때)
내부의 for문이 한바퀴 돌면
10에서 시작하는 최대 길이가 확정이 되는 방식을 찾으면 되지 않을까
생각이 잘 안난다
...
...
...
10으로 끝나는걸 구하면 어떨까?
10으로 끝나는걸 구현한 다음, 그 뒤에 10보다 큰걸로 구현한다면
앞에서 10으로 끝나는것 뒤에 다른걸 추가하는 방식으로 하면 되지 않을까?
한번 나열해보자
10으로 끝나는 것의 길이는 1
9로 끝나는 것의 길이는 1
2로 끝나는 것의 길이는 1
5로 끝나는 것의 길이는 2 인데, 2로 끝나는 것의 길이 +1로 표현할 수 있다
3으로 끝나는 것의 길이는 2인데, 2로 끝나는 것의 길이 +1로 표현 가능
7로 끝나는 것의 길이는 3인데, 2로 끝나는 것의 길이 +2, 3으로 끝나는 것의 길이 +1, 5로 끝나는 것의 길이 +1로 표현 가능
101로 끝나는 것의 길이는 4인데, 같은 방식으로라면 7로 끝나는 것의 길이 +1로 표현 가능
18로 끝나는 것의 길이는 4인데, 7로 끝나는 것의 길이 +1로 표현 가능
이걸 내부 for문을 돌면서 결정하면 될 것 같다
i가 가장 큰 숫자가 되어야하니, i보다 작은 숫자만큼 순회해야 한다
그러면 결과는
1
1
1
2
2
3
4
4
가 되어야한다
static public int LengthOfLIS(int[] nums)
{
//int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 }; // 2, 3, 7, 101 또는 2, 3, 7, 18
//int[] nums = { 0, 1, 0, 3, 2, 3 }; // 0, 1, 2, 3
// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5, 11, 12
int[] assendingLength = new int[nums.Length]; // 기본값 0 초기화
int max = -1; // i보다 작은 nums의 인덱스 중에서 nums의 값이 최대가 되는 인덱스
int answer = 0; // assendingLength[i] 중에서 최댓값
for (int i = 0; i < nums.Length; i++)
{
max = -1; // 초기값은 -1
assendingLength[i] = 1; // 자기자신 1개는 포함
// i번째의 수가 마지막이다
for (int j = 0; j < i; j++)
{
// 0~i-1 까지 순회하며 i보다 작은 숫자들 오름차순으로 표시
// i 보다는 작아야 한다
if (nums[j] < nums[i])
{
// max의 갱신 문제
if (max == -1 || assendingLength[max] < assendingLength[j])
{
max = j;
}
}
}
// 그런데.. 더하면 안될 때가 있다
// 끝나면 nums[i]보다 작은 nums[j]가 최대가 되게 하는 j가 max에 저장
// 유효한 max가 존재할 때만 더하기
if (max != -1 && (nums[max] < nums[i]))
{
assendingLength[i] += assendingLength[max];
}
answer = answer > assendingLength[i] ? answer : assendingLength[i];
}
return answer;
}
중요한건
if (max == -1 || assendingLength[max] < assendingLength[j])
nums배열의 값의 크기가 큰쪽이 아니라
해당 인덱스까지의 최대길이가 긴쪽을 선택해야 한다는거
비교조건 찾기가 힘들었다
difficulty: ★★★
'코딩테스트 > LeetCode' 카테고리의 다른 글
| Flood Fill : 문제 번호 733 (C#) (0) | 2025.02.14 |
|---|---|
| Largest Rectangle in Histogram : 문제 번호 84 (C#) (0) | 2025.01.30 |