[프로그래머스] 고득점 kit 정리

 

1. 해시

완주하지 못한 선수

from collections import Counter
def solution(participant, completion):
    answer = ''
    Counter_p = Counter(participant)
    Counter_c = Counter(completion)
    for c in Counter_c:
        Counter_p[c] -= Counter_c[c]
    
    for p in Counter_p:
        if Counter_p[p] > 0:
            answer+= p
    return answer

 

폰켓몬

from itertools import combinations
def solution(nums):
    answer = 0
    MAX_N = len(nums) // 2
    set_nums = set(nums)
    
    if len(set_nums) > MAX_N:
        answer = MAX_N
    else:
        answer = len(set_nums)
    return answer

 

전화번호목록

-> 이중 for문 최대한 지양해야함 ㅠ

효율성 구린 코드

def solution(phone_book):
    answer = True
#     어떤 번호가 다른 번호의 접두어인 경우가 있으면 flase, 그렇지않으면 true

    for i in phone_book:
        if answer == False:
            break
        for j in phone_book:
            len_i = len(i)
            len_j = len(j)
            if i != j and len_i < len_j:
                if j[:len_i] == i:
                    answer = False
                    break
        
                

    return answer

def solution(phone_book):
    answer = True
#     어떤 번호가 다른 번호의 접두어인 경우가 있으면 flase, 그렇지않으면 true
    p_s = sorted(phone_book)

    for i in range(len(phone_book)-1):
        pre = p_s[i]
        # print(pre, phone_book)
        if p_s[i+1][0:len(pre)] == pre:
            answer = False
            break
    return answer

접두사 관점에서 sort 하면 비슷한애들끼리 정렬되기때문에 이걸 이용해도 좋다

 

의상

def solution(clothes):
    answer = 1
    hash_c = {}
    for clothe, categori in clothes:
        if categori not in hash_c:
            hash_c[categori] = 1
        else:
            hash_c[categori] += 1
    for c in hash_c:
        answer *= (hash_c[c]+1) # 옷의 종류 + 안입는 상태
    
    return answer - 1 # 알몸상태 제거

 

베스트 앨범 -> todo

 

---

2. 스택/큐

 

같은 숫자는 싫어

def solution(arr):
    answer = []

    for i in range(len(arr)-1):
        if arr[i+1] != arr[i]:
            answer.append(arr[i])
    answer.append(arr[-1])
    return answer

 

기능개발

• (100 - p + s - 1) // s 형태로 계산해야 작업일수가 올림 처리됨
• 각 작업의 완료일 days를 먼저 계산한 뒤 앞 작업 완료일을 기준으로 배포 여부를 판단해야 함
• 뒤 작업이 더 빨리 끝나면 days[i] <= pre_works 조건으로 같이 배포해야 함

def solution(progresses, speeds):
    answer = []
    
    
    days = []
    for p, s in zip(progresses, speeds):
        days.append((100 - p + s - 1) // s)
        
    works = 1
    pre_works = days[0]
    for i in range(1,len(progresses)):
        if pre_works >= days[i]:
            works += 1
        else:
            answer.append(works)
            works = 1
            pre_works = days[i]
    answer.append(works)
    print(days)
    return answer

 

올바른 괄호

'(' 면 쌓아주고 ')' 면 조건부로

stack = ['(',')'] 되면 스택 비워주기

def solution(s):
    answer = True
    stack = []
    
    for i in s:
        if i == '(':
            stack.append(i)
        else:
            if stack and stack[-1] == '(':
                stack.pop()
            else:
                answer = False
                break
                
    if stack != []:
        answer = False

    return answer

 

프로세스

우선순위 있는지 확인하고 없으면 다시 넣고 반복하기 -> 한번 더 풀어보면 구조 잡힐

• enumerate(arr) 는 (인덱스, 값) 형태로 반환함
• for i, v in enumerate(arr) 에서 i는 인덱스, v는 실제 값임

from collections import deque
def solution(priorities, location):
    answer = 0
    queue = deque()
    for idx,value in enumerate(priorities):
        queue.append([idx,value])
        

    while queue:
        check = False
        queue_idx, queue_pri = queue.popleft()
        for q_idx, q_pri,  in queue:
            if queue_pri < q_pri: # 현재의 프로세스보다 큐 안에 우선순위의 프로세스가 있다면
                check = True

        if check:
            queue.append([queue_idx, queue_pri])
            continue
        else:
            answer += 1
        
        if location == queue_idx:
            return answer
    return answer

 

 

다리를 지나는 트럭

 

주식가격

 

---

3. 정렬

 

K번째 수

def solution(array, commands):
    answer = []
    for i in range(len(commands)):
        start, end, k = commands[i]
        
        new_array = array[start-1:end]
        new_array.sort()
        # print(new_array)
        answer.append(new_array[k-1])
        
    return answer

가장 큰 수 

• sort()는 반환값이 None이라 answer = numbers.sort() 형태로 쓰면 안됨
• x*3은 숫자 곱셈이 아니라 문자열 반복이어야 하므로 map(str, numbers)로 문자열 변환이 필요함
• "3"*3 = "333" 과 "30"*3 = "303030" 형태로 비교하며 문자열은 앞 글자부터 비교하므로 "333"이 더 커서 "3"이 앞에 옴

 

def solution(numbers):

    numbers = list(map(str,numbers))

    answer = sorted(numbers, key=lambda x: x*3, reverse=True) # 문자열 곱하기 비교

    return str(int("".join(answer)))

H-Index

 

---

4. 탐욕법

체육복

def solution(n, lost, reserve):
    answer = 0
    # 바로 앞번호 학생이나 뒷번호 학생한테만 빌려줌
    # 체육 수업을 들을 수 있는 학생의 최댓값
    num_dict = {i:1 for i in range(1,n+1)}
    
    for i in lost:
        num_dict[i] -=1
    for i in reserve:
        num_dict[i] += 1
    # lost의 뒷사람이 체육복이 있는지 확인
    for num in num_dict:
        if num_dict[num] == 0:
            if 1 < num and num_dict[num-1] == 2:
                    num_dict[num-1] -= 1
                    num_dict[num] += 1
                    continue
            elif num < n and num_dict[num+1] == 2:
                    num_dict[num+1] -= 1
                    num_dict[num] += 1
                    continue
    for i in num_dict:
        if num_dict[i] > 0:
            answer += 1
    return answer

 

큰 수 만들기

참고 블로그: https://jjaehyeok.tistory.com/5

 

 

5. BFS/DFS

타겟 넘버

1. solution(numbers, target)의 인자값은 지역변수라서 다른 함수(dfs)에서는 바로 사용할 수 없고, 공유하려면 global 선언이 필요하다.
2. 재귀에서는 idx == len(nums)가 되면 숫자를 전부 사용한 상태이므로 무조건 return으로 종료해야 한다.
3. if idx == len(nums) and value == tg처럼 같이 검사하면 target이 아닐 때 계속 재귀가 돌아 nums[idx] 접근으로 IndexError가 발생할 수 있다.

def solution(numbers, target):
    global nums, tg, answer
    answer = 0
    nums = numbers
    tg = target
    dfs(0,0)
    return answer

def dfs(value,idx):
    global nums, tg, answer
    
    if idx == len(nums):
        if value == tg:
            answer += 1
            return
    else:
        dfs(value + nums[idx], idx + 1)
        dfs(value - nums[idx], idx + 1)

 

 

게임 맵 최단거리

from collections import deque

def solution(maps):
    n = len(maps)
    m = len(maps[0])

    queue = deque([(0, 0, 1)])  # y, x, 거리
    visited = [[False] * m for _ in range(n)]
    visited[0][0] = True

    dy = [0, 0, 1, -1]
    dx = [1, -1, 0, 0]

    while queue:
        qy, qx, dist = queue.popleft()

        if qy == n - 1 and qx == m - 1:
            return dist

        for i in range(4):
            y = qy + dy[i]
            x = qx + dx[i]

            if 0 <= y < n and 0 <= x < m:
                if not visited[y][x] and maps[y][x] == 1:
                    visited[y][x] = True
                    queue.append((y, x, dist + 1))

    return -1

 

 

6. DP

 

7. HEAP