일하는 개미의 개발 블로그

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)로도 문제가 해결됐지만 일반적으로 대기업 코딩테스트에서는 조금 힘들 가능성이 높겠죠. 문제를 해결했다고 해서 만족하고 넘어가는 것이 아니라, 조금 더 나은 코드들을 생각해보시고 그 방법으로 다시 문제를 풀어보시는 것이 좋겠습니다.

1. 문제 파악하기

- new_id는 길이가 1이상 1,000 이하인 문자열이다. → 별로 길지 않은 문자열

- new_id는 알파벳 대문자, 알파벳 소문자, 숫자, 특수문자로 구성되어 있음.

- new_id에 나타날 수 있는 특수 문자는 -_.~!@#$%^&*()=+[{]}:?,<>/ 로 한정. → 이 중에서 앞에 - _ . 만 사용가능하고 나머지는 지워야함

2. 문제 접근하기

이번 문제는 문제에서 주어진 7가지 단계 순서대로 구현하면 쉽게 문제를 해결할 수 있습니다. 코드는 level1 문제치곤 길다고 생각드실 수도 있지만 그렇게 어려운 알고리즘을 생각할 필요는 없다고 생각이 듭니다.

3. 주의할 점

- 입력으로 주어지는 new_id의 길이가 1이상 1,000 이하인 문자열이라서 무한루프에 빠지지만 않는다면 실행시간이 그렇게 오래걸리지 않을 것입니다. 7가지 단계 중 특수 문자 제거, 연속된 마침표를 제거 부분에서 while문을 이용해서 코드를 작성하신 분들이라면 무한루프를 조금 주의해서 코드를 작성하셨어야 할거 같습니다.

- 특수 문자 제거, 마침표 제거 등 문자열을 제거하다보면 빈문자열이 만들어지는 경우가 있을텐데, 이때 인덱싱 에러 문제로 조금 조심해야할 부분인거 같습니다.

4. 정답 코드 및 해석

def solution(new_id):
    del_str = ["~", "!", "@", "#", "$", "%", "^", "&", "*","(", ")", "=",
               "+", "[", "{", "]", "}", ":", "?", ",", "<", ">", "/"]
    #1단계 소문자로 바꾸기
    new_id = new_id.lower()
    #2단계 특수 문자 제거
    index = 0
    while index < len(new_id) :
        if new_id[index] in del_str :
            new_id = new_id.replace(new_id[index], "")
        else :
            index += 1
    #3단계 마침표 2번이상 연속을 하나로 치환
    while ".." in new_id :
        new_id = new_id.replace("."*2, ".")
    #4단계 마침표 처음과 끝에 위치 제거
    if len(new_id) > 0 and new_id[0] == "." :
        new_id = new_id[1:]
    elif len(new_id) > 0 and new_id[-1] == "." :
        new_id = new_id[:-1]
    #5단계 빈 문자열이면 "a"를 대입
    if new_id == "" :
        new_id = "a"
    #6단계 16자리 이상이면 15까지 남기고 제거 & 끝자리 마침표 제거
    if len(new_id) > 15 :
        new_id = new_id[:15]
    if new_id[-1] == "." :
        new_id = new_id[:-1]
    #7단계 2자리 이하면 아이디의 마지막 문자 반복
    while len(new_id) <= 2 :
        new_id += new_id[-1]
    return new_id

정답 코드 및 해석입니다. 7가지 단계로 나눠서 작성하다보니 코드가 조금 길어서 단계별로 나눠서 설명을 드리겠습니다.

우선 del_str이라는 리스트가 있습니다. 보시면 아시겠지만 지워야할 특수 문자들이 들어있습니다.

1단계는 대문자로 되어 있는 문자열을 소문자로 바꾸는 과정입니다. 파이썬에서는 .lower() 함수를 이용해서 대문자를 소문자로, .upper() 함수를 이용해서 소문자를 대문자로 바꿀 수 있습니다. 파이썬의 장점중 하나인 유용한 내장함수가 많은 것을 활용하여 1단계는 1줄로 코드를 작성할 수 있습니다.

2단계는 특수 문자를 제거하는 것입니다. index라는 변수에 0을 초기화 시킵니다. 그런 다음 while문을 이용해서 new_id의 한문자씩 확인하면서 del_str에 들어 있는 특수 문자라면 replace("지울 문자", "지운 문자 대신 바꿀 문자") 함수를 이용해서 제거시킵니다. 다른 라이브러리를 사용하여 해결할 수 있는 방법도 있지만 import를 사용하지 않고 그냥 내장함수만을 이용해서 코드를 작성한다면 이렇게 간단한 방법이 있을거 같습니다. 어차피 new_id의 최대 길이가 1,000 밖에 안되니 큰 문제는 될거 같지 않습니다.

3단계는 마침표가 2번이상 연속된 부분을 하나로 치환하는 것입니다. 저는 개인적으로 이 부분을 가장 까다롭다고 생각했는데요. '어떻게하면 간단하고 짧게 해결할 수 있을까?' 생각했던거 같습니다. 제가 생각한 방법은 while문을 사용하여 new_id에 ".."이 있으면 "."으로 치환하는 방법입니다. "..."이더라도 앞의 ".."이 먼저 인식이 되서 ".."으로 바뀔 것이고 이는 한번 더 while문에 걸려서 "."으로 바뀝니다.("..." → ".." → ".") 이렇게 하면 3단계 코드도 간단하게 완료 할 수 있습니다.

4단계는 마침표가 처음이나 끝에 위치하면 제거하는 단계입니다. 이 부분은 인덱싱을 이용하면 쉽게 제거 할 수 있어서 다들 쉽게 하셨을거 같습니다. 저는 앞에 과정 때문에 길이가 0인 new_id일 경우 new_id[0]과 new_id[-1] 코드가 인덱싱 에러가 방생하여 앞에부분에 len(new_id) > 0이라는 조건을 넣어줬습니다.

5단계는 빈 문자열이면 "a"를 대입하는 단계입니다. 이 부분은 if문을 사용하시면 쉽게 하실 수 있는 부분이니 넘어가겠습니다.

6단계는 16자리 이상이면 15자리까지 남기고 나머지는 제거 & 끝자리에 마침표가 있으면 제거하는 단계입니다. 이부분도 if문을 사용하면 쉽게 구현할 수 있습니다. new_id가 15자리 초과라면 new_id를 슬라이싱하여 0~14까지 자릅니다. 그런 다음 new_id의 끝자리에 "."이 있으면 제거해줍니다.

마지막 7단계는 new_id가 2자리 이하라면 new_id의 마지막 문자를 반복하여 new_id의 길이를 3으로 만드는 단계입니다. 이 부분도 while, if문을 사용하면 쉽게 구현할 수 있었습니다.

이렇게 코드를 작성하면 다음과 같은 결과로 통과를 할 수 있었습니다.

5. 마치며

이번 문제도 크게 어려운 부분은 없었습니다. 빈문자열 처리, 무한루프에 빠지지만 않으셨다면 금방 해결하셨을거 같습니다. 저는 replace(), lower() 등을 사용하여 쉽게 구현했는데 내장 함수를 잘 모르시면 힘드셨을거 같습니다. 파이썬을 사용하신다면 파이썬의 큰 장점 중 하나인 내장 함수를 익히셔서 유용하게 사용하는 것을 추천드립니다. 내장 함수가 많은 만큼 기능은 비슷하지만 시간 복잡도, 공간 복잡도가 차이가 나는 함수들이 있습니다. 이런 것들을 잘 알고 비교해서 사용하신다면 시간초과가 나는 문제를 잘 해결하실 수도 있습니다.