선발대

프로그래머스: 카펫 (링크) 예전에 간단하게 풀었던 기억이 있는데 다시 그 풀이를 보니까 주석이 없어서 왜 이런 식으로 되는지 이해를 못 했다. 과거의 내가 더 똑똑한 걸까? 대체 어떻게 한 거지? 계속 봐도 기억이 안 나서 그냥 아예 새로운 방식으로 다시 풀었다. 이번에는 근의 공식을 이용해서 풀었다. 갈색 카펫과 노란색 카펫의 각각의 가로, 세로를 Bx, By, Yx, Yy 라고 한다면 아래와 같은 관계식이 성립하게 된다. 카펫의 개수는 각각 B, Y로 지정했다. 1. Bx * By = B + Y2. Bx = Yx + 2, By = Yy + 2 --> Bx * By = (Yx + 2) * (Yy + 2) = YxYy + 2(Yx + Yy) + 43. Y = Yx * Yy 위의 식을 정리해보면 Bx *..

프로그래머스: H-Index (링크) 주어진 citations을 내림차순으로 정렬한 다음, 0부터 len(citations)을 반복문으로 돌려서 각각의 원소와 h 사이의 크기를 비교해주면 된다. (내림차순으로 정렬하는 이유는 h-index의 최댓값을 구해야 하기 때문) 예를 들어 [3, 0, 6, 1, 5]는 [6, 5, 3, 1, 0]으로 정렬시키고 for문을 돌려서 0번째 인덱스부터 문제의 조건대로 h보다 작은지 확인을 해준다. h보다 작은 경우에는 이미 h개의 요소가 있기 때문에 바로 h를 리턴해주면 된다.  def solution(citations): citations.sort(reverse=True) for h in range(len(citations)): if citat..

프로그래머스: 가장 큰 수 (링크) 주어진 리스트를 문자열로 변경해서 내림차순으로 정렬하는 것까지는 생각했는데 내 경우에는 lambda: x: (x[0], x[1], x[2]) 이런 식으로 작성했기 때문에 '3' ,'34'인 경우에는 인덱스 에러가 나왔다. 결국 풀이를 참고했는데 엄청 간단했다. 주어진 리스트를 문자열로 변경하고 lambda 함수로 x * 3을 적용하게 되면 '3'은 '333', '34'는 '343434' 로 변경되고 그걸 기준으로 reverse=True 내림차순으로 정렬되므로 쉽게 구할 수 있다. x * 3을 하는 이유는 주어지는 numbers의 원소가 1000 이하의 수이기 때문이다. '3'과 '334'를 비교할 때 앞의 3자리만 비교하면 되므로 x * 3을 해서 각각 '333', '..

LeetCode: 2336. Smallest Number in Infinite Set (링크)    Leet code에서는 문제를 처음 풀어봐서 어떻게 풀어야 할지 헤매다가 블로그를 참고하여 풀어봤다.input 형태가 백준이나 프로그래머스와 다르게 되어 있었는데 이해하고 나니 생각보다 간단했다. 문제를 요약하면 다음과 같다. 무한한 양의 정수가 있는 집합 하나가 있고, __init__에서 생성한 빈 집합 black이 있다. 여기에서 우리는 popSmallest를 했을 때 무한한 양의 정수 집합에서 최솟값을 리턴하고 그 값을 무한양수집합에서 제거해야 한다. 그러므로 제일 처음에 popSmallest를 하게 되면 가장 작은 값인 1이 리턴된다. 다음에 또다시 popSmallest를 하게 되면 1을 제외하고 ..

프로그래머스: 더 맵게 (링크) 라이브러리 heapq를 사용했다. heapq.heapify(): 주어진 리스트를 힙으로 변경한다.heapq.heappop(): 가장 최소의 수를 뽑는다.heapq.heappush(): 힙에 다시 수를 넣는다 heapq.heapify()를 사용하게 되면 작은 순서부터 자동으로 정렬된다. 그러면 문제에서 주어진 조건대로 heapq.heappop()을 이용하여 가장 작은 수를 하나씩 뽑은 후 계산한 후 다시 heapq.push()로 넣고 cnt + 1를 한다. 가장 최소의 값이 K 이하가 될 때까지 계속 while문을 돌린다. import heapqdef solution(scoville, K): heapq.heapify(scoville) min_sum = 0 ..

프로그래머스: 올바른 괄호 (링크) 괄호의 짝이 올바르게 연결되었는지 판단하는 문제이다. 간단하게 문자열 s를 리스트로 변경하고 for문을 통해 하나씩 꺼내온다. 그러면서 '(' 인 경우에는 temp 리스트에 넣어주고 ')' 인 경우에는 pop()을 이용하여 temp에서 꺼내준다. try-except문으로 pop이 불가능한 경우에는 '('가 없는 상황인데 ')'를 꺼내려는 경우이므로 짝이 맞지 않기 때문에 False를 리턴해준다. ## 내가 작성한 코드def solution(s): s = list(s) temp = [] if s[0] == ')' or s[-1] == '(': return False for elem in s: if elem == '('..

프로그래머스: 기능개발 (링크) 먼저 days라는 리스트를 두고 작업이 완료되는 날들을 append 해야 한다. 다만 하루의 끝에서 배포가 이루어지므로 만약 progresses가 speeds로 나누어 떨어지지 않으면 +1을 해줘야 한다. 그 후 temp라는 변수에 days[0] 값을 초기값으로 두고 days 리스트를 1번째 인덱스부터 끝까지 돌면서 temp와 days[i]를 비교한다. 만약 temp가 days[i] 보다 크다면 days[i]는 temp가 끝날 때까지 대기해야 하므로 cnt에 +1을 해준다. 그 반대의 경우라면 그대로 answer 리스트에 cnt 값을 넣어준다. 모든 for문을 돌고 나면 최종 cnt가 answer 리스트에 추가되지 않은 채로 끝나므로 마지막 줄에 answer.append(..

프로그래머스: 의상 (링크) 딕셔너리를 어떤 형식으로 구현할지 결정하면 간단하다. box 라는 딕셔너리에 키 값은 종류, 밸류 값은 이름 리스트로 해서 구분하면 편하다. 전체 for문을 돌면서 이런 식으로 입력값을 box 딕셔너리에 저장하고, 전체 경우의 수를 구하는 것이므로 각 이름 리스트의 가짓수를 곱해주면 된다. 착용하지 않을 수도 있는 경우의 수도 생각해야 하므로 +1을 해준다. 최종 answer 값에는 아무것도 입지 않는 경우를 제외해야 하므로 answer - 1 을 리턴한다. def solution(clothes): box = {} answer = 1 for name, category in clothes: if category in box.keys(): ..

프로그래머스: 전화번호 목록 (링크) 얼마 전에 99클럽 1기를 잘 마무리했는데 매일 알고리즘 한 문제씩 푸는 게 좋아서 이번에도 2기를 지원했다.이번 기수에서는 TIL을 처음부터 꾸준히 써보려 한다. 화이팅! 해시 카테고리에 있는 문제이지만 해시를 이용하지 않고 풀 수 있는 문제였다.처음에는 sort를 안 하고 이중 for문을 사용했었는데 그랬더니 효율성 테스트에서 시간 초과가 나왔다.문제를 잘 읽어보면 말머리만 동일하면 바로 False를 출력하면 되므로,sort로 리스트를 정렬하고 해당 요소와 바로 뒤의 요소만 비교하면 된다. def solution(phone_book): answer = True phone_book.sort() for i in range(len(phone_book)-..

프로그래머스: 소수 찾기 (링크) 소수 자체를 판별하는 방법은 예전에 풀어봐서 알고 있었는데 가능한 조합을 찾는 방법이 바로 떠오르지 않았다. permutations 사용은 감이 왔는데 매번 달라지는 가짓수를 어떻게 선택하나 싶었다가 다른 분의 블로그에서 힌트를 얻을 수 있었다. 그냥 for문 돌리면서 가짓수를 변경한 조합을 리스트에 저장하고 나중에 join으로 합쳐준 뒤 int로 변경하면 되는 방식이었다. 이렇게 되면 "17"이 주어졌을 때 int_num에는 [1, 7, 17, 71] 이 남게 된다. 그리고 하나 더 중요한 점이 combination이 아니라 permutation을 사용했기 때문에 만약 [1, 1, 2]인 경우 11이 2번 나오게 된다. 이런 경우 때문에 정답을 출력 시 set으로 중복..

28324번: 스케이트 연습 (링크) 단순하게 생각해서 전체 리스트 중 최소값을 기준으로 '최솟값 + (최솟값+1)*(n-1)'로 구할 수 있다고 생각했다. 그런데 문제 조건에 따르자면 중간 지점에서 원하는대로 최댓값으로 올라갈 수 있는데 이 부분을 미처 고려하지 못했다. 전체 for문을 돌려서 최솟값과 비교하며 하나씩 해볼까 하다가 다르게 푸신 분이 계셔서 참고했다. 문제의 조건에 따르자면 마지막 지점에서는 속도가 0이어야 하고, 속도는 내려갈 때 1씩만 감소할 수 있으므로 마지막 중간지점은 무조건 속도가 1이어야 한다. 이렇게 limit_velocity를 미리 1 값을 주고 for문도 n-1번만 돌린다. 마찬가지로 감속은 1씩만 가능하므로 현재 중간지점의 속도는 그 뒤의 속도 개수에 따라 최댓값이 정..

프로그래머스: 숫자 변환하기 (링크) 처음에는 재귀로 풀 수 있을 것이라 생각하고 돌렸는데 계속 오류가 나서 결국 다른 사람의 풀이를 찾아봤다.dp에 매번 값을 넣어두고 set을 이용해서 동일한 값을 제거하는 방식으로 풀었다.x값이 초기 dp에 있으므로 x값과 동일한 y값이 나타나면 그 때의 answer를 리턴하게 된다.막상 풀이를 보면 간단한데 아직 적재적소에 맞는 방법이 바로 떠오르지 않는 것 같다. def solution(x, y, n): answer = 0 dp = set() dp.add(x) while dp: if y in dp: return answer else: dp_y = set() ..

15700번: 타일 채우기 4 (링크)엄청 간단한 문제였다. 큰 문제점은 없었고 쉽게 해결할 수 있었다.생각해보면 주어진 입력값으로 만들어지는 배열은 항상 직사각형 또는 정사각형이다.따라서 2 x 1, 1 x 2 타일로 채우려면 그냥 그 입력값으로 받은 직사각형 배열 개수를 2로 나누어 주면 된다. 내일도 차근차근 풀어봐야겠다. import sysinput = sys.stdin.readlinen, m = map(int, input().split())print(n * m // 2)