본문 바로가기

알고리즘/프로그래머스

[월간 코드 챌린지 시즌2]모두 0으로 만들기, 파이썬 문제 프로그래머스 모두 0으로 만들기 문제 링크 풀이 월간 코드 챌린지 시즌2 1, 2 번은 매우 쉬웠는데 3번에서 런타임에러가 나와서 4번은 풀지도 못했다. 3번이 레벨 3이기 때문에 3번까지는 무난히 풀 수 있어야 한다. 어쨌든 3번은 트리가 주어졌을 때 리프노드부터 탐색할 수 있는지 묻는 문제이다. 주어진 트리의 모든 노드 가중치 합이 0이 아니면 -1을 리턴한다, 0이라면 무조건 답을 구할 수 있다. 트리는 어떤 노드도 루트노드가 될 수 있기 때문에 시작점을 아무거나 잡아도 상관 없지만 길이가 2이상이라 편의상 0을 루트노드로 잡았다. 풀이 1의 경우 재귀를 사용했는데 파이썬은 기본 재귀 횟수를 1000으로 제한한다고 한다. 따라서 a의 최대 길이인 300,000으로 재귀 횟수 제한을 늘려주어야 ..
[프로그래머스] 월간 코드 챌린지 - 스타 수열, 파이썬 문제 프로그래머스 스타수열 링크 풀이 난이도 : 레벨 3 월간 코드챌린지가 뭔지는 모르겠으나 기업 코딩테스트용-스타일 문제는 아니다. 주어지는 배열 a의 최대 길이가 500,000 이기 때문에 O(N^2)으로는 시간초과가 나온다. 부분수열은 순서를 바꿀 수 없기 때문에 순서대로 a 배열을 순환하며 조건에 맞게 딕셔너리에 값을 넣어준 후 나중에 비교하였다. [0, 1, 0, 1]과 같은 순서는 문제 없으나 [0, 1, 1, 0], [1, 1, 0, 1]과 같은 자료는 문제가 될 수 있다. 따라서 위 케이스 등을 고려해서 문제에서 요구한 답을 O(N)으로 구할 수 있도록 코드를 짰다. 코드 from collections import defaultdict def solution(a): N = len(a) if..
2020 카카오 인턴십 - 보석 쇼핑, 파이썬 문제 프로그래머스 카카오 코딩 테스트 문제 링크 풀이 난이도 : 레벨 3 gems 배열 크기는 최대 100,000 이기 때문에 O(N^2)으로 풀면 시간 초과가 난다. 따라서 start, end 두개의 포인터를 조작하는 투포인터 알고리즘을 활용 보석의 종류별로 최소 1개 이상의 수량이 있을 때까지 right를 1씩 더해줌 최소 1개 이상의 수량이 확보되었으면 left를 1씩 움직여가며 중복된 보석을 제거해줌 gems 배열 끝까지 위 단계를 반복해 cand 배열에 넣은 후 구간 길이가 짧고, 같다면 left 크기가 작은 원소를 리턴한다. 코드 from collections import defaultdict def solution(gems): cand = [] left = right = 0 N, gem_nu..
[프로그래머스] 스티커 모으기(2)- 파이썬 문제 프로그래머스 Summer/Winter Coding(~2018) 문제 링크 풀이 난이도 : level 3 예전 문제들은 이렇게 딱 기본 문제로 나온 것 같은데 요즘 추세는 장황한 문제가 나오는 편이다. DP로 풀었다. leet code에서도 비슷한 문제를 좀 더 깔끔하게 푼 풀이를 본 것 같은데 아래 코드는 그다지 깔끔하지는 않다. 원형이기 때문에 첫 번째를 포함하면 마지막 스티커를 포함할 수 없어 케이스를 나누어 계산하였다. dp_y는 포함케이스, dp_n는 불포함 케이스로 계산하여 풀어주었다. dp[idx]는 각 idx 까지의 최대값이다. idx 위치에서 스티커를 포함한다면 그 전단계를 포함하지 못하므로 idx -2 위치의 최대값을 포함, 그렇지 않다면 최대값은 idx -1 위치의 최대값이다. 마..
[프로그래머스]2020 카카오 인턴십- 경주로 건설, 파이썬 문제 ㅍ로그래머스 경주로 건설 문제 링크 풀이 경로문제, 벽이 있는 문제이므로 아래, 위, 오른쪽, 위 4가지 방향으로 모두 움직이는 케이스를 고려해야 한다. 비용은 상하 에서 좌우로 변할 때 600원 상하, 좌우끼리는 100원 소요되므로 상하는 -1, 좌우는 1 값을 넣어 계산해줬다. 다음에 위치할 수 있는 위치(상하좌우로 이동, 0~N 사이의 위치, 벽이 아닌 경우)를 계산한다. check 배열을 만들어 초기값으로 무한을 주고 check 배열에 들어있는 값보다 같거나 작을 경우 큐에 추가해준다. check 배열을 만들지 않으면 무한루프에 빠짐 x == N-1 and y == N-1 마지막에 도달하면 지금까지의 비용을 cand 배열에 넣고 최소값을 리턴한다. 뭔가 좀 지저분하게 푼 것 같은데 나중에 다..
[프로그래머스] Summer/Winter Coding(~2018) - 기지국 설치, 파이썬 문제 프로그래머스 기지국 설치 링크 풀이 레벨 3 예전에 나온 문제들은 확실히 쉬운 편이다. 점점 문제도 길어지고 시간이 걸리는 문제가 나오는 것 같다. 컨디션 난조로 집중이 안돼서 그냥 대충 풀었다. 좀 더 고민하면 깔끔한 코드를 구현할 수 있을 것이다. 코드 def solution(n, stations, w): prev = 0 ans = 0 for i, station in enumerate(stations) : pos = station - w - prev - 1 prev = station + w num = 2*w + 1 if pos % num == 0 : ans += pos//num else : ans += pos//num + 1 if i == len(stations) - 1 and station +..
[프로그래머스]Summer/Winter Coding(~2018)- 숫자 게임, 파이썬 문제 프로그래머스 숫자 게임 문제 링크 풀이 레벨 3 풀이법은 간단하다. 두 배열 모두 정렬을 한 후 A의 가장 큰 값보다 B의 가장 큰 값이 크면 둘다 배열에서 없애주고 ans에 1을 더해준다. 반대로 A의 가장 큰값보다 B에 큰 값이 없다면 점수를 얻을 수 없으므로 B의 가장 작은 값을 날려준다.(그리디) 끝까지 반복하여 ans 리턴 코드 from collections import deque def solution(A, B): ans = 0 A.sort(reverse = True) B.sort(reverse = True) a = deque(A) b = deque(B) for i in range(len(A)) : if a[0] < b[0] : ans += 1 a.popleft() b.popleft() ..
[프로그래머스] 징검다리 건너기- 파이썬, O(n), 모노톤큐 문제 2019 카카오 개발자 겨울 인턴십 문제 링크 풀이 문제 풀이의 핵심은 구간(k)에서의 최대값 중 최소값을 구하는 것 밑에 1번 코드로 짜고 장렬히 효율성에서 털림 이분탐색을 써야하나 싶었는데 왠지 O(n)에 풀릴 것 같았음 결국 검색 후 Monotone Queue 를 찾아내 적용시켜 풀었음 본 문제같은 케이스를 "Maximum window sliding" 문제라고 한다고 한다(추가 정보 필요시 키워드로 검색) 추후에 모노톤 큐에 대한 내용을 정리하기로 하고 일단 간단하게 풀이를 아래 코드에 작성해 놓음 코드 효율성 틀린 초기 코드 k개 연속으로 0이 되면 더이상 건널 수 없음에서 착안 시간 복잡도는 O(k) * O(len(stones) - k) 인데 stones 길이 최대값은 200,000, k도..

티스토리툴바