코딩테스트 기록 5일차
CodingTest
코딩테스트 기록 5일차
1. 9375번: 패션왕 신해빈 (메모리: 14180 KB, 시간: 128 ms)
문제 정리
- 목표 : 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 모든 경우의 수를 찾는거
- 조건 : 한번 입었던 옷의 조합은 다시 안입음. 같은 종류의 의상은 동시에 하나만 착용.
- 입력
- Line 1 테스트케이스 횟수(최대100)
- Line 2 해빈이의 의상 수 (n)
- Line T_1 의상의 이름, 의상의 종류(사이 빈 공백)
- 출력 : 각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우
개념 및 접근법
- HashMap을 사용한다.(의상의 종류, 개수)
- 해빈이는 각 의상을 입거나 입지 않을 수 있다. (알몸만 아니면 됨)
- 각 의상 종류별로 의상을 입는 경우의 수 + 1(의상을 안 입는 경우)로 계산.
- 각 의상 종류별 경우의 수를 곱한 후, 아무것도 입지 않는 경우를 제외하여 최종 값을 도출
- (a+1)(b+1)(c+1)-1 =결과값
2. 2075번: N번째 큰 수 (메모리: 243540 KB, 시간: 932 ms)
문제 정리
- 목표 : N * N 크기의 표가 제공된다. N 번째 큰수를 찾아라
- 입력 :
- Line 1 : 표의 크기 N
- Line N : 숫자
- 출력 : N번쨰로 큰 수 찾기.
개념 및 접근법
- Priority Queue 이용
- PQ의 우선순위는 숫자의 오름차순을 이용
- peek값이 N번째로 오게 출력.
3. 2002번: 추월 (메모리: 14876 KB, 시간: 600 ms)
문제 정리
- 목표 :-터널 내에서의 차선 변경은 불가능하다 . 대근이는 터널 입구, 영식이는 터널 출구에서 자신들이 적은 차량을 비교해 반드시 추월을 했을것으로 보여지는 차들의 대수를 확인한다.
- 입력 :
- Line 1 : 차의 대수 N
- Line 2~N+1 : 대근이가 적은 차량번호 목록
- Line N+2~2N : 영식이가 적은 차량번호 목록
- 출력 : 터널 내부에서 추월을 반드시 했을것으로 여겨지는 차의 대수
개념 및 접근법
- 터널 입구 차량번호(대근), 터널 출구 차량번호(영식)를 각각 저장
- 대근이와 영식이가 적은 차량번호는 무조건 같아야함.(내가생각한 전제조건)
- 영식이의 차량번호가 대근이의 차량번호보다 인덱스가 앞설경우 무조건 추월했다판단.
- ArrayList를 사용해서 차량의 진입 탈출 순서를 보장. 서 차량의 진입 탈출 순서를 보장.
4. 15903번: 카드 합체놀이 (메모리: 15260 KB, 시간: 180 ms)
문제 정리
- 목표 : 카드 합체 놀이를 통해 가장 작은 점수 계산하기.
- 입력 :
- n (2 ≤ n ≤ 1,000): 카드의 개수.
- m (0 ≤ m ≤ 15×n): 카드 합체를 하는 횟수.
- a1, … ,an 맨 처음 카드의 상태를 나타내는 n개의 자연수, 공백으로 구분되어 입력된다.
- 출력 : 만들 수 있는 가장 작은 점수를 출력한다.
개념 및 접근법
- 두 장의 카드를 선택 후 더한 값을 두 카드에 다시 넣는방식.
- m번 반복한 후, 모든 카드의 수를 더한 값을 출력한다.
- 가장 작은 두 수를 선택하여 합체해야함.
정리
- PriorityQueue를 사용해서 점수를 최소화하고 더한 값을 추가하며 m번반복
5. 11286번: 절댓값 힙 (메모리: 27060 KB, 시간: 636 ms)
문제 정리
- 목표 : 주어진 연산들을 수행하면서, 절댓값이 가장 작은 값을 찾아 출력하고 배열에서 제거하는 프로그램을 작성한다.
- 입력 :
- 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다.
- 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다.
- x ≠ 0: 배열에 x를 추가한다.
- x = 0: 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
- 절댓값이 가장 작은 값이 여러 개일 경우, 가장 작은 수를 출력하고 제거한다.
- 출력 :
- 입력에서 0이 주어진 횟수만큼, 절댓값이 가장 작은 값을 출력한다.
- 배열이 비어 있는 경우에 0이 입력되면 0을 출력한다.
개념 및 접근법
- 우선순위 큐를 사용해서 절댓값을 기준으로 정렬되게 커스텀한다.
6. 1715번: 카드 정렬하기 (메모리: 25504 KB, 시간: 364 ms)
문제 정리
- 목표 : 여러 묶음의 숫자 카드를 모두 하나의 묶음으로 합치기 위해 필요한 최소 비교 횟수를 구한다.
- 입력 :
- 첫째 줄에 숫자 카드 묶음의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)
- 이어서 N개의 줄에 걸쳐 각 숫자 카드 묶음의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.
- 출력 :
- 모든 카드 묶음을 하나로 합치기 위해 필요한 최소 비교 횟수를 출력한다.
개념 및 접근법
- 우선순위 큐(Priority Queue)를 사용해서 크기가 가장 작은 두 묶음의 카드를 선택하고 합친다.
- 값들을 더하고, 합친 묶음을 다시 추가한다.
- 하나의 묶음이 될떄 까지 반복한다.
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.