이번 포스팅에서는 지난 MathWorks의 Cody문제에 이어서 Problem 44949를 해결한 내용을 다룹니다. 이번 문제에서는 자료구조와 알고리즘 수업 때 공부했던 Sorting 개념을 적용하여 cutoff 이상의 rating값을 가진 호텔 이름이 오름차순으로 Sorting된 벡터를 반환하도록 문제를 변형하여 해결해보았습니다.

Review

먼저 기존 문제와 문제에 대한 솔루션입니다.

# Problem 44949. Find the Best Hotels

Given three input variables:
hotels - a list of hotel names
ratings - their ratings in a city
cutoff - the rating at which you would like to cut off


Return only the names of those hotels with a rating of cutoff value or above as a column vector of strings good.

# Problem 44949. Solution

function good = find_good_hotels(hotels,ratings,cutoff)
    good = hotels(ratings >= cutoff)
end

---

다음은 Sorting 기능을 추가한 벡터값을 반환하도록 변형한 문제와 솔루션입니다.

# Problem 44949. Find the Best Hotels(Modified)

Given three input variables:
hotels - a list of hotel names
ratings - their ratings in a city
cutoff - the rating at which you would like to cut off


Return only the names of those hotels with a rating of cutoff value or above as a column vector of strings good.
Esspecially, the name of the hotel that is output at this time should be output in the order of the lowest rating value.

# Problem 44951. Solution using Selection Sorting(Modified)

function good = find_good_hotels(hotels,ratings,cutoff)
    good_not_sorted = hotels(ratings >= cutoff)
    ratings_not_sorted = ratings(ratings >= cutoff)
    siz = length(good_not_sorted);
    for m = 1:siz-1
        idx = m;
        for n = m+1:siz
            if ratings_not_sorted(idx) > ratings_not_sorted(n)
                idx = n;
            end
        end
        tmpRating = ratings_not_sorted(m);
        ratings_not_sorted(m) = ratings_not_sorted(idx);
        ratings_not_sorted(idx) = tmpRating;
        
        tmpGood = good_not_sorted(m);
        good_not_sorted(m) = good_not_sorted(idx);
        good_not_sorted(idx) = tmpGood;
    end
    good = good_not_sorted
end

---

---

문제를 마치며

즉흥적으로 Sorting 문제를 만들고 해결하다보니 알고리즘 수업시간에 배웠던 여러 가지 Sorting Algorithim- Insertion Sort, Merge Sort, Quick Sort etc.-을 곧바로 구현하기에 어려움이 있어 시간복잡도가 가장 크고 비효율적인 Selection Sort를 활용하여 문제를 해결하였습니다.

스스로 문제를 변형하여 해결하는 과정에서 이론적인 학습 이외에도 이러한 알고리즘 문제를 코딩으로 직접 경험하고 해결하는 경험이 필요하다는 느낌을 받았습니다. 이를 계기로 기회가 된다면 기본적인 자료구조와 알고리즘에 관한 코딩테스트 문제를 해결하고 포스팅하며 복습할 것을 다짐했습니다.