문제오늘 날짜가 주어지고, 약관에 따라 개인정보의 유효기간이 지나 파기해야 하는 개인정보의 번호를 리스트로 출력하는 문제이다. 풀이약관에 따라 유효기간이 다르고 개인정보가 수집된 날짜가 다르기 때문에 만료 기간을 계산하여 오늘 날짜와 비교하면 된다.먼저 약관의 정보는 빠른 속도로 불러오기 쉽도록 dictionary에 담는다.날짜를 일수로 변환하는 to_days 함수를 통해 날짜를 비교한다.(주의) 개인정보 수집 날짜와 약관 유효기관을 더한 일수에 1을 빼어야 유효기간 만료일이다. Python 코드# 날짜를 일수로 변환def to_days(date): y, m, d = map(int, date.split(".")) return y*12*28 + m*28 + ddef solution(today, ..
문제NxM 크기의 격자 미로 안에서 출발지 (x, y)에서 도착지 (r, c)로 가는 경로를 알파벳으로 표기했을 때, 사전 순으로 가장 빠른 경로를 찾는 문제이다.미로를 탈출하기 위해서 이동하는 거리는 k여야 한다. ( 이동거리 = 이동 횟수 = 경로 문자열 길이 )경로는 u(상), d(하), l(좌), r(우) 로 표현 가능하며 사전 순으로 가장 빠른 경로를 선택한다. 풀이깊이 우선 탐색(DFS) 알고리즘을 활용하여 경로를 찾을 수 있다.DFS 알고리즘은 LIFO(Last In First Out)의 특징을 갖고 있기 때문에 사전순으로 앞서는 알파벳을 뒤에서 탐색한다면 항상 사전순으로 빠른 문자열을 먼저 탐색할 수 있다.탐색 방향을 u, r, l, d 순으로 설정한다.한 노드에서 상하좌우로 이동할 때 u..
틀렸던 문제는 두 수의 합과 유사하지만 조금 더 복잡한 문제였다. 먼저 기초가 되는 두 수의 합 문제를 풀어보면서 응용할 수 있도록 공부해서 다음엔 풀 수 있도록 연습하자. 문제 두 수의 합 문제는 다음과 같다. n개의 정수로 이루어진 수열이 입력되었을 때, 서로 다른 위치의 두 수를 뽑아 더한 값이 k가 되는 경우의 수를 구하는 문제이다. 풀이 모든 두 수 조합을 비교하는 것은 매우 시간이 오래 걸린다. 딕셔너리에 중복 값을 넣어주고, 중복 값을 제외한 뒤 비교하는 것도 마찬가지로 시간이 오래 걸린다. 5달 전에도 같은 문제를 풀었는데 습관처럼 위와 같은 방법을 사용했었다. 하지만 앞의 숫자부터 k값을 만들 수 있는 짝꿍이 있는지 비교하면서 경우의 수를 세어주는 것이 가장 빠른 방법이다. 이번엔 머릿속..
문제주어진 용액들 중에서 세 개를 선택해 특성 값의 합이 0에 가까운 조합을 찾는 문제이다.풀이정렬과 투 포인터 기법을 활용해 문제를 풀 수 있다.먼저 주어진 용액들의 정보를 오름차순으로 정렬하면 더 효율적으로 조합을 찾을 수 있다.세 개의 용액 중 한개를 임의로 고정하고 나머지 두 용액을 투 포인터로 탐색한다.첫번째 포인터(left)는 고정된 용액 바로 다음 위치를 가리킨다.두번째 포인터(right)는 정렬된 배열의 최대값인 오른쪽 끝을 가리킨다.세 원소의 합이 0보다 크면 오른쪽 포인터를 왼쪽으로 이동시켜 더 작은 값을 선택하게 한다.합이 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동시켜 더 큰 값을 선택하게 한다.만약 0과 같으면 해당 조합이 최고의 조합임으로 해당 조합을 저장하고 탐색을 종료할 수..
문제차량의 입출차 기록을 통해 차량별 주차요금을 계산하는 문제이다.주차요금은 요금표를 기준으로 기본 시간에 대한 기본 요금을 부여하고 초과한 경우 단위 시간당 당위 요금이 추가된다.초과한 시간이 단위 시간으로 나누어 떨어지지 않는다면 올림으로 계산한다.풀이입차와 출차가 겹치는 경우가 없고, 입차와 출차 순서가 뒤집히는 경우도 없기 때문에 순차적으로 계산하기만 하면 간단히 주차 시간을 계산할 수 있다.출차 시간에서 입차 시간을 뺀 값이 주차 시간임으로 총 주차 시간을 계산할 때 차량별로 입차 시간은 빼주고, 출차 시간은 더해주면 된다.출차 기록이 없는 경우에는 23:59분으로 가정하고 계산해야 한다.이때 차량의 주차 시간을 통해 출차 기록이 없다는 것을 판단할 수 있다.입차 시간이 00:00 일 때는 주차..
문제두 수열이 주어졌을 때 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하는 문제이다. 여기서 부분 수열이란 것은 어떤 수열에서 원래 순서를 유지하면서 일부 원소를 선택하여 만들어진 새로운 수열을 말한다.풀이A, B 두 개의 수열이 주어졌을 때 공통되는 부분 수열을 구해야 한다. 따라서 set을 사용하여 A와 B 수열의 공통되는 숫자를 선별한다.만약 공통되는 숫자가 없다면 0을 출력하고 종료하면 된다.부분 수열들 중 사전 순으로 가장 나중인 것을 구하는 것이기 때문에, 공통 숫자들 중 가장 큰 숫자(max_val)를 뽑아 result에 담는다.부분 수열은 원래 수열의 순서를 유지하면서 선택돼야 하므로, A와 B 각각의 수열에서 max_val의 위치를 찾아 해당 위치 이후의 수열로 업데이..
[프로그래머스 / Python] 크레인 인형뽑기 게임
문제인형 뽑기 게임을 진행하면서 몇 개의 인형이 사라졌는지 출력하는 문제이다.크레인이 작동한 위치에 따라 인형을 집어 올리고, 바구니(stack)로 이동하면서 인형이 연속되면 제거하여 사라진 인형 개수를 구한다.풀이2차원 배열과 스택을 활용해 문제를 풀 수 있다.크레인을 작동시킨다.move 위치에서 맨 위쪽부터 즉 row가 작은 순으로 탐색한다.인형이 있는 경우 인형 정보를 저장하고 board는 빈칸(0)으로 만든다.동일한 인형일 경우 인형을 제거한다.새로 뽑은 인형의 정보와 basket에 담긴 마지막 인형이 동일하다면 마지막 인형을 제거하고 count에 2를 더한다.만약 동일한 인형이 아니라면 뽑은 인형을 basket에 담는다.count 된 숫자를 return 한다.Python 코드def solutio..