프로그래머스

프로그래머스: 햄버거 만들기(파이썬, 스택)

파이썬의 index에 접근하는 기능과 스택을 이용하면 쉽게 풀 수 있는 문제이다. 보통 list에서 원소들이 문제 조건에 맞는지 판단하는 문제는 스택, while문, 재귀를 이용하면 풀린다. 이 문제는 원소의 순서가 중요하므로 스택을 이용하여 풀어보았다. 리스트에 원소들을 계속 집어놓고 -index를 이용하여 리스트의 원소끝부터 4번째 원소까지가 [1, 2, 3, 1]이라면 리스트의 원소들을 4번 제거하고 count를 1 증가시키는 방식이다. def solution(ingredient): s = [] cnt = 0 for i in ingredient: s.append(i) if s[-4:] == [1, 2, 3, 1]: cnt += 1 for i in range(4): s.pop() return cnt

프로그래머스: 문자열 나누기 (파이썬, 반복문)

레벨2를 집중적으로 풀던 중 레벨1에 새로운 문제가 추가되어 풀어본 문제이다. 수를 계속 세야하므로 while문, 재귀함수 혹은 stack등 다양한 풀이가 있겠으나 제일 구현하기 쉬운 while문으로 풀어보았다. 문자열이 하나 남는경우만 잘 처리해준다면 까다롭지 않은 문제였던 것 같다. 나는 python의 list slicing을 이용하여 첫번째 문자 x와 x가 아닌 문자들이 갯수가 같아질 때마다 전체 문자열 s를 줄여주고, 문자열이 남은 경우 답을 하나 더해줌으로써 해결하였다. def solution(s): answer = 0 i,j = 0, 1 # cnt1은 첫번째 문자를 카운트하기 위한 용도이므로 미리 1로 지정하고, 반복문 시작구간을 첫번째문자 +1로함 cnt1, cnt2 = 1, 0 while ..

프로그래머스: 전화번호 목록 (파이썬, hash, dictionary)

hash문제이다. 자바에서는 해시값을 사용하는 자료형이 hashmap이고 파이썬에서는 dictionary이다. 내가 푼 문제가 아닌건 블로그에 기록하지 않는데 풀이가 너무 좋아서 내 나름의 수정을 더해 코드와 깨달은 점을 올려본다. 전화번호부가 10^6이기에 완전탐색을 하면 시간복잡도가 O(n^2)이므로 10^12이 되어 시간초과가 날 것 같았다. 따라서 처음에 푼 풀이는 비교하려는 수보다 큰 수일때만 접두사가 될 수 있다는 점, 비교하려는 수보다 값이 커지면 더 비교를 할 필요가 없다는 점을 이용해 반복문에 조건문을 추가하여 탐색을 중간에 멈추게 함으로써 시간복잡도를 nO(logn)으로 만들어 6*10^6으로 풀려고 시도했으나 보기좋게 마지막시도에서 계속 시간초과가 났다. 예를 들어 [121, 83, ..

프로그래머스: 숫자블록 (파이썬, 구현)

프로그래머스에는 약수를 구하는 문제가 꽤 많은데 그 중 한 문제이다. 길의 길이는 10^9이고 블록의 길이는 최대 10^7이기에 완전탐색을 하면 틀리는 문제이다. 약수를 효율적으로 구하는 것이 문제의 핵심인데 약수는 일일이 나눠서 구해야하므로 완전탐색으로 구해야하고, 더 빠르게 구하려면 약수는 제곱근 전 후로 쌍을 이룬다는 성질을 응용하여 제곱근까지만 약수를 구하고 그 약수들로 수를 나누어 나머지 약수들을 찾아야 한다. 먼저 내가 푼 코드이다. from bisect import bisect_left def get_yaksu(num): # 1은 모든 수의 약수 yaksu = [1] # 제곱근까지 약수를 구함 으로써 탐색 범위를 줄임 for i in range(2, int(num**0.5)+1): if nu..