방구석프로의 이야기

https://school.programmers.co.kr/learn/courses/30/lessons/12906

문제 해결을 위한 과정

이 문제는 배열의 길이 1,000,000 이므로 이중 For문이 아닌 단일 for문으로 해결해야 합니다.
현재 인덱스와 다음 인덱스를 비교해서 다른 경우에만 answer 리스트에 append 해주는 식으로 쉽게 해결할 수 있습니다.

소스코드

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

https://school.programmers.co.kr/learn/courses/30/lessons/42626

문제 해결을 위한 과정

이 문제는 heapq를 이용하면 쉽게 해결할 수 있는 문제였습니다. 매번 정렬을 한다면 효율성의 문제가 생길 수 있으므로 최소힙을 이용해 O(logN)으로 가장 작은 값을 꺼내면 됩니다. 이 때 2개씩 꺼내어 더 맵게 하는 과정을 거치는데 q의 길이가 1이라면 두번을 꺼낼 수 없으므로 예외처리를 따로 해주시면 됩니다.

소스코드

import heapq

def solution(scoville, K):
    answer = 0
    q = []
    for i in range(len(scoville)):
        heapq.heappush(q, scoville[i])
    while True: 
        if len(q) >= 2:
            num1 = heapq.heappop(q)
            num2 = heapq.heappop(q)
        elif len(q) == 1:
            num1 = heapq.heappop(q)
            if num1 < K:
                answer = -1
                break
        if num1 >= K:
            break
        answer += 1
        heapq.heappush(q, (num1 + num2 * 2))
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42579

문제 해결을 위한 과정

이 문제는 딕셔너리를 사용하면 쉽게 해결할 수 있었습니다. 장르를 키, 횟수를 값으로 하면 다음과 같습니다. 

classic: 1450, pop: 3100. 이때 전체의 genres 및 plays 리스트를 조회하면서 temp 리스트에 장르별 전체 재생 횟수, 고유번호, 노래재생 횟수를 넣습니다. 이렇게 되면 다음과 같습니다.

temp = [(1450, 3, 800), (3100, 1, 600), (1450, 2, 150), (1450, 3, 800), (3100, 4, 2500)] 

이 temp를 재생횟수 내림차순 - 같으면 곡 재생 횟수 내림차순 - 같으면 고유번호 오름차순으로 정렬을 합니다. 그렇게 되면 다음과 같이 됩니다.

temp = [(3100, 4, 2500), (3100, 1, 600), (1450, 3, 800), (1450, 0, 500), (1450, 2, 150)]

이후 각 장르별로 두 곡씩 answer에 담아서 return 하면 됩니다.

소스코드

def solution(genres, plays):
    answer = []
    music_dict = {}
    temp = []
    for i in range(len(genres)):
        if genres[i] not in music_dict:
            music_dict[genres[i]] = plays[i]
        else:
            music_dict[genres[i]] += plays[i]
    
    for i in range(len(genres)):
        temp.append((music_dict[genres[i]], i, plays[i]))
    
    temp.sort(key = lambda x: (-x[0], -x[2], x[1]))
    gen = {}
    for i in range(len(temp)):
        if temp[i][0] not in gen:
            gen[temp[i][0]] = 1
            answer.append(temp[i][1])
        elif temp[i][0] in gen:
            if gen[temp[i][0]] == 1:
                gen[temp[i][0]] += 1
                answer.append(temp[i][1])
            else:
                continue
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/86491

문제 해결을 위한 과정

이 문제는 sizes 배열의 각 행마다 정렬을 해준 뒤 가로, 세로 최댓값을 구하면 쉽게 해결할 수 있는 문제였습니다.

def solution(sizes):
    answer = 0
    for i in range(len(sizes)):
        sizes[i].sort()
    maxA = 0
    maxB = 0
    
    for a, b in sizes:
        maxA = max(maxA, a)
        maxB = max(maxB, b)
    answer = maxA * maxB
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/1845

문제 해결을 위한 과정

이 문제는 해시를 이용하면 쉽게 풀 수 있는 문제였습니다. 각 폰켓몬들을 딕셔너리에 추가해 주고 n/2보다 딕셔너리의 수가 크거나 같다면 n/2를, 그렇지 않다면 딕셔너리의 수를 return 해주면 되는 문제입니다.

소스코드

def solution(nums):
    answer = 0
    pocket_dict = {}
    for i in range(len(nums)):
        if nums[i] not in pocket_dict:
            pocket_dict[nums[i]] = 1
        else: 
            pocket_dict[nums[i]] = 1
            
    if len(nums)//2 <= len(pocket_dict): 
        answer=len(nums)//2
    else: 
        answer=len(pocket_dict)
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42578

문제 해결을 위한 과정

이 문제는 가장 쉽게 해결 방법을 떠올릴 수 있는 건 이중 for문이다. 그러나 이중 for문을 사용하면 phone_book의 길이는 1 이상 1,000,000 이하입니다.라는 조건 때문에 최대 1,000,000 * 1,000,000 = 1,000,000,000,000 1조 번의 연산을 수행하면 이는 시간 초과 (TLE)로 이어진다.(파이썬은 1초에 20,000,000번 연산 가) 따라서 TLE를 받지 않기 위해서는 이중 for문이 아닌, Hash를 사용하여 단일 for문으로 풀어야 함을 알 수 있다. 각각을 조회하며 각 번호가 접두사로 존재하는지 확인하고, 번호 전체를 Hash에 등록해 주면 된다. (소스코드 참고) 

단, 이때 예외케이스가 발생할 수 있는데 바로 정렬의 문제이다. ["1192345", "119"]로 phone_book이 있다면 이를 정렬하여 ["119", "1192345"]로 정렬을 한 뒤 진행해야 한다. 그렇지 않다면 위 경우는 True를 return하며 이는 오답이 될 것이다.

 소스코드

def solution(phone_book):
    answer = True
    phone_dict = {}
    phone_book.sort()
    for i in range(len(phone_book)):
        for j in range(1, len(phone_book[i]) + 1):
            if phone_book[i][:j] in phone_dict:
                return False
        if phone_book[i] not in phone_dict:
            phone_dict[phone_book[i]] = 1
        
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42578

문제 해결을 위한 과정

이 문제의 경우 dict를 이용하면 쉽게 해결할 수 있었습니다. 얼굴(1번 용품, 2번 용품), 상의(1번 용품, 2번 용품), 하의(1번 용품) 이렇게 있을 때 입는 경우는 다음과 같습니다.

얼굴(1번 용품, 2번 용품, 아무것도 안 입는 경우) - 3가지

상의(1번 용품, 2번 용품, 아무것도 안입는 경우) - 3가지

하의(1번 용품, 아무것도 안 입는 경우) - 2가지

결과 =  3 x 3 x 2 - 1(아무것도 안 입는 경우)

이를 일반화 하면 다음과 같습니다.

(얼굴 + 1) * (상의  + 1) * (하의 * 1) - 1

소스코드

def solution(clothes):
    answer = 1
    cloth_dict = {}
    for name, type in clothes:
        if type in cloth_dict:
            cloth_dict[type] += 1
        else:
            cloth_dict[type] = 1
    for name, type in clothes:    
        if cloth_dict[type] != 0:
            num = cloth_dict[type]
            cloth_dict[type] = 0
            answer *= (num + 1)
    answer -= 1
    return answer

https://programmers.co.kr/learn/courses/30/lessons/92334

문제 해결을 위한 과정

문제의 범위에서 알 수 있듯이 단순하게 리스트를 이용하여 해결하면 시간 초과 판정을 받는 문제였습니다. 따라서 dictionary를 이용하여 해결해야 합니다.

소스코드

def solution(id_list, report, k):
  report = list(set(report))
  rCount = {string:0 for string in id_list}
  answer = {string:0 for string in id_list}
  for temp in report:
    user, rUser = temp.split()
    rCount[rUser] += 1

  for temp in report:
    user, rUser = temp.split()
    if rCount[rUser] >= k:
      answer[user] += 1

  ans = list(answer.values())
  return ans