본문 바로가기

알고리즘/프로그래머스

2019 카카오 코딩테스트 기출 - 실패율 , 파이썬 1. 문제 - 이번 문제 역시 매우 쉬운 편으로 문제 요구사항을 구현하면 된다. 2. 풀이 - 여러가지 풀이가 있겠지만 아래 풀이는 좀 지저분한편 - stages 배열을 순회하며 각 스테이지에 몇 명 도달했고 몇 명 멈춰있는지 저장 - 실패율을 계산하고 0으로 나누지 않도록 주의(문제에 명시되어있음) - 사실 가장 어려운 부분은 정렬인데 실패율은 내림차순으로, 실패율이 같은 경우는 오름차순으로 정렬해야한다. * 참고 1) 파이썬 다중정렬 비교할 아이템의 요소가 복수 개일 경우, 튜플로 그 순서를 내보내주면 된다. ex. sorted(e, key = lambda x : (x[0], -x[1])) -를 붙이면, 현재 정렬차순과 반대로 하게 된다. 2) 람다(Lambda) lambda 인자 : 표현식 def ..
2019 KAKAO BLIND RECRUITMENT - 오픈채팅방, 파이썬 1. 문제 - 2019 카카오 코딩테스트 1차 1번 오픈채팅방 문제이다. - 난이도는 레벨 1로 추정되며 매우 쉬운 문제 - 개선점을 기록하고자 남겨둠 2. 풀이 - 들어왔던 ID가 새로 들어왔을 때 그 이전 기록이 새로 들어온 닉네임으로 바뀜. - Leave의 경우 닉네임 기록이 없음 - Change의 경우도 해당 아이디의 닉네임이 모두 새로운 닉네임으로 바뀜 - 딕셔너리에 아이디를 키로 해서 최신 닉네임으로 업데이트해준다. - 나중에 반복문으로 출력 def solution(record): ans = [] dic = {} for i, data in enumerate(record): record[i] = data.split(" ") if record[i][0] == 'Enter' or record[i][..
2020 KAKAO BLIND RECRUITMENT - 가사 검색 (파이썬) 1. 문제 - 카카오 코딩테스트 가사검색 문제 - 주어진 queries 에 맞는 words의 수를 리턴하는 문제 - 단 와일드카드 "?" 가 들어감 - queriesquequeriesries 2. 풀이 - word와 query의 길이는 각각 100,000 이기 때문에 Brute Force로 풀면 시간초과가 나온다. - 따라서 시간초과가 떴고 써 본적이 없는 트라이 구조를 검색해서 적용해봤다. - 와일드카드가 단어 중간에 들어갈 수 없으며 빈칸일 수는 없다는 점(와일드카드에 따라 단어 수가 변동되지 않는다는 점)이 힌트인듯 - 단어 길이는 최대 10,000 이기 때문에 각 단어길이에 맞는 Trie 배열을 생성해준다.(접두사가 같더라도 단어 길이에 따라 = 뒤에 붙는 와일드카드 ? 개수에 따라 답이 다르기 ..
카카오 코딩테스트 2020 괄호 변환, 파이썬 1. 문제 1) 문제에서 주어진 정의에 따라 요구한 순서대로 풀면 된다. 2) 말 그대로 언어를 프로그래밍 언어로 변환하면 되는 문제이기 때문에 매우 쉬운 문제이다. 3) 알고리즘은 사실상 완전한 괄호를 찾는 알고리즘(스택이나 Brute force 이용)만 필요. 2. 풀이 좀 길긴 하지만 누구나 이해하기 쉽게 짰다는 점에서 만족스럽다. 다만 함수 이름과 변수명에 대해서는 좀 고민이 필요할듯..^^ def solution(p): answer = '' if not p : return answer while not is_val(p) : idx = find_u(p) u = p[:idx] v = p[idx:] if is_val(u) : answer += u p = v else : temp_v = solution..
카카오 코딩테스트- 문자열 압축, 파이썬 1. 문제 문자열을 압축하여 표현할 때 가장 짧은 문자열 수를 구하라 2. 풀이 1부터 문자열 길이의 절반까지 반복해서 압축된 문자열의 길이 중 최소값을 구하는 식으로 풀었다. Brute force 문제인데 왜 함수명을 dfs라쓴지는 모르겠다. 1번문제 답게 어렵지 않게 풀 수 있다. 다만 두 가지 때문에 테스트케이스를 틀렸는데 1) 아래처럼 범위를 돌리다보니까 s 길이가 1인 경우 for문이 실행되지 않아 ret 배열이 비어버려 오류가 난다. for i in range(1, len(s)//2 + 1) : dfs(s, i, ret) 그냥 구현만 하려고 위에 문자열 길이가 1인 경우 예외처리를 해줬는데 주의해야할 부분이다 2) 반복되는 문자열이 나온 경우 앞의 숫자 예를들어 aaa의 경우 3a로 생각하고 ..
카카오 코딩테스트 2021 - 합승 택시 요금 (파이썬) 문제 프로그래머스 합승 택시 요금 링크 A와 B가 같은 지점에서 택시를 타고 임의의 경유지까지 합승 후(옵션) 각자의 목적지까지 가는 최소의 요금의 합을 구하는 문제 결국 정점을 거쳐 출발지에서 목적지로 가는 최소비용을 구하는 문제 풀이 레벨 3 난이도 합승하지 않는 케이스는 출발지점에서 출발지점까지 합승한다고 가정하면 이때 비용은 0이므로, 결국 모든 노드까지 합승하는 비용 + 합승지점에서 각자의 목적지까지 가는 비용을 더한 값 중 최저값을 구하면 된다. 각 지점에서 각 지점까지 가는 최소비용이 필요, dfs를 이용해서 구했더니 타임초과가 떴다. 결국 검색 후 플로이드 와샬이 알고리즘을 적용했다. 플로이드와샬 알고리즘 기본적으로 DP에 근거한 알고리즘 거쳐가는 정점 기준으로 최소 비용을 구하는 알고리즘..
2021 KAKAO BLIND RECRUITMENT - 순위 검색, 파이썬 과정 1. 문제를 구현하는 것은 어렵지 않지만 시간 조건때문에 조금 까다롭다. 주어진 두 개의 배열이 각각 50,000, 100,000개라서 각각 순환하며 조건을 체크하면 1억번이 넘어 시간제한(10초)에 걸리게 된다. 2. 따라서 딕셔너리를 이용해서 어지간한 건 사전처리를 해줘서 이용하기 쉽게 해준다. 예를 들어 sort()같은 경우 시간복잡도가 O(n)이기 때문에 따로 빼줘서 시간제한에 걸리지 않게 해준다. 3. 조건 점수에 맞는 케이스를 찾는 것도 그냥 인덱싱은 O(n)이라 시간초과가 나와 O(logn)인 이분탐색을 활용한다. lower boundary니 Upper boundary니 있던데 어차피 binary search 고 그때그때 예시로 생각해보면 된다. 개선점 1. 시간초과를 생각안하고 풀면서..
2021 카카오 코딩테스트 기출- 메뉴 리뉴얼 - 카카오는 기출을 프로그래머스에 공개한다. 내 수준에서 레벨1은 쉽고 레벨 2는 구현은 가능하나 코드가 지저분하고, 레벨 3은 반반이다. 레벨 4부터는 확실히 어렵다. 코딩테스트 통과 기준은 정해져있지 않지만 통상 레벨 3까지는 무난하게 풀어야 한다고들 말한다. 릿코드 기준으로 medium 까지는 그냥 풀어야 하는 것. - 카카오 기출은 문제가 난이도와 관계없이 문제가 장황한 편이다. 논리력은 기본이나 회사생활에 필요한 독해력을 보려고 하는 것이 아닌지 추측해본다. 기획자의 주저리 주저리 요청사항에서 필요한 요소를 뽑아내는 능력을 보는 것이 아닐까? -일단 목표는 구현 및 통과가 첫번째, 나중에 다른사람들의 코드를 참고하거나 내 코드를 리팩토링 하도록 해보자. 문제 - 생략 코드 - 파이썬 def so..

티스토리툴바