본문 바로가기

알고리즘/프로그래머스

프로그래머스 2018 카카오 코딩테스트 - 프렌즈4블록, 파이썬 1. 문제 - 애니팡같이 블럭을 없애는 게임을 구현하는 것 2. 풀이 - 요구하는 구현이 그렇게 어렵지는 않다 - 없어지는 블록 찾기, 찾으면 블록 없애주기, 없어지면 위에 블록 당겨주기, 가능한 블록 다 없앴으면 그동안 제거한 블록 리턴 - 답을 내는 건 쉬웠는데 코드가 다소 지저분하다. 3. 코드 # 없어지는 블록을 0으로 구현했기 때문에 0을 제외한 4개가 같으면 True def check_block(board, i, j) : if board[i][j] == 0: return False if board[i][j] == board[i+1][j+1] == board[i+1][j] == board[i][j+1] : return True return False # 없어지는 블록을 0으로 구현 def del..
2018 KAKAO BLIND RECRUITMENT- 뉴스 클러스터링, 파이썬 문제 프로그래머스 문제 링크 문제 파악 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의 다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로, J(A, B) = 3/7, 약 0.42 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다 대문자와 소문자의 차이는 무시 자카드 유사도를 구하고 6553..
2018 카카오 코딩테스트 - 추석 트래픽, 파이썬 문제 로그 문자열이 들어있는 lines 배열이 주어질 때 초당 최대 처리량을 리턴하라 풀이과정 시간복잡도 고려 : 크게 고려할 필요 없음 lines 배열은 N(1 ≦ N ≦ 2,000) 문제 조건 확인 2016-09-15 hh:mm:ss.sss 형식, 2016-09-15 03:10:33.020 0.011s은 "2016년 9월 15일 오전 3시 10분 33.010초"부터 "2016년 9월 15일 오전 3시 10분 33.020초"까지 "0.011초" 동안 처리된 요청을 의미 기준 시간, 시작 시간, 끝 시간 지정이 애매한데 예제 2번에서 친절히 설명되어 있다 설명: 처리시간은 시작시간과 끝시간을 포함하므로 첫 번째 로그는 01:00:02.003 ~ 01:00:04.002에서 2초 동안 처리되었으며, 두 번째..
2019 카카오 블라인드 코딩 테스트 - 블록게임, 파이썬 1. 문제 - 테트리스에서 개념을 가져온 문제로 세부사항은 프로그래머스 문제 참고 2. 풀이 - 이 문제는 마지막 문제인데다가 쉬워보여서 얼렁뚱땅 풀어보다 틀렸다. - 아래 테스트케이스에서 답이 1이 나와야 한다. [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 2, 2, 0, 0, 0, 0, 0], [0, 0, 0, 2, 1, 0, 0, 0, 0, 0], [0, 0, 0, 2, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] - 또한 테스트케이스 14, 15, 16, 17번이 왜 틀렸나 했더니 반복문 중에 블록 숫자만큼 반복해줘야 하는데 적당히 N만큼 반복해줬다 틀렸다(예제 ..
2019 KAKAO BLIND - 매칭 점수(파이썬, 정규표현식 없이) 1. 문제 - 2019 카카오 코딩테스트 매칭 점수 문제 - 조건에 따라 문자열을 적절히 처리해주는 문제 - 테스트케이스 9번, 10번이 까다롭다. 2. 풀이 - 다들 정규식을 사용하였으나 실제 시험이었다면 정규식을 모르고 들어갔을 것이므로 정규식 없이 풀어봄 - 코드는 상당히 지저분하고 시간 및 공간 효율이 좋지 못하나 매우 이해하기 쉽게 짰음 #### 9번과 10번 테스트 케이스 실패한 경우 ###### - 9번은 meta 태그 내의 url을 파싱하지 못해서, 10번은 a 태그 내의 링크를 파싱하지 못해서 실패가 뜬다. - 9번과 10번을 해결하기 위해서는 각각 문제 조건에 주어진대로 9번의 url은 meta태그 내에서만, 10번의 링크는 a태그 내에서만 가져와야 한다. 아마 href 혹은 https..
2019 KAKAO BLIND RECRUITMENT- 길 찾기 게임, 파이썬 1. 문제 - 2차원 배열로 좌표가 주어지면 주어진 조건에 따라 전위순회, 후위순회 배열을 리턴하면 된다. 2. 풀이 - 이진트리에서 전위 순회(preorder), 후위 순회(postorder)에 대한 내용을 알고 있으면 크게 어렵지 않은 문제이다. - 트리 자료구조를 구현하여 풀 수도 있지만 그냥 풀릴것 같아서 풀어봤다. - 다만 테스트 6번, 7번에서 런타임 에러가 났는데 찾아보니 파이썬 재귀함수 횟수 제한에 걸려서 그렇다고 한다. - 재귀 제한이 기본 1000으로 걸려있다고 한다. - 재귀 제한 안에 푸는 것도 문제에서 요구하는 것인가 잠깐 생각해봤지만 재귀 제한을 1005로 늘렸을 때 테스트를 통과하는 것으로 봐서는 문제 설계의 오류가 아닌가 의심해본다(희망사항) - 솔직히 sys.setrecur..
2019 KAKAO BLIND RECRUITMENT- 무지의 먹방 라이브, 파이썬 1. 문제 - 효율성 테스트에 부분점수가 있는 문제 = 효율성 테스트 통과가 관건 - 문제 자체는 이해하기 쉬운 편 2. 풀이 - 효율성 통과를 못할걸 알았지만 일단 대강 짜서 정확성 테스트만 통과했다. - 효율성 테스트의 경우 k의 값이 이미 1억을 넘기기 때문에 k번 순회하는 것은 안 된다. - 배열에서 최소값을 찾아내야 하고 적절한 계산 후 pop()으로 빼줘야 하기 때문에 우선순위 큐가 떠오르긴 했다. - 다만 배열 길이를 줄여가면서 몫과 나머지로 처리하려는 계획이 너무 복잡해서 그냥 구글링을 해봤다. - 조금 더 고민했으면 풀었을 것 같은데 너무 쉽게 포기한 감이 있다. - 맨 아래 코드는 구글링 한 코드를 참고하여 작성하였다. - 주의할 점은 heapq.heappop(heap)의 경우 heap..
2019 KAKAO BLIND RECRUITMENT- 후보키, 파이썬 1. 문제 - 주어진 relation 배열에서 후보키를 구하는 문제 - 유일성과 최소성을 만족해야함 - 후보키의 개수를 리턴 2. 풀이 - 풀이 방법 자체는 어렵지 않게 떠올릴 수 있으나 좀 깔끔하게 짤 수 없을까 하다가 오래걸림 - 각 키들의 모든 조합을 구한 후 중복이 배열에 중복이 없는지 체크(유일성) - 단 최소성을 만족시키기 위해 a 가 후보키인 경우 [a, c] 조합을 계산할 필요 없음 - return_cases 함수로 모든 조합을 구한 후(인덱스를 구했으나 그냥 문자열로 구하는게 편했을듯, 유효성 체크할때), 모든 케이스에 대해 check_dup로 중복이 있는지(유일성) 체크, 그 뒤에 val_check로 최소성 체크, 최소성 만족한다면 check에 후보키로 등록, 마지막에 후보키의 개수를 ..

티스토리툴바