본문 바로가기

알고리즘/프로그래머스

[프로그래머스]월간 코드 챌린지 시즌1- 풍선 터트리기, 파이썬 문제 프로그래머스 문제 링크 풀이 시간초과를 생각하지 않고 짜다 오래걸렸다(문제를 잘 읽고 풀자 ㅠ) 양 끝은 최후까지 남기는 것이 가능하다([1, 2] 라 했을 때 한 번 작은걸 터트릴 수 있는 기회로 1을 날려버리면 됨) 위 가정을 하기 위해서는 2개 남기기 전까지는 무조건 큰 수를 제거해야 함을 알 수 있다. 예시로 주어진 [-16, 27, 65, -2, 58, -92, -71, -68, -61, -33] 을 보자 따라서 27은 제거되어야 하기 때문에 양 극단이 될 수 없다 = -16보다 작은 수가 왼쪽 끝이 될 자격이 있고 오른쪽도 마찬가지 논리로 적용 [-16, ~], [-92, ~], [~, -92], [~, -71], [~, -68], [~, -61], [~, -33] 이 가능하다. 양쪽 방..
2020 KAKAO 코딩테스트- 외벽 점검, 파이썬 문제 프로그래머스 문제 링크 풀이 필요역량 레벨 3 Brute force, permutation 정렬하고 간격으로 어떻게 풀어보려다 결국 테스트케이스에 실패, 다른 코드를 참고했다. weak 배열 크기도 작고, dist 배열 크기도 작기 때문에 완전탐색으로 문제를 풀 수 있다 (=쉽게 푼다고 머리만 쓰고 틀리지 마라) 파이썬 순열 : from itertools import permutations 파이썬 순열 라이브러리 몰라서 새로 짜서 썼다. (= 어리석음) 배워가야할 부분은 1. 완전탐색이 가능하면 단순하게 완전탐색으로 일단 풀자. 2. 원형으로 주어진 자료를 선형으로 풀자. 코드 풀이는 아래 주석으로 달아놓았다. 코드 from itertools import permutations def solutio..
[프로그래머스] 그리디 - 단속카메라, 파이썬 문제 프로그래머스 문제 링크 routes 배열에 각 차량의 진입, 진출 시점이 주어지는데 모든 차량을 감시할 수 있는 최소 카메라의 수를 리턴하는 문제 풀이 요구역량 레벨 3 그리디(아이디어) 프로그래머스에는 그리디 알고리즘 문제로 분류되어 있다. 그리디 알고리즘은 각 단계에서 최선의 선택(논리적으로 합당한)을 이어나가며 문제를 해결하는 방법인데 아이디어가 떠오르면 쉽게 풀리는 경우가 있다. 주어진 routes 배열을 진출시점(=진출 위치, 좌표로 판단)을 기준으로 정렬해 준 후 체크되지 않은 첫 번째 차량의 진출위치를 camera 변수에 담아준다. (모든 차량을 체크해야 하기 때문에 가능한 뒤쪽에 카메라를 설치하는 선택 = 그 시점에서의 최선의 선택) 해당 카메라 위치 전에 진입하는 차량들은 모두 패스..
[프로그래머스] N으로 표현, 파이썬 문제 프로그래머스 링크 풀이 요구 능력 레벨 3 DP라고 하지만 아이디어, 구현 틀려서 답을 참조해서 다시 푼 문제이다. "최솟값이 8보다 크면 -1을 return 합니다" 라는 조건이 있기 때문에 모든 케이스를 고려할 수 있다는 힌트를 얻을 수 있다. 예시 "12 = 55 / 5 + 5 / 5" 에서 볼 수 있듯 사칙연산에 더해 고려해야 할 것은 55가 연속으로 쓰인 부분. N이 5라면 5, 55, 555, 5555, 55555 등을 중심으로 문제를 풀어나갈 수 있다. 따라서 아래 코드로 문제를 풀었다. 코드 def solution(N, number): # 만약 N이 5라면 case는 [{5}, {55}, {555}, {5555}, {55555}, {555555}, {5555555}, {55555555..
[프로그래머스] 해시 - 베스트앨범, 파이썬 문제 프로그래머스 링크 풀이 요구 능력 레벨 3 해시, 딕셔너리, 정렬 문제의 요구사항을 따라가다보면 그다지 어려운 문제는 아니다. 다만 주의해야할 점은 파이썬 딕셔너리에서 sort()를 제공하지 않아 정렬을 위해 내장함수인 sorted()를 사용해야한다. 왜지?? 라는 생각이 들텐데 위에 대한 내용은 시간여유가 있으면 정리해봐야겠다. (= 시간이 없어 대충 풀어제낌 ㅠ) 밑에 코드는 좀 더 깔끔하게 정리 가능하다.(= 지저분하단 소리) 코드 from collections import defaultdict def solution(genres, plays): answer = [] dic_lst = defaultdict(list) dic_n = defaultdict(int) arr = [] # dic_n 딕..
[프로그래머스] 그리디 - 큰 수 만들기, 파이썬 문제 문제 링크 number 문자열이 주어지고 자연수 k가 주어질 때 k 개의 문자를 제거한 가장 큰 수를 문자열로 리턴해야 하는 문제이다. 풀이 레벨 2 스택, 문자열 처리 어려운 편은 아니지만 시간초과가 나올 수 있으며 테스트케이스 12번이 틀릴 수 있다.(Part 2 참조)Part 1 우선 문자열을 arr 배열에 담아준다. 반복문을 돌며 만약 stack이 비어있지 않고 stack의 마지막 원소가 지금 문자열의 수보다 작으면 while문으로 들어간다. 이때 k가 0보다 크고(제거할 문자열이 있고) stack에 문자열이 있고 stack의 마지막 원소가 지금 문자열보다 작으면 stack의 마지막 원소를 제거해준다. 이렇게 할 때 k가 0보다 클 때 stack은 내림차순으로 정렬된다. 큰 수를 위해서는 높..
프로그래머스 - 순위, 파이썬 문제 프로그래머스 링크 풀이 그래프 문제에 속해있지만 해쉬로 풀 수 있는 문제 파이썬 내장모듈인 Collections 의 defaultdict 클래스를 활용하였다. 굳이 활용하지 않아도 되지만 파이썬의 딕셔너리의 경우 키 값이 없으면 에러가 나서 귀찮기 때문이다. defaultdict 클래스를 활용하면 defaultdict(set)의 경우 모든 키에 대해서 값이 없는 경우 자동으로 인자로 넘어온 함수를 호출하여 그 결과값으로 설정해준다. 순위를 정하는 문제이기 때문에 a에게 진 선수들, a를 이긴 선수들을 각각 딕셔너리로 저장해준다.(중복을 피하기 위해 set 자료형 활용 선수 수만큼 반복문을 돌면서 a에게 진 선수들은 a를 이긴 선수들에게도 모두 지고, a를 이긴 선수들은 a가 이긴 선수들을 모두 이긴..
2018 KAKAO BLIND RECRUITMENT - n진수 게임, 파이썬 문제 프로그래머스 n진수 게임 요구 능력 레벨 2 진수 변환에 대한 구현 풀이 그다지 어렵진 않았다고 하기엔 다른 풀이들이 너무 간단했다. 더 최적화가 가능할 것도 같다. 프로그래머스 문제는 2단계는 건너 뛰고 5단계는 제끼고(..) 3, 4 단계 문제만 풀도록 해야겠다. 코드는 읽어보면 어렵지 않게 이해할 수 있기 때문에 코드 설명은 생략 코드(파이썬) def change_base(n, base) : s = "0123456789ABCDEF" ans = '' while n // base > 0 : ans = s[n % base] + ans n = n // base ans = s[n % base] + ans return ans def solution(n, t, m, p): answer = &..

티스토리툴바