다시푸는 코딩 테스트 준비 일지
응시 사이트 : BOJ
사용언어 : C#
난이도 : Easy
풀이시간 : 1h 27m
유형 : 투 포인터, 정렬, 그리디
문제
Farmer John has discovered the Internet is buying bales of hay online when he notices a special deal. For every bale of hay of size A (1 <= A <= 1,000,000) he buys, he can get a bale of hay of size B (1 <= B < A) for free!
The deal, however, is restricted: the larger bale must be high quality hay and the smaller one must be low quality hay. FJ, being a frugal and thrifty fellow, does not care: any quality of hay will do as long as he saves some money.
Given a list of the sizes of N (1 <= N <= 10,000) bales of high quality hay and M (1 <= M <= 10,000) bales of low quality hay, find the maximum number of bales of hay Farmer John can purchase. He can buy bales of high quality hay without getting the free bale of low quality hay, but he cannot buy bales of low quality hay (i.e., he must get them for free in the deal).
입력
Line 1: Two space-separated integers: N and M.
Lines 2..N+1: Line i+1 contains a single integer which is the size of the ith bale of high quality hay.
Lines N+2..N+M+1: Line i+N+1 contains a single integer which is the size of the ith bale of low quality hay.
출력
Line 1: The maximum total number of bales of hay Farmer John can obtain.
예제 입력 1 복사
3 4
6
1
3
1
5
3
4
예제 출력 1 복사
5
문제 풀이 접근
문제를 잘못이해해서 시간이 오래걸렸는데, 첫 접근은 N배열의 고품질 건초 1개를 살때 저품질 건초배열에서 품질 낮은 모든 것을 무료로 가져갈 수 있는줄 잘못이해하고 풀었다.
문제 요구사항은 제목에 직관적으로 나와있다. One Buy - One Free 즉, 하나 사면 하나 공짜 1+1 개념이다.
여기서 문제가 원하는 것은 최대한 영리하게 구입해서 최대한 많은 건초 몇개를 가져올 수 있느냐 였다.
문제 풀이 흐름
고품질 건초 배열 N, 저품질 건초 배열 M을 "내림차순"으로 정렬한다
=> 이렇게 해야 앞수에서 앞수로 빠르게 체크해서 break 처리할 수 있어서 루프 하나라도 줄일 수 있다.N의 원소로 건초 배열 M안에 있는 배열의 원소 수를 돌리고, N의 원소가 더 작을 경우 M의 다음원소와 비교한다 ( 내림차순이기 때문에)
N의 원소가 M의 배열에서 가장 근접하며, 사용하지 않은 원소를 찾는다면 HashSet에 사용한 인덱스를 등록한다.
=> 건초의 크기는 중복될 수 있기 때문에, 인덱스로 계산하는 것이 정확하다.HashSet에 등록된 Index가 저품질 건초 배열에서 가져올 수 있는 건초의 수다. 고품질 건초를 구매했다는 카운트를 올린다.
반복이 끝나면 고품질 건초 구매 수 + 저품질 건초 무료로 받은 갯수 를 출력한다.
작성 코드 (C#)
using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;
using System.Text;
///*
// * Difficulty : Middle
// * URL : https://www.acmicpc.net/problem/6230
// * Time : 1h 27m
// */
namespace CodingTestProj
{
internal class Program
{
static void Main(string[] args)
{
Solution solu = new Solution();
solu.solve();
}
}
public class Solution
{
public HashSet<string> _hs_ret;
public int _n;
public int _m;
public int[] _arrN;
public int[] _arrM;
public int _left;
public int _right;
public void solve()
{
_hs_ret = new HashSet<string>();
string[] _input = Console.ReadLine().Split(' ');
_n = int.Parse(_input[0]);
_m = int.Parse(_input[1]);
_arrN = new int[_n];
_arrM = new int[_m];
for (int i = 0; i < _n; ++i)
_arrN[i] = int.Parse(Console.ReadLine());
for (int i = 0; i < _m; ++i)
_arrM[i] = int.Parse(Console.ReadLine());
/*
* A크기 건초베일 하나 살때 B 크기의 건초베일 무료로
* N 고품질 배일 , M 저품질 베일
*/
_left = 0;
_right = _n - 1;
// 제일 큰 수에서 가져오면 된다.
Array.Sort(_arrN, (int a, int b) => { return b.CompareTo(a); });
Array.Sort(_arrM, (int a, int b) => { return b.CompareTo(a); });
int _retResult = 0;
while(_left < _arrN.Length)
{
int _nArrElem = _arrN[_left];
for(int i = 0; i < _arrM.Length; ++i)
{
int _mArrElem = _arrM[i];
if (_nArrElem <= _mArrElem) continue;
string _key = $"{i}"; // 인덱스로 넣음
if(!_hs_ret.Contains(_key))
{
_hs_ret.Add(_key); // 저품질 건초 +
break;
}
}
++_retResult; // 고급 건초 카운트
++_left;
}
_retResult += _hs_ret.Count;
Console.WriteLine(_retResult);
}
}
}
코드 결과
