본문 바로가기

알고리즘/프로그래머스

 (45)
[프로그래머스][2018 KAKAO BLIND RECRUITMENT][Python] 다트 게임 [ 문제 ] 문제 풀러 가기 [출제 의도] 문자열 처리 [ 문제 풀이 ] 보너스와 옵션에 맞춰 누적된 숫자에 계산해주면 됩니다. 다만, 이를 문자열을 한 글자씩 처리할 경우 신경써서 처리해야 할 부분이 생깁니다. 두 자리 수입니다. 두 자리 수는 10밖에 없습니다. 따라서 10을 미리 한 자리 문자열로 치환하면 계산을 쉽게 처리할 수 있습니다. [ 정답 코드 ] # S: 1제곱, D: 2제곱, T: 3제곱 # *: 해당 점수와 바로 전에 얻은 점수를 각 2배 # #: 해당 점수를 마이너스 def solution(dartResult): li = [] i = -1 dartResult = dartResult.replace("10", "K") for n in dartResult: if n == "S": cont..
[프로그래머스][2018 KAKAO BLIND RECRUITMENT][Python] 방금그곡 [ 문제 ] 문제 풀러 가기 [출제 의도] 문자열 처리 [ 문제 풀이 ] ABC는 ABC#안에 들어있지 않지만, ABCD안에는 들어있습니다. C과 C#은 다르기 때문입니다. 그래서 #의 문자열 처리가 이 문제의 핵심입니다. 저는 C#은 c로 치환하여 C#과 C와의 차이를 두었습니다. 다른 '대문자#' 문자열에도 마찬가지로 적용했습니다. [ 정답 코드 ] def solution(m, musicinfos): answer = ["(None)", 0] for info in musicinfos: start, end, title, song = info.split(",") # 악보 변환 ch = {"C#": "c", "D#": "d", "F#": "f", "G#": "g", "A#": "a", "E#": "e"} f..
[프로그래머스][2018 KAKAO BLIND RECRUITMENT][Python] 비밀지도 [ 문제 ] 문제 풀러 가기 [출제 의도] 비트 연산자 활용 [ 문제 풀이 ] 지도1과 지도2의 각 정수를 비트 OR 연산자를 이용해 합칩니다. 합친 결과의 길이가 N보다 짧다면 앞 부분에 공백을 넣어 길이를 N으로 맞춥니다. 마지막으로 0은 공백으로 1은 #으로 치환하면 됩니다. [ 정답 코드 ] def solution(n, arr1, arr2): answer = [""] * n for i in range(n): tmp = str(bin(arr1[i] | arr2[i]))[2:] # 비트 OR answer[i] = (n % len(tmp)) * "0" + tmp # 고정길이 N answer[i] = answer[i].replace("0", " ") answer[i] = answer[i].replace(..
[프로그래머스][2019 KAKAO BLIND RECRUITMENT][Python] 오픈채팅방 [ 문제 ] 문제 풀러 가기 [출제 의도] 해시 활용 [ 문제 풀이 ] 먼저, record를 순회하면서 '입장과 변경 기록'을 가지고 딕셔너리를 이용해 유저 아이디마다 최종 닉네임을 구하고, '입장과 퇴장 기록'은 new_record를 만들어서 따로 저장합니다. 그다음, new_record를 순회하면서 채팅방에 출력할 메시지를 생성합니다. 이때 유저 아이디는 최종 닉네임을 사용하면 됩니다. [ 정답 코드 ] # 시간복잡도 O(N)으로 처리 from collections import defaultdict def solution(record): name = defaultdict(str) order = [] new_record = [] # 닉네임 관리 for datas in record: data = data..
[프로그래머스][2019 KAKAO BLIND RECRUITMENT][Python] 매칭 점수 [ 문제 ] 문제 풀러 가기 [출제 의도] 정규표현식 활용 [ 문제 풀이 ] 먼저, 정규표현식으로 HTML 파일에서 현재 URL, 외부 URL 그리고 검색어를 찾습니다. 외부 URL의 수는 외부 링크 수가 되고, 검색어의 개수는 기본 점수가 됩니다. 각 HTML 파일의 기본 점수 / 외부 링크를 저장해 놓았다가, 해당 웹 페이지와 연결된 다른 웹 페이지의 링크 점수를 구할 때 사용합니다. 마지막으로 페이지마다 (기본 점수와 링크 점수를 더한) 매칭점수를 구하고, 최댓값의 Index를 구합니다. 최댓값이 여러 개라면, Index가 가장 작은 것이 정답입니다. [ 정답 코드 ] # 졍규표현식 활용 from collections import defaultdict import re def solution(wor..
[프로그래머스][2020 KAKAO BLIND RECRUITMENT][Python] 괄호 변환 [ 문제 ] 문제 풀러 가기 [출제 의도] 주어진 로직 그대로 구현 문자열 활용 재귀함수 [ 용어의 정의 ] '균형 잡힌 괄호 문자열'은 괄호의 개수가 맞습니다. '올바른 괄호 문자열'은 괄호의 개수도 맞고 짝도 맞습니다. [ 문제 풀이 ] 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 4..
[프로그래머스][2020 KAKAO BLIND RECRUITMENT][Python] 문자열 압축 [ 문제 ] 문제 풀러 가기 [출제 의도] 문자열을 활용 [ 문제 풀이 ] 문자열 길이가 N일 때, 분절 범위는 1부터 n/2입니다. n/2를 넘어가게 되면 문자열을 줄일 수 없습니다. 문자열의 길이는 최대 1,000입니다. 따라서 완전 탐색을 해도 시간 초과가 나지 않습니다. 그래서 분절 범위마다 줄인 결괏값 중에서, 가장 짧은 길이를 찾았습니다. 주의할 점은 문자열 길이가 1이면 1을 반환합니다. [ 정답 코드 ] def solution(s): result = len(s) + 1 for n in range(1, (len(s) // 2) + 1): # 분절 범위 cnt = 1 tmp = len(s) check = True for i in range(0, len(s) - n + 1, n): # 앞에서부터..
[프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 합승 택시 요금 [ 문제 ] 문제 풀러 가기 본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다. [출제 의도] 최단 경로 알고리즘 [ 문제 풀이 ] 먼저, 모든 노드에서 모든 노드로의 최단 경로를 구해야 합니다. Floyd-Warshal 알고리즘을 사용했습니다. cost[i][j] = i에서 j로 가는 최저 택시 요금 그다음, 어느 노드를 A와 B의 분기점으로 정할지 구해야 합니다. K를 분기점이라고 했을 때, S ~ K, K ~ A, K ~ B의 합이 최솟값일 때가 정답입니다. 문제에서 요구하는 답 = min(cost[s-1][k] + cost[k][a-1] + cost[k][b-1]) (단, k = 1 ~ n) Dijkstra 알고리즘을 사용하지 않은 이유는 비효율적이기 때문입니다. [ 정답 코드 ] #..
[프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 메뉴 리뉴얼 문제를 정리해보자. 이전에 각 손님이 주문할 때 가장 많이 함께 주문했던 단품 메뉴들을 코스요리 메뉴로 구성한다. 1) 코스요리 메뉴는 최소 2가지 이상의 단품 메뉴로 구성된다. 2) 최소 2명 이상의 손님으로부터 주문된 단품 메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함한다. 입출력 1. orders: 각 손님이 주문한 단품 메뉴들이 문자열 형식으로 담긴 배열 2. course: "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품 메뉴들의 개수가 담긴 배열 풀이를 생각해보자. 첫 번째 예로 생각해보자. ABCFG로 만들 수 있는 2, 3, 4개 코스의 후보는 아래와 같다. 이렇게 orders의 메뉴 구성마다 N개 코스의 후보를 구한다. 최종적으로 N개 코스마다 가장 많이 주문된 후보가 정답이다. ..
[프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 순위 검색 문제를 정리해보자. 카카오는 하반기 경력 개발자 공개채용을 진행 중이다. 현재 지원서 접수와 코딩테스트가 종료되었다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였다. 항목은 아래와 같다. 개발언어: cpp, java, python 지원 직군: backend, frontend 지원 경력: junior, senior 소울푸드: chicken, pizza 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에게 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인지 쉽게 알 수 있는 도구를 만들어보자. 개발팀에서 궁금해하는 내용: '[조건]을 만족하는 사람 중 코딩테스트 점수 X점 이상 받은 사람은 모두 몇 명인가?' 예) 코딩테스트에 ja..

티스토리툴바