[프로그래머스] - 고득점 Kit 레벨 1~2 문제

곧 이번주말에 유플러스, cns, c&c 코테가 있어서 프로그래머스 고득점 Kit 레벨 1~2 문제를 다시 풀었다.

게임 맵 최단거리

• 사이트/난이도: 프로그래머스 / 2
• 코드

from collections import deque

def solution(maps):
    answer = 0
    n, m = len(maps), len(maps[0])
    bfs(maps, n, m)
    if maps[n-1][m-1] == 1:
        return -1
    return maps[n-1][m-1]

def bfs(maps, n, m):
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    q = deque([])
    q.append((0, 0))
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if maps[nx][ny] == 0:
                continue
            if maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1
                q.append((nx, ny))

• 느낀점
  • 정석적인 bfs문제
  • 모든거리가 1일때 최단거리를 구할꺼면 bfs를 이용하여 손쉽게 구할수 있음

폰켓몬

• 사이트/난이도: 프로그래머스 / 1
• 코드

from collections import Counter

def solution(nums):
    answer = 0
    dic = Counter(nums) # 포켓몬 번호: 포켓몬 개수
    keys = list(dic.keys())
    return len(keys) if len(nums) // 2 >= len(keys) else len(nums) // 2

# 다른 사람 풀이
def solution(ls):
    return min(len(ls)/2, len(set(ls)))

• 느낀점
  • 기본적인 해시 문제
  • 나는 Counter를 이용해서 포켓몬 번호들만 가져와서 더 작은값을 반환하는식으로 했지만 다른 사람 풀이를 보니 그냥 set으로 고유 포켓몬 번호가져오고 배열을 2로나눈 길이와 비교하여 더 작은걸 반환함.

위장

• 사이트/난이도: 프로그래머스 / 2
• 코드

from collections import Counter

def solution(clothes):
    answer = 1
    c = Counter([kind for name, kind in clothes]) # 의상 종류: 의상 개수
    arr = list(c.values())
    for i in range(len(arr)):
        answer = answer * (arr[i]+1) # 모든 경우의 수 = 각 의상별 개수 + 1(안입을 때) 을 계속 곱하고 마지막 -1 (모두 안입을떄)
                    
    return answer-1
#다른 사람 풀이
def solution(clothes):
    from collections import Counter
    from functools import reduce
    cnt = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
    return answer

• 느낀점
  • 알고리즘을 알아야 풀 수 있는 함수
  • 처음에 그냥 조합을 통해 완전탐색으로 풀려니까 1번에서 시간초과가 남
  • 생각해보니 이 문제의 알고리즘은 각 의상별 개수 + 1(안입을 때) 을 계속 곱하고 마지막 -1 (모두 안입을떄) 를 처리하면 답이 나왐
  • 다른사람 풀이도 나와 같은 알고리즘인데 reduce(집계 함수(누적값, 현재값), 순회 가능한 데이터[, 초기값]) 를 사용

전화번호 목록

• 사이트/난이도: 프로그래머스 / 2
• 코드

def solution(phone_book):
    phone_book.sort()
    for i in range(1, len(phone_book)):
        if phone_book[i].startswith(phone_book[i-1]):
            return False
    return True

• 느낀점
  • 시간초과 나서 헤멘 문제…
  • 생각해보니 전화번호는 str이라서 정렬하면 인접한 전화번호들만 검사해도 되서 반복문을 이중으로해서 완탐안해도 된다. ex) 12, 123, 1234, 13 ….
  • 그리고 다른 사람풀이에서 startswith 라는 함수를 알았다. 나는 re.match 를 통해 정규표현식을 이용했는데 시간초과났다…. 이게 더 빠른듯?

같은 숫자는 싫어

• 사이트/난이도: 프로그래머스 / 1
• 코드

def solution(arr):
    answer = []
    for a in arr:
        if not answer:
            answer.append(a)
        if answer[-1] == a:
            continue
        answer.append(a)
    return answer

# 다른 사람 풀이
def no_continuous(s):
    a = []
    for i in s:
        if a[-1:] == [i]: continue
        a.append(i)
    return a

• 느낀점
  • 그냥 기본적인 스택 문제
  • 근데 다른사람풀이에서 a[-1:] 이런식으로 하면 빈배열 처리가 가능하다는 사실을 알게됨

올바른 괄호

• 사이트/난이도: 프로그래머스 / 2
• 코드

def solution(s):
    answer = True
    stack = []
    for i in s:
        if i == "(":
            stack.append(i)
        elif i == ")":
            try:
                stack.pop()
            except IndexError:
                return False
    return len(stack) == 0

• 느낀점
  • 기본적인 스택 문제
  • 나는 pop할떄 예외처리로 안하고 if문 하나 더써서 풀었는데 예외처리도 좋은 방법같음

프린터

• 사이트/난이도: 프로그래머스 / 2
• 코드

from collections import deque

def solution(priorities, location):
    answer = 0
    q = deque([(val, idx) for idx, val in enumerate(priorities)])
    priorities.sort()
    while True:
        val, idx = q.popleft()
        if priorities[-1] == val:
            answer += 1
            priorities.pop()
            if idx == location:
                break
        else:
            q.append((val, idx))
    return answer

• 느낀점
  • 적당한 큐 문제
  • enumerate 를 이용해서 idx, val 값을 구함. 그리고 priorities 를 오름차순 정렬해서 최대값인지 확인했음

다리를 지나는 트럭

• 사이트/난이도: 프로그래머스 / 2
• 코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck_in = deque(truck_weights) # 다리 건너기 전 트럭
    truck_out = deque([]) # 다리를 건넌 트럭
    bridge = deque([0 for _ in range(bridge_length)]) # 다리에 있는 트럭
    total = 0 # 다리에 있는 트럭 무게 총 합
    while len(truck_out) != len(truck_weights):
        out = bridge.popleft()
        total -= out
        if out > 0:
            truck_out.append(out)
        
        if total + truck_in[0] <= weight:
            truck = truck_in.popleft()
            truck_in.append(0)
            bridge.append(truck)
            total += truck
        else:
            bridge.append(0)
            
        answer += 1
    return answer

• 느낀점
  • bridge 에 다리 무게를 넘지 않으면 트럭을 추가하고 넘으면 0을 추가하는게 핵심 알고리즘
  • 그리고 sum 으로 구현해서 다리 위의 트럭 무게 총합을 구하면 시간초과남

주식가격

• 사이트/난이도: 프로그래머스 / 2
• 코드

from collections import deque

def solution(prices):
    answer = []
    queue = deque(prices)
    while queue:
        now = queue.popleft()
        time = 0
        for q in queue:
            time += 1
            if now > q:
                break
        answer.append(time)
        
    
    return answer

• 느낀점
  • prices를 하나씩 앞에서 꺼내서 뒤까지 비교하여 time을 올려주는 알고리즘
  • prices의 최대 길이가 10만인데 이렇게 풀면 $O(n^2)$ 이니까 시간초과 날꺼같은데 안나는 문제.. 머지?

더 맵게

• 사이트/난이도: 프로그래머스 / 2
• 코드

from heapq import heappush, heappop, heapify

def solution(scoville, K):
    answer = 0
    heapify(scoville)
    while len(scoville) > 1 and scoville[0] < K:
        cur = heappop(scoville)
        _next = heappop(scoville)
        result = cur + _next * 2
        heappush(scoville, result)
        answer += 1
    if scoville[0] < K:
        return -1
    return answer

• 느낀점
  • scoville 의 길이가 백만까지 되므로 원소 추가, 삭제 때마다 알아서 정렬해주는 최소힙 이용
  • 여기서 heappop을 두번 하므로 조건문에 길이가 2이상인것을 안해놔서 런타임 에러났었음.

k번째 수

• 사이트/난이도: 프로그래머스 / 1
• 코드

def solution(array, commands):
    answer = []
    for i, j, k in commands:
        arr = array[i-1:j]
        arr.sort()
        answer.append(arr[k-1])
    return answer

• 느낀점
  • 기본적인 정렬 문제

가장 큰 수

• 사이트/난이도: 프로그래머스 / 2
• 코드

def solution(numbers):
    arr = [str(n) for n in numbers]
    arr.sort(key=lambda x: 3*x, reverse=True)
    return str(int(''.join(arr)))

• 느낀점
  • numbers의 원소 크기가 0~ 1000까지 인데 만약 9 랑 991 이랑 원소에 있을때 가장 크게 만들려면 9991 이나와야되는데 9919 가나오므로 3을 곱해줘서 졍렬을 올바르게 해준다.
  • 알고리즘을 떠올리기 힘든 정렬 문제

H-index

• 사이트/난이도: 프로그래머스 / 1
• 코드

def solution(citations):
    answer = 0
    citations.sort(reverse=True) # 내림 차순 정렬
    for i in range(len(citations)):
        if citations[i] < i+1: # 논문 개수가 인덱스보다 작을때, 그 전의 인덱스 값을 리턴
            break
        answer = i + 1
    return answer

• 느낀점
  • 설명이 어려워서 이해하기 힘든 정렬 문제
  • 인덱스 + 1을 h 로 잡아서 해당값과 배열값을 비교하면서 결과 구하기