해시
001 완주하지 못한 선수
문제설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한 사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
입출력 예제
|participant|completion|return|
|—|—|—|
|["leo", "kiki", "eden"]|["eden", "kiki"]|"leo"|
|["marina", "josipa", "nikola", "vinko", "filipa"]|["josipa", filipa", "marina", "nikola"]|"vinko"|
|["mislav", "stanko", "mislav", "ana"]|["stanko", "ana", "mislav"]|"mislav"|
코드
def solution(participant, completion):
participant.sort() # nlog(n)
completion.sort() # nlog(n)
for p, c in zip(participant, completion):
if p != c:
return p
return participant[-1]코드 설명
- "completion의 길이는 participant의 길이보다 1 작습니다."의 조건이 있기 때문에 두 리스트를 정렬해서 나열할 경우 일치하는 이름이 있을경우 서로 같은 인덱스를 공유하는 형태를 가지게 된다.
- 정렬된 나란한 리스트 둘을 zip()함수를 이용해 묶게 되면 명단에 누락이 발생하지 않을 경우 같은 요소가 담기게 된다.
- 반복문으로 한 요소씩 가져와서 둘을 비교하는 조건을 걸어주고 요소가 같지 않을 경우 참가 명단에는 있지만, 완주는 하지 못했다는 의미가 되므로 participant 의 요소를 가져오는 p를 반환해준다.
- 반복문이 종료될 때 까지 조건문을 만족하는 요소가 없을 경우 정렬된 참가명단에서 가장 마지막에 서로 매칭이 되지 않은 참가자가 완주하지 못한 선수를 의미하므로 participant[-1]로 리스트의 마지막 요소를 반환해준다.
다른 사람의 풀이
import collections
def solution(participant, completion):
answer = collections.Counter(participant) - collections.Counter(completion)
return list(answer.keys())[0]002 전화번호 목록
문제설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한 사항
- phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
입출력 예제
|phone_book|return|
|—|—|
|["119", "97674223", "1195524421"]|false|
|["123", "456", "789"]|true|
|["12", "123", "1235", "567", "88"]|false|
코드
def solution(phone_book):
phone_book.sort()
for i in range(len(phone_book) - 1):
if phone_book[i] in phone_book[i + 1]:
return False
return True코드 설명
- phone_book 리스트의 모든 요소가 서로를 문자열의 접두어로 포함하지 않을 경우 True를 반환하고, 포함하는 경우가 하나라도 있을 경우 False를 반환하도록 하는 코드
- 모든 요소를 순회하면서 검사하지 않도록 사전에 정렬한 뒤 앞 뒤 요소를 비교하는 방법으로 반복횟수를 줄입니다.
다른 사람의 풀이
def solution(phoneBook):
phoneBook = sorted(phoneBook)
for p1, p2 in zip(phoneBook, phoneBook[1:]):
if p2.startswith(p1):
return False
return True003 위장
문제설명
스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
|종류|이름|
|—|—|
|얼굴|동그란 안경, 검정 선글라스|
|상의|파란색 티셔츠|
|하의|청바지|
|겉옷|긴 코트|
스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
- clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
- 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
- 같은 이름을 가진 의상은 존재하지 않습니다.
- clothes의 모든 원소는 문자열로 이루어져 있습니다.
- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
- 스파이는 하루에 최소 한 개의 의상은 입습니다.
입출력 예
|clothes|return|
|—|—|
|[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]|5|
|[["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]|3|
코드
def solution(clothes):
answer = 1
category = dict()
for value, key in clothes:
if category.get(key) is None:
category[key] = []
category[key].append(value)
else:
category[key].append(value)
for key in category:
answer *= len(category[key]) + 1
return answer - 1코드 설명
- 같은 카테고리의 의상으로 key-value 형태의 dictionary를 만들어 줍니다.
- 각 카테고리(key)에 '옷을 입지 않는 경우'가 되는 아무것도 없는 경우를 추가해서 각 카테고리(key)가 가질 수 있는 경우를 모두 곱해준다. → 해당 카테고리를 착용하지 않는 경우가 포함된 모든 조합의 경우의 수를 알 수 있다. (
answer *= len(category[key]) + 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스택/큐
001 주식가격
문제설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
- prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
- prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
|prices|return|
|—|—|
|[1, 2, 3, 2, 3]|[4, 3, 1, 1, 0]|
코드
def solution(prices):
answer = []
for i in range(len(prices) - 1):
count = 0
j = i + 1
while j < len(prices):
count += 1
if prices[i] > prices[j]:
break
j += 1
answer.append(count)
answer.append(0)
return answer코드 설명
- 해당되는 각 시점의 주식가격이 몇 초동안 하락하지 않는지 (같거나 큰 경우) 시간을 정답 리스트에 기록하는 문제
- 순차적으로 리스트의 요소에 접근하는 첫번째 반복문
for i in range(len(prices) - 1):, 다음 요소와의 비교를 위해 전체길이 보다 1 작은 요소까지 접근 - 비교될 다음 요소를 증가시킬 반복문 내부의 반복문
while j < len(prices):, j는 i + 1 지점부터 리스트의 마지막 요소까지 순회- 반복문 내부에서 기준이 되는 i 인덱스의 요소가 비교되는 j 인덱스 요소보다 커지는 순간 반복문을 탈출하고 그때까지 증가된 count를 answer리스트에 append 해준다.
- 마지막 요소는 순회를 돌지 않도록 설계 되었으므로(동시에 비교되는 다음 요소가 없으므로 자동으로 count는 0이 되므로 answer리스트의 마지막에는 무조건 0을 추가해준다.
다른 사람의 코드
from collections import deque
def solution(prices):
answer = []
prices = deque(prices)
while prices:
c = prices.popleft()
count = 0
for i in prices:
if c > i:
count += 1
break
count += 1
answer.append(count)
return answer002 기능개발
문제설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
입출력 예
|progresses|speeds|return|
|—|—|—|
|[93, 30, 55]|[1, 30, 5]|[2, 1]|
|[95, 90, 99, 99, 80, 99]|[1, 1, 1, 1, 1, 1]|[1, 3, 2]|
코드
def solution(progresses, speeds):
answer = []
length = len(progresses)
for i in range(length):
progresses[i] = 100 - progresses[i]
days = 1
while progresses[i] > speeds[i] * days:
days += 1
progresses[i] = days
print(progresses)
start = 0
while start < length:
end = start + 1
while end < length:
if progresses[start] >= progresses[end]:
end += 1
else:
break
answer.append(end - start)
start = end
return answer코드 설명
- progresses리스트의 요소는 각 작업의 진척도를 완료된 상태(100)을 기준으로 나타냄
- 각 요소를 순회하면서
100 - progresses[i]를 적용한 값으로 남은 작업량으로 대체 - 동시에 남은 작업량을 해당 작업의 작업속도로 작업할 때 완료되는데 걸리는 시간으로 계산해서 요소로 대체
- 결과, 기존의 progresses 리스트는 각 순번의 작업이 완료되는데 걸리는 시간을 담게 됨
- progresses 리스트의 각 요소에 순차적으로 접근 : start → end 까지
progresses[start] >= progresses[end]를 만족하면 end를 한자리씩 뒤로 밀어가면서 비교해준다. 조건을 만족하지 않는 시점에 반복문을 탈출하게 되며, 그 때 end 값에서 start를 빼준 값이 start 작업이 완료되는 시점에 동시에 완성되는 작업의 수가 된다. - 마지막으로 변화된 end의 이전 값 까지 작업이 완료되었으므로, 이후의 작업을 비교하기 위해 start를 end 값으로 초기화 시켜주고 위의 과정을 반복해준다.
다른 사람의 풀이1
def solution(progresses, speeds):
Q=[]
for p, s in zip(progresses, speeds):
if len(Q)==0 or Q[-1][0]<-((p-100)//s):
Q.append([-((p-100)//s),1])
else:
Q[-1][1]+=1
return [q[1] for q in Q]무슨 코드인지 이해를 못하겠습니다. python을 한 동안 안썼더니 기본문법을 다 잊어버렸습니다...
다른 사람의 풀이2
def solution(progresses, speeds):
print(progresses)
print(speeds)
answer = []
time = 0
count = 0
while len(progresses)> 0:
if (progresses[0] + time * speeds[0]) >= 100:
progresses.pop(0)
speeds.pop(0)
count += 1
else:
if count > 0:
answer.append(count)
count = 0
time += 1
answer.append(count)
return answer정렬
001 K번째수
문제설명
배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.
예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면
- array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
- 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
- 2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- array의 길이는 1 이상 100 이하입니다.
- array의 각 원소는 1 이상 100 이하입니다.
- commands의 길이는 1 이상 50 이하입니다.
- commands의 각 원소는 길이가 3입니다.
입출력 예
|array|commands|return|
|—|—|—|
|[1, 5, 2, 6, 3, 7, 4]|[[2, 5, 3], [4, 4, 1], [1, 7, 3]]|[5, 6, 3]|
코드
def solution(array, commands):
answer = []
for i, j, k in commands:
split_array = array[i - 1:j]
split_array.sort()
answer.append(split_array[k - 1])
return answer코드 설명
- 없음
다른 사람의 코드
def solution(array, commands):
return list(map(lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1], commands))- 람다를 이용한.. 숏코딩
002 가장 큰 수
문제설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한사항
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
입출력 예
|numbers|return|
|—|—|
|[6, 10, 2]|"6210"|
|[3, 30, 34, 5, 9]|"9534330"|
코드
# 진행중- 첫번째 시도 → 삽입정렬 → time out
- 두번째 시도 → 라이브러리 순열 함수 → time out
- 세번째 시도 → 거꾸로된 Radix 정렬 → 진행중...
'Temp' 카테고리의 다른 글
| 20210216, Netwhat 단계별로 밟아가기 (IP ~ OSI 7 Layer) (0) | 2021.02.17 |
|---|---|
| 20210206, 프로그래머스 문제 (0) | 2021.02.08 |
| 20210204, 프로그래머스 문제 - 스택/큐 (0) | 2021.02.08 |
| 20210203, Network (1) (0) | 2021.02.08 |
| 20210201, 프로그래머스 문제 (0) | 2021.02.02 |