CS/Algorithm 문제
[Programmers] 주식가격
[Programmers] 주식가격 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42584 💬설명 for문을 두번 돌면 되는 문제 처음부터 끝까지 돌면서 각각에 대해 뒤에 있는 price들을 체크해준다. 데이터 크기도 그렇게 크지 않고 O(nlogn)에 풀수 있어서 효율성도 통과했다. 스택으로 풀면 시간이 더 단축된다. (두번째 풀이) (약 100ms -> 약 20ms) 👩💻코드 def solution(prices): answer = [] for index, price in enumerate(prices): answer.append(0) for i in range(index + 1, len(prices)): answer[-1] += 1 if price..
[Programmers] 다리를 지나는 트럭
[Programmers] 다리를 지나는 트럭 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42583 💬설명 처음에 다리 길이 만큼 [0, 0, ... 0] 이렇게 만들어주고 트럭이 올라가고 지나가는 것을 pop과 append로 구현해줬다. 입출력이 순서가 있는 문제이므로 스택/큐 문제! 👩💻코드 def solution(bridge_length, weight, truck_weights): answer = 0 bridge = [0 for _ in range(bridge_length)] weight_sum = 0 while bridge: answer += 1 weight_sum -= bridge.pop(0) # 다음 대기 트럭이 올라갈 수 있는지 무게 체..
[Programmers] 프린터
[Programmers] 프린터 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42587 💬설명 문제에 나와있는대로 그대로 구현하면 되는 문제 인쇄에 순서가 있어서 스택/큐 문제라고 생각했다. 과정은 다음과 같다. 문서를 앞에서부터 하나씩 뽑음 (while문) 지금 뽑은 문서가 최대값이라서 인쇄대상인 경우 만약 해당 문서가 내가 인쇄를 요청한 문서인 경우 누적된 횟수값 리턴후 종료 만약 해당 문서가 내가 인쇄를 요청한 문서가 아닌 경우 요청한 문서 위치값 update 지금 뽑은 문서가 최대값이 아니어서 뒤로 넘겨야 하는 경우 해당 문서가 내가 인쇄를 요청한 문서인 경우 요청한 문서 위치값 맨 마지막으로 update 해당 문서가 내가 인쇄를 요청한 문서가..
[Programmers] 기능개발
[Programmers] 기능개발 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42586 💬설명 입출력에 순서가 있다 -> 스택/큐 생각해보자. 가장 앞에 있는 작업이 완료되는 시점으로 시간이동 -> 100퍼센트 넘어간 작업들 popleft하면서 개수를 세준다. 다른 사람들은 어떻게 풀었을지 구글링 해보니 모든 작업들에 대해 각각이 완료되는 시점을 모두 구해놓은 뒤에 계산해주는 방식도 있었다. (이렇게 하면 더 깔끔할듯?!) 👩💻코드 import math def solution(progresses, speeds): answer = [] while progresses: answer.append(0) first_progress = progresses[0..
[Programmers] 베스트앨범
[Programmers] 베스트앨범 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42579 💬설명 조금의 생각이 필요한 문제였다. python의 sort함수를 잘 이용하면 쉽게 풀 수 있다. 간단하게 얘기하면 아래와 같다. 장르 이름을 key로 가지는 dictionary에 노래들을 [재생횟수, 고유 번호] 배열로 집어 넣는다. 장르별로 노래 총 재생횟수도 함께 세어준다. 노래가 많이 재생된 장르별로 정렬한다. 정렬된 장르별로 각 장르에 속하는 노래를 "재생횟수 -> 고유 번호" 순으로 정렬해서 최대 2개씩 answer 배열에 append 해준다. 👩💻코드 def solution(genres, plays): answer = [] songs = {} g..
[Programmers] 위장
[Programmers] 위장 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42578 💬설명 문제 자체는 어렵지 않았다. 우선 옷 종류별로 dictionary에 넣어서 개수를 센다. (ex) {"face": 2, "headgear": 1 } 각각의 옷 종류별로 (아무것도 선택 안함, 첫번째꺼 선택, 두번째꺼 선택, ... 마지막꺼 선택) 이렇게 선택이 가능하다. 즉, face가 2개가 있다면 (아무것도 선택 안하거나, 선글라스를 선택하거나, 마스크를 선택하거나) 이렇게 3가지의 선택지가 있다. 옷 종류별로 n + 1가지의 선택지가 있으므로 이것들을 전부 곱해준다. 중요한건 아무것도 입지 않는 경우는 없으므로 1을 빼줘야 한다는 것. 효율성 점수도 없고..
[Programmers] 전화번호 목록
[Programmers] 전화번호 목록 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3 💬설명 전화번호 목록이 있을 때 임의의 전화번호가 다른 전화번호의 접두어인 경우가 있는지 체크하는 문제 이중 for문을 이용해 풀어 줄 수도 있지만 "phone_book의 길이는 1 이상 1,000,000 이하입니다." 로 봐서 그렇게 하면 바로 효율성에서 틀릴 것 같았다. 따라서 모든 전화번호를 파이썬의 dictionary에 넣어두고(N) 전화번호 하나씩 돌아가면서(N) 처음-i번째까지가 dictionary에 있는지 체크(최대 20)하는 방식으로 풀어줬다. 이렇게 하면 dictionary는 찾는게 O(1)밖에 안걸리기 때문에 ..
[Programmers] 완주하지 못한 선수
[Programmers] 완주하지 못한 선수 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42576 💬설명 우선 문제 자체는 어려운 문제가 아니다. 다만 효율성을 따지면 조금 생각이 필요했다. 푸는 방식이 매우 다양한데, 그중 파이썬은 collections 모듈에 있는 Counter를 이용하면 아주 편하다. 공식 레퍼런스 사이트는 여기서 보면 된다. 재밌는 모듈을 하나 알아가서 좋았다:) 👩💻코드 from collections import Counter def solution(participant, completion): # 각각에 대해 정렬 participant.sort() completion.sort() # 개수만큼 빼준다. 없는 사람이 있으면 ..