알고리즘/문제풀이

[프로그래머스] H-index

문제: https://programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 문제를 조건을 그대로 따라가면서 풀었다. isValid 함수는 넘어온 h값이 h-index의 후보가 될 수 있는지를 true false로 리턴한다. solution 함수에서는 0부터 999까지를 h에 넣어보며 h의 최댓값을 구한다 (문제 조건에 따라 h는 0이상 1000이하이다.) 지금보니 range를 1000이 아니라 l..

[프로그래머스] 가장 큰 수

문제: https://programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 맨 처음 직관적으로 드는 생각: 주어진 숫자로 가장 큰 수를 만드려면, 주어진 숫자들을 내림차순으로 정렬하면 되지 않을까? ex) 1, 3, 9 가 주어졌을 때 가장 큰 수는 931 하지만 숫자들이 일의 자리를 넘어가게 되면 문제가 생긴다. ex) 1, 3, 10 이 주어졌을 때 가장 큰 수..

[프로그래머스] 이중 우선순위 큐

문제: https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr max heap queue와 min heap queue를 만들고 operation에 맞게 업데이트해주면 된다. max heap queue에서 pop하는 경우, 데이터 동기화를 위해 min heap queue도 같이 pop해줘야 하는데, 그냥 remove로 삭제했다. 이렇게 해보고 혹시 성능상의 이슈가 있으면 탐색하는 부분을 따로 구현하려고 했는데 큰 문제는 없어보인다. + 생각해보니 max heap에서 최솟값은 리프노드에 있으므로 remove 연산 후 heapify를 해주지 않아도 된다.

[프로그래머스] 기능개발

문제: https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 1. 작업해야하는 day 계산 2. 모든 작업에 day * speed 더함 3. 완료된 작업의 개수 n 계산 4. n개 pop 5. answer에 n 추가 반복조건: progresses가 비어있지 않음

[프로그래머스] 더 맵게

문제: https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 힙으로 만들고 2개씩 pop 해서 mix 한 뒤 push 하는 걸 반복한다. 반복조건: 힙의 루트노드가 K 미만인 경우 예외: 더이상 섞을 수 없는 경우 => return -1

[프로그래머스] 베스트앨범 (+파이썬 테크닉)

문제: https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 자잘하게 신경써줘야할 게 많아서 난이도가 레벨3으로 측정된 것 같습니다. 천천히 한 단계씩 해결해나가면 오래걸리긴 해도 안 풀리는 문제는 아닙니다. 아래는 제 풀이입니다. 다른 분들의 풀이를 보니 알고 있으면 좋을 만한 테크닉들이 보여서 정리해봤습니다. 리스트에서 중복 제거 map과 sum 활용하기 myList = [(1,10),(2,20),(3,30)..

[프로그래머스] 위장

문제: https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 수학적으로 접근하면 구현을 쌩까고 바로 수식으로 처리해버릴 수 있습니다. 1. 각 부위별 옷의 개수를 카운트합니다. 2. (각 부위별 옷의 개수 + 1) 을 해서 모두 곱연산합니다. 3. 그렇게 나온 결과에서 1을 뺀 값이 정답입니다.

[프로그래머스] 전화번호 목록 (정렬보다는 해시를)

문제: https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 정렬을 이용하는 방법 사실 보자마자 딱 생각나는 방법은 정렬하고 두 개씩 비교하는 방법입니다. 정렬하면 앞부분이 비슷한 것들끼리 인접하게 되기 때문에 인접한 두 전화번호끼리만 비교해도 결과는 맞게 나옵니다. 효율성 테스트도 나쁘지 않게 나오네요. 해시로 풀어보기 그래도 해시 관련 문제이므로 해시로 다시 풀어봤습니다. 접두..

[프로그래머스] 완주하지 못한 선수

문제: https://programmers.co.kr/learn/courses/30/lessons/42576 보자마자 생각나는 아이디어는 이랬습니다. 각 리스트를 정렬하고, 처음부터 쭉 순회하다가 원소가 서로 다르면 그 원소를 리턴 하지만 해시를 이용하면 더 빠르게 해결할 수 있습니다.

[백준] 2581 - 소수찾기(3)

문제 : www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 이전 문제와 거의 똑같은 문제다. 이전 문제: 2020/12/25 - [프로그래밍/문제 풀이] - [문제풀이] 백준 1929번 - 소수찾기(2) {시간초과이슈} [문제풀이] 백준 1929번 - 소수찾기(2) {시간초과이슈} 문제: www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이..

[백준] 1929 - 소수찾기(2) {시간초과이슈}

문제: www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 자체는 간단하다. 그러나 이전 문제와 같은 방식으로 풀면 시간초과가 난다. 이전 문제: 2020/12/24 - [프로그래밍/문제 풀이] - [문제풀이/C] 백준 1978번 - 소수 찾기 [문제풀이/C] 백준 1978번 - 소수 찾기 문제: www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수..

[백준] 1978 - 소수 찾기

문제: www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 쉬운 문제이므로 코드만 적음

[백준] 1011 - 나를 알파 센타우리로 보내줘

문제: www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 어찌 되었든 1 2 3 4 5 ··· 5 4 3 2 1 이런 식으로 이동해야 할 것 같다. 1 + 2 + 3 + ··· + n + n-1 + n-2 + n-3 + ··· + 3 + 2 + 1 = n^2 이므로 이동해야 하는 거리 D에 대하여 n^2

[백준] 2775 - 재귀함수로 풀어보자

문제: www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1

[백준] 10250 - 행렬에 순서 매기기

문제 : www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13 예를 들어 4 x 4 인 호텔의 경우 위와 같은 순서로 손님들이 들어오게 된다. 이때 14번 손님이 들어오는 방에 대해 살펴보자. 이 방은 2층의 4번째 방이므로 14 = (4 - 1) * 4 + 2 가 된다. 즉 n층의 m번째 방에는 (m - 1) * 4 + n 번째 손님이 들어오게 된다. 우리에게 주어지는 것은 (m ..