문제 사이트

300. Longest Increasing Subsequence

설명

LeetCode는 문제가 영어로 되어있어서 구글 번역기를 돌려봤다.

설명에는 -10^4 ~ 10^4까지의 정수 배열이 주어질때 엄격하게(?) 증가하는 가장 긴 길이를 반환합니다. 라고 적혀있어서 이게 무슨 문제인지 이해를 못해서 구글링을 해보았다.

최장 증가 부분 수열 - (자세한 설명이 있어 이보다 자세한 내용을 원하면 읽길 추천한다.)
그랬더니 떡 나무위키가 나오는게 아닌가!
들어가서 읽어보자

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.

그니깐 쉽게말해 주어진 수열에서 내가 임의로 제거하여 만든 가장 긴 크기의 오름차순 수열이라는 말이다.

풀이

방법

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

List<int> list = new List<int>();
list.Add(-10001);

list에 -10001을 추가한 이유는 수열안의 값이-10^4 ~ 10^4까지의 정수이기 때문이다.

현재 상황이다

이제 nums의 값을 list에 들어있는 가장 큰 값과 비교하여 크면 추가를, list의 값과 값의 사이에 있는 값이면 변경해서 가장 큰 길이의 수열을 만들어야 된다.

for(int i = 1; i < nums.Length +1; i++)
{
	if(nums[i-1] > list.Last())
	{
		list.Add(nums[i-1]);
	}
    
    ~~~~
    
}

여기서 들어온 값이 리스트의 마지막(왜냐하면 리스트는 정렬되어 있는 상태이기에 마지막 값이 가장 큰 값이기 때문이다) 값과 비교하여 큰 값이면 추가를 해야한다.

여기서 마지막값인 -10001 보다 크기 때문에 값을 추가 해주었다.

하지만 가장 큰 값에 비해 작은 값이면 리스트 안에 들어있는 값과 비교하여 위치를 선정해서 값을 넣어줘야된다.

for(int i = 1; i < nums.Length +1; i++)
{
	if(nums[i-1] > list.Last())
	{
		list.Add(nums[i-1]);
	}
    else
    {
    	for(int j = 1; j < list.Count; j++)
        {
			if (nums[i - 1] < list[j] && nums[i - 1] > list[j-1])
			{
				list[j] = nums[i - 1];
            }
		}
	}
}

이전 값보다 크면서 현재 값보다는 작은 값은 현재 값을 대신해서 들어간다.

여기서 9는 10보다는 작지만 -10001보다는 크기 때문에 10의 값을 9로 변경해 주었다.

다음 값들도 이와 같은 형태로 진행해주면 된다.

코드

public class Solution {
    public int LengthOfLIS(int[] nums) {
        List<int> list = new List<int>();
        list.Add(-10001);

        for(int i = 1; i < nums.Length +1; i++)
        {
            if(nums[i-1] > list.Last())
            {
                list.Add(nums[i-1]);
            }
            else
            {
                for(int j = 1; j < list.Count; j++)
                {
                    if (nums[i - 1] < list[j] && nums[i - 1] > list[j-1])
                    {
                        list[j] = nums[i - 1];
                    }
                }
            }
        }
        return list.Count-1;
    }
}

여기서 이 코드를 조금더 최적화를 해줄려면 같은 값이 들어왔을때 for문을 나가던가 진행없이 바로 다음값이 입력되게 해주면된다.

public class Solution {
    public int LengthOfLIS(int[] nums) {
        List<int> list = new List<int>();
        list.Add(-10001);

        for(int i = 1; i < nums.Length +1; i++)
        {
            if(nums[i-1] > list.Last())
            {
                list.Add(nums[i-1]);
            }
            else if (nums[i - 1] == list.Last())
            {
                continue;
            }
            else
            {
                for(int j = 1; j < list.Count; j++)
                {
                    if(nums[i - 1] == list[j])
                    {
                        break;
                    }
                    else if (nums[i - 1] < list[j] && nums[i - 1] > list[j-1])
                    {
                        list[j] = nums[i - 1];
                    }
                }
            }
        }
        return list.Count-1;
    }
}