일하는 개미의 개발 블로그

1. 문제 파악하기

- orders 배열의 크기는 2 이상 20이하이다. & orders 배열의 각 원소의 크기는 2이상 10이하인 문자열이며 대문자로만 이루어져 있다.

- 정답은 오름차순으로 정렬해서 return해야함.

2. 문제 접근하기

- orders에 있는 원소들의 조합을 생각해야함. 이때 조합의 길이는 2이상 10이하의 자연수임 → itertools 라이브러리의 combinations를 사용할 것임

- 단품 메뉴 조합이 2번이상 나와야하며 가장 많이 나온 것들을 찾아야함.

3. 주의할 점

- orders의 원소들은 대문자로 되어있지만 사전순으로 정렬되어 있지 않음 → 먼저 정렬시킬 필요가 있음

- 언급은 되었더라도 2번 이상 언급이 된 코스요리여야함.

4. 정답 코드 및 해석

제가 작성한 코드는 아래와 같습니다.

from itertools import combinations

def solution(orders, course):
    answer = []
    for i in course :
        combination = []
        for j in orders :
            j = ''.join(sorted(list(j)))
            result = list(combinations(j,i))
            for k in result :
                combination.append((''.join(list(k))))
        result = []
        for j in combination :
            count = combination.count(j)
            result.append((j,count))
        result = list(set(result))
        result = sorted(result, key=lambda x: x[1], reverse=True)
        max_result = list(filter(lambda x: x[1] > 1 and x[1] == result[0][1], result))
        for j in max_result :
            answer.append(j[0])
    answer.sort()
    return answer

1. 우선 course의 원소를 기준으로 for문을 돕니다.

2. 그 안에 다른 for문을 작성하는데 이는 orders의 원소를 기준으로 돕니다. 이 for문의 용도는 orders 원소를 i길이로 combination하기 위함입니다. orders의 원소는 사전식으로 정렬되어 있지 않았습니다. 따라서 문자열을 리스트로 변형시키고 정렬한 다음 .join()을 이용해서 정렬된 문자열로 만듭니다.

3. result 변수 안에는 i길이로 조합된 원소들이 있습니다. 이때 result안에 원소들은 ("A","B")와 같이 집합 형태로 되어 있으므로 join()을 이용해서 combination이라는 변수에 조합된 문자열을 넣습니다. for문을 다 돌았을 때, combination 변수 안에는 orders안에 있는 원소가 i길이로 조합된 문자열이 들어 있을 것입니다. ex) i=2, orders = ["ABC", "EFQ"] 라면 combination의 최종 결과는 ["AB", "AC", "BC", "EF", "EQ", "FQ"]가 들어 있습니다.

4. 다시 for문을 만들어서 combination의 각 원소가 몇번 나왔는지 센다음 result에 (조합된 문자열, count) 형태로 저장합니다. 하지만 이때 result에는 중복된 값이 있을 수 있습니다. 그래서 result = list(set(result))를 이용해서 중복된 값을 제거한 다음 다시 리스트로 만듭니다.

5. result에 들어있는 원소들을 count를 기준으로 내림차순으로 정렬합니다. 그러면 가장 많이 count된 조합이 가장 앞에 있겠죠? count된 횟수가 같은 원소들이 있을테니 filter 함수를 이용해서 count가 2이상, 가장 많이 언급된 원소들만 골라냅니다. 골라낸 원소들은 max_result 변수에 저장됩니다.

6. filter된 원소들을 answer에 넣습니다.

7. 마지막 return하기전에 answer 리스트를 정렬한 다음 return합니다.

이렇게 코드를 작성하고 채점을 하면 다음과 같은 결과로 통과가 됩니다.

5. 마치며

이번 문제는 level2치곤 쉬운 문제였습니다. 하지만 itertools의 combinations 기능을 몰랐다면 조합을 어떻게 만들지 조금 많이 고민했어야 했을거 같습니다. 이번 문제는 카카오 블라인드 채용에서 나온 문제인데 예전보다 카카오에서 나오는 문제들이 꽤 많이 까다롭고 복잡한 경우가 많은거 같습니다. 이번 문제는 코딩을 할줄 아냐 모르냐를 판별하는 정도인거 같은데 다른 문제들을 보면 꽤 어려운 문제들도 많더군요..ㅎ 더 노력해야겠습니다. 이번 문제는 조금 길어서 겁먹으신 분들도 있으실텐데 코딩테스트도 수능 문제처럼 문제가 길수록 힌트가 많은거 같습니다. 문제가 길수록 옆에 개인 노트에 잘 정리하면서 문제를 생각한다면 조금 더 수월하게 문제를 풀 수 있을거 같습니다.

1. 문제 파악하기

- prices의 각 가격은 1~10,000 이하인 자연수 & prices의 길이는 2이상 100,000 이하 → level 1에서보단 prices의 길이가 조금 긴편이지만 그래도 적당한 길이.

2. 문제 접근하기

- 초 단위로 기록된 주식 가격이 담긴 배열 prices가 매개변수로 주어지고, 가격이 떨어지지 않은 기간은 몇초인지 retrurn해야함. → 1초의 가격이 2이고 2초 가격이 1이면 return 배열에 들어가는 1초 가격이 떨어지지 않은 기간은 1초이다. 1초 가격이 2, 2초가격이 3, 3초 가격이 1이면 return 배열에 들어가는 1초 가격이 떨어지지 않은 기간은 2초이다.

3. 주의할 점

level 1 과 다르게 인자로 주어지는 값의 길이가 많이 커졌습니다. 이때 단순하게 level 1에서 생각한 방법으로 코드를 작성하시다간 시간초과가 일어날 가능성이 높습니다. 이번 문제에선 커트라인을 꽤 크게 주어진 듯하지만 개인적으로도 만족하지 않은 코드입니다. 다른 사람들 풀이의 댓글에보면 스택을 이용하면 O(n)로 문제를 풀 수 있다고 합니다. 저도 지금 당장은 생각이 나지도 않고 다른 사람들 풀이에도 O(n^2)으로 푼 방법 밖에 없어서 한번 생각해봐야겠습니다. ㅎㅎ

4. 정답 코드 및 해석

제가 문제를 푼 방법은 다음과 같습니다.

def solution(prices):
    answer = [0 for i in range(len(prices))]
    for i in range(len(prices)) :
        for j in range(i+1,len(prices)) :
            if prices[i] <= prices[j] :
                answer[i] += 1
            else :
                answer[i] += 1
                break
    return answer

시간 복잡도를 신경쓰지 않는다면 생각보다 간단하게 문제를 해결할 수 있습니다.

저는 우선 answer이라는 배열에 prices길이만큼 0이라는 숫자들을 담았습니다.

그런 다음 다들 보이시겠지만 2중 for문을 사용하여 O(n^2)으로 문제를 해결했습니다.

이 코드는 원소 하나씩 차례대로 비교하면서 값을 구하는 방법이죠.

이렇게 코드를 작성하면 아래와 같이 케이스를 해결할 수 있습니다.

5. 마치며

오늘은 level 2의 문제를 보았지만 그 중에서도 가장 짧고 간단한 코드들을 보았습니다. level 2라고해서 level 1과 크게 다를 것은 없습니다. 다만 코드의 길이가 조금 늘어나고 level 2부터는 시간 복잡도를 생각하면서 문제를 해결하기 시작해야합니다. 이번 문제에서는 O(n^2)로도 문제가 해결됐지만 일반적으로 대기업 코딩테스트에서는 조금 힘들 가능성이 높겠죠. 문제를 해결했다고 해서 만족하고 넘어가는 것이 아니라, 조금 더 나은 코드들을 생각해보시고 그 방법으로 다시 문제를 풀어보시는 것이 좋겠습니다.