다시푸는 코딩 테스트 준비 일지
응시 사이트 : BOJ
문제 : 19637.IF문 좀 대신 써줘
사용언어 : C#
난이도 : Middle
풀이시간 : 1h 26m
유형 : 이분 탐색
문제
게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다.
예를 들어, 전투력 10,000 이하의 캐릭터는 WEAK, 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL, 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호를 붙여준다고 하자. 이를 IF문으로 작성한다면 아래와 같이 구현할 수 있다.
if power <= 10000
print WEAK
else if power <= 100000
print NORMAL
else if power <= 1000000
print STRONG혼자서 게임을 개발하느라 매우 바쁜 밀리를 대신해서, 캐릭터의 전투력에 맞는 칭호를 출력하는 프로그램을 작성하자.
입력
첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105)
두 번째 줄부터 N개의 줄에 각 칭호의 이름을 나타내는 길이 1 이상, 11 이하의 영어 대문자로만 구성된 문자열과 해당 칭호의 전투력 상한값을 나타내는 109 이하의 음이 아닌 정수가 주어진다. 칭호는 전투력 상한값의 비내림차순으로 주어진다.
N + 2번째 줄부터 M개의 각 줄에는 캐릭터의 전투력을 나타내는 음이 아닌 정수가 주어진다. 해당하는 칭호가 없는 전투력은 입력으로 주어지지 않는다.
출력
M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.
예제 입력 1 복사
3 8
WEAK 10000
NORMAL 100000
STRONG 1000000
0
9999
10000
10001
50000
100000
500000
1000000
예제 출력 1 복사
WEAK
WEAK
WEAK
NORMAL
NORMAL
NORMAL
STRONG
STRONG
예제 입력 2 복사
3 5
B 100
A 100
C 1000
99
100
101
500
1000
예제 출력 2 복사
B
B
C
C
C
문제 풀이 접근
이 문제는 여태까지 했던 이분 탐색의 느낌과는 조금 다른데, 크게 다르진 않다.
일단 내가 이 문제를 풀어온 아이디어 흐름은
1. 이분 탐색 ( 값 비교로 아이디어를 잡음 ) - 실패
> 값 비교가 아니라 이 문제는 영역에 존재하는지 판단하는 것이기 때문에, 사용할 수 없음으로 판단하여 사용로직 변경
2. 풀 배열에 값을 넣고 Hash 처럼 Index 접근으로 직접 접근 - 실패
> 이 방식은 초기 세팅이 오래걸린다는 단점이 있지만, O(1)로 바로 찾을 수 있어서 가능하지 않을까? 해서 사용해봄
3. 다시 영역(인덱스)으로 아이디어를 다시 잡고 이분 탐색 사용 - 성공
값 비교 이분탐색
여태까지 사용했던 이분 탐색은 값을 기준으로 비교하는 방식이었다.
1 2 3 4 5 가 있다고 하고, 찾을 원소가 2 라면,
1) 1 2 3 4 5 에서 mid = (left+right)/2 = mid 2 (index)
2) right = 2 로 변경 , 1 2 3 에서 mid = (left+right)/2 = mid 1 (index)
3) value == arr[mid] 충족, 있는지 2회 루프로 존재하는지 판단 성공
이런 방식으로 사용하는 것인데, 이 문제에서는 TC 1을 보면 10000 WEAK, 100000 NORMAL, 1000000 STRONG 이다.
즉, 내 전투력이 0, 1, 9999 등에 매칭되는 값이 대부분 없다.
그래서 값 비교 이분탐색은 초기 아이디어에서 바로 포기하고 다음으로 넘어갔다.
풀 배열 접근 방식
풀 배열 접근 방식이 무엇이냐면, 그냥 모든 값을 배열에 다 때려넣는 방식이다.
단순 무식하고, 공간에 대한 할당이 무지막지 하기때문에, 하면서도 안될것이다라고 생각은 했지만 일단 손이 많이가는 방식은 아니라서 진행해보았다.
자료구조 Dictionary를 사용하고 key = 전투력 상한 value (int), value = 칭호 value (string) 을 이용하여 구성하였고, 초기 구성 갯수는 넉넉하게 10,000,001개로 잡았는데, 택도없이 시간초과가 발생했다.
영역 비교 이분탐색
문제를 풀다가 문득 떠오른 방식이다.
값을 == 로 비교하는 방식이 아니라 left, right를 인덱스로 영역에 포함되었는지 부등호를 이용해서 영역을 판단하는 것이다. 조건은
1) arr[_left].key <= val && arr[mid].key >= val 일 때,
> 이는 곧, 아래와 같다.
2) 그리고 그 외 left 의 경우일 때,
이런식으로 변경한 뒤에, 값을 어떻게 산출하느냐 라는 판단 기준이 필요했는데, 이렇게 루프를 돌다보면 결국에 아래와 같이 left로 쏠리면서 모두 같아지거나, 우측으로 쏠리면서 같아지는 경우가 결국에 온다.
이럴때, 문제에서는 선입력을 기준으로 출력을 요구했기 때문에, right에 해당하는 value 값을 가져와서 StringBuilder에 버퍼스트링을 추가해두고 모든 서치가 끝났을 때 출력하면 필요한 내용이 모두 출력되는 것을 볼 수 있다.
작성 코드 (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/19637
* Time : 1h 26m
*/
namespace CodingTestProj
{
internal class Program
{
static void Main(string[] args)
{
Solution solu = new Solution();
solu.solve();
}
}
public class Solution
{
public int _titleCnt;
public int _chrCnt;
public Dictionary<int, string> _dct_title;
public const int CTCnt = 10000001;
public int[] _arr;
public StringBuilder _sb;
public void solve()
{
_sb = new StringBuilder();
_dct_title = new Dictionary<int, string>();
for (int i = 0; i < CTCnt; i++)
_dct_title.Add(i, string.Empty);
string[] _input;
_input = Console.ReadLine().Split(' ');
_titleCnt = int.Parse(_input[0]);
_chrCnt = int.Parse(_input[1]);
_arr = new int[_chrCnt];
int min = 0;
for (int i = 0; i < _titleCnt; i++)
{
_input = Console.ReadLine().Split(' ');
int _val = int.Parse(_input[1]);
for (; min <= _val; ++min)
{
_dct_title[min] = _input[0];
}
}// title
for (int i = 0; i < _chrCnt; ++i)
{
_arr[i] = int.Parse(Console.ReadLine());
}
//_chrCnt
for (int i = 0; i < _arr.Length; ++i)
{
_sb.AppendLine(BinarySearch(_arr[i]));
}
Console.WriteLine(_sb.ToString());
}
public string BinarySearch(int val)
{
return _dct_title[val];
}
}
}작성 코드 (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/19637
// * Time : 1h 26m
// */
namespace CodingTestProj
{
internal class Program
{
static void Main(string[] args)
{
Solution solu = new Solution();
solu.solve();
}
}
public class Solution
{
public int _titleCnt;
public int _chrCnt;
public List<KeyValuePair<int, string>> _lst_kvt;
public const int CTCnt = 10000001;
public int[] _arr;
public StringBuilder _sb;
public void solve()
{
_sb = new StringBuilder();
_lst_kvt = new List<KeyValuePair<int, string>>();
_lst_kvt.Add(new KeyValuePair<int, string>(0, string.Empty));
string[] _input;
_input = Console.ReadLine().Split(' ');
_titleCnt = int.Parse(_input[0]);
_chrCnt = int.Parse(_input[1]);
_arr = new int[_chrCnt];
for (int i= 0; i < _titleCnt; i++){
_input = Console.ReadLine().Split(' ');
string _title = _input[0];
int _val = int.Parse(_input[1]);
_lst_kvt.Add(new KeyValuePair<int, string>(_val, _title));
}// title
for(int i = 0; i < _chrCnt; ++i){
_arr[i] = int.Parse(Console.ReadLine());
}
//_chrCnt
for(int i = 0; i < _arr.Length; ++i)
{
_sb.AppendLine(BinarySearch(_arr[i]));
}
Console.WriteLine(_sb.ToString());
}
public string BinarySearch(int val){
string _ret = string.Empty;
int _left = 0;
int _right = _lst_kvt.Count - 1;
while(_left <= _right)
{
int mid = (_left + _right) / 2;
if (_left == mid || _right == mid)
{
_ret = _lst_kvt[_right].Value;
break;
}
else if (_lst_kvt[_left].Key <= val && _lst_kvt[mid].Key >= val)
{
_right = mid;
}
else
_left = mid;
}
return _ret;
}
}
}코드 결과
