본문 바로가기

알고리즘/프로그래머스

 (45)
[프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 신규 아이디 추천 문제를 정리해보자. 카카오 아이디가 주어진다. 규칙에 맞지 않는 아이디라면 규칙에 맞는 아이디로 바꿔야 한다. 다음은 카카오 아이디의 규칙이다. 1. 아이디의 길이는 3자 이상 15자 이하여야 한다. 2. 아이디는 알파벳 소문자, 숫자, 빼기, 밑줄, 마침표 문자만 사용할 수 있다. (단, 마침표는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없다.) 규칙 맞는 아이디로 처리하는 과정은 아래와 같다. 1단계: 모든 대문자를 대응되는 소문자로 변환한다. 2단계: 알파벳 소문자, 숫자, 빼기, 밑줄, 마침표를 제외한 모든 문자를 제거한다. 3단계: 마침표가 2번 이상 연속된 부분을 하나의 마침표로 치환한다. 4단계: 마침표가 처음이나 끝에 위치한다면 제거한다. 5단계: 빈 문자열이라면, "a"를 ..
[프로그래머스][2021 Dev-Matching: 웹 백앤드 개발자(상반기)][Python] 다단계 칫솔 판매 문제를 정리해보자. 위 판매망은 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태이다. 각각은 자신을 조직에 참여시킨 추천인에게 연결되어 피라미드식의 구조를 이루고 있다. 조직의 이익 분배 규칙은 다음과 같다. 1. 이익에서 10%를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가진다. + 모든 판매원은 자신이 칫솔 판매에서 발생한 이익뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10%까지 자신에 이익이 된다. + 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배된다 2. 단, 10%를 계산할 때는 원 단위에서 절사한다. 그리고 10%를 계산한 금액이 1원 미만인 경우에는 이득을 분배하지 않고 자신이 ..
[프로그래머스][2021 Dev-Matching: 웹 백앤드 개발자(상반기)][Python] 로또의 최고 순위와 최저 순위 문제를 정리해보자. 로또는 1부터 45까지 숫자 중에서 6개를 찍어서 맞히는 대표적인 복권이다. 아래는 로또의 순위를 정하는 방식이다. 민우는 로또를 구매했다. 하지만 숫자 몇 개는 알아볼 수 없게 됐다. 민우의 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보자. (0은 알아볼 수 없는 숫자이다.) 예) 민우의 번호 : 44, 1, 0, 0, 31, 25 당첨 번호 : 31, 10, 45, 1, 6, 19 최고 순위 : 3등 (4개 번호가 일치) 최저 순위 : 5등 (2개 번호가 일치) 풀이를 생각해보자. 먼저, 민우가 구매한 로또의 번호와 당첨 번호가 몇 개가 일치하는지 확인한다. 그리고 최고 순위와 최저 순위를 구한다. 최고 순위 : 0이 모두 당첨 숫자가 일 때이다. 최저 순위 : 0이 모두..
[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] 파괴되지 않은 건물 문제를 정리해보자. N x M 크기의 행렬 모양의 게임 맵이 있다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있다. 1. 건물은 적의 공격을 받으면 내구도가 감소한다. 2. 건물은 내구도가 0이하가 되면 파괴된다. 3. 건물은 아군의 회복 스킬을 받으면 내구도가 증가한다. 4. 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 된다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수는 몇 개인가? 아래는 프로그래머스에 나온 예이다. 풀이를 생각해보자. 방법 1) 매번 적의 공격 혹은 아군의 회복 스킬을 기본 게임 맵의 내구도에 적용시킨다. 이 방법은 효율성 테스트에서 통과할 수 없다. skill의 행의 길이는 최대 250,000이다. b..
[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] k진수에서 소수 개수 구하기 문제를 정리해보자. 양의 정수 n이 주어진다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 조건에 맞는 소수가 몇 개인지 찾으면 된다. 조건은 아래와 같다. ( P는 소수[Prime Number]를 의미한다.) 1. 소수 양쪽에 0이 있는 경우 : 0P0 2. 소수 오른쪽에만 0이 있는 경우 : P0 3. 소수 왼쪽에만 0이 있는 경우 : 0P 4. 소수 양쪽에 아무것도 없는 경우 : P 단, P는 각 자릿수에 0을 포함하지 않는 소수이다. 예를 들어, 101은 P가 될 수 없다. 풀이를 생각해보자. 예를 들어, 437674을 3진수로 바꾸면 211020101011이다.먼저, 211020101011안에서 조건에 맞는지 확인할 수를 찾자. ( N는 수[Number]를 의미한다.) 0을 기준으로 좌우를 ..
[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] 양과 늑대 문제를 정리해보자. 1. 이진 트리 모양의 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있다. 2. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 한다. 3. 각 노드를 방문할 때마다 해당 노드에 있던 양과 늑대가 나를 따라온다. 4. 이때, 양의 수보다 늑대의 수가 많아지면 모든 양은 잡아 먹힌다. 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아보자. 풀이를 생각해보자. 0번 - 2번 - 5번 - 1번 - 4번 - 8번 - 3번 - 7번 노드 순으로 이동하면 양 5마리, 늑대 3마리가 된다. 여기서 6번, 9번 노드로 이동하면 양 5마리, 늑대 5마리로 양이 모두 잡아 먹힌다. 따라서 늑대에게 잡아먹히지 않도록 하면서 최대로 모을 수 있는 양은 5마리이..
[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] 주차 요금 계산 문제를 정리해보자. 주차장의 요금표와 차량의 입/출자 기록이 있다. 차량별로 주차요금을 계산하자. 기본시간 이하로 이용했다면, 기본요금만 지불한다. 기본시간을 초과했다면, 기본요금 + 추가요금을 지불한다. 기본시간(분) : 180분 기본요금(원) : 5000원 단위시간(분) : 10분 단위요금(원) : 600원 예) 5961 입차 : 5시 34분 (334) 출차 : 7시 59분 (479) = 145분 입차 : 22시 59분 (1379) 출차 : 23시 (1380) = 1분 5961 결과 146분 (기본시간 이하) : 5000원 예) 0000 입차 : 6시 00분 (360분) 출차 : 6시 34분 (394분) = 34분 입차 : 18시 59분 (1139분) 출차 : 23시 59분 (강제, 1439분) = ..
[프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] 신고 결과 받기 문제를 정리해보자. 게시판 불량 이용자[용의자]를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발했다. 규칙은 다음과 같다. 1. 각 유저는 한 번에 한 명의 유저만 신고할 수 있다. 1-1) 신고 횟수에 제한이 없다. 1-2) 서로 다른 유저를 계속해서 신고할 수 있다. 1-3) 한 유저를 여러 번 신고할 수 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리된다. 2. k번 이상 신고된 유저는 게시판 이용이 정지된다. 2-1) 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 보낸다. 2-2) 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송한다. 3. 자기 자신을 신고하는 경우는 없다. 위 규칙을 바탕으로, 유저별로 처리 결과 메일을 받은 ..
[프로그래머스][Python] 가장 먼 노드 문제를 정리해보자. n개의 노드가 있는 그래프가 있다. 각 노드는 1부터 n까지 번호가 적혀있다. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하자. 가장 멀리 떨어진 노드란? 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드이다. 풀이를 생각해보자. 간선에 가중치가 없다. 따라서 N번 노드와 1번 노드의 최단 경로는 간선이 가장 적은 경로이다. 예를 들어, 5번 노드와 1번 노드의 최단 경로는 1 -> 2 -> 5이다. BFS로 최단 경로를 구할 수 있다. 구현해보자. from collections import deque def solution(n, edge): graph = [[] for _ in range(n + 1)] for node in edge: A, B = node[0], node[..
[프로그래머스][Python] 도둑질 문제를 정리해보자. 아래 그림과 같이 집이 동그랗게 배치된 마을이 있다. 도둑은 이 마을을 털 계획이다. 하지만 인접한 두 집을 털면 경보가 울리게 되어 있다. 그래서 도둑은 경보가 울리지 않게 마을을 털 것이다. 각 집에 돈이 담겨 있을 때, 도둑이 훔칠 수 있는 돈의 최댓값을 구하자. 풀이를 생각해보자. 이 문제에서 주의해야 할 점은 2가지이다. 1. 인접한 두 집을 털면 안 된다. 2. 집이 원형 모양으로 배치되어 있다. 위 그림과 같은 마을이 있다고 하자. 첫 번째 집을 방문하면, 두 번째 집과 여섯 번째 집은 방문하지 못한다. 두 번째 집을 방문하면, 첫 번째 집과 세 번째 집은 방문하지 못한다. 다른 집도 마찬가지이다. 집을 1차원상에 두고 생각해보자. 그리고 조건 1을 보자. 두 집이 인접하..

티스토리툴바