안녕하세요. 오늘은 프로그래머스에서 제가 애를 먹었던 문제를 소개해보려고 합니다.
겉으로 보기에는 간단한 문제입니다. 주사위 4개를 던졌을 때 숫자가 나오는 양상에 따라 다르게 처리를 하면 되거든요.
그런데 문제는 조건 분기입니다. input이 a,b,c,d일 때 네 개가 같은지 다른지 알려면, 비교를 굉장히 많이 해야합니다.
이 과정은 조건문을 쓰는 것도 까다롭고, 실수하면 디버깅도 어렵기 때문에 a,b,c,d를 모두 비교하는 것은
이 문제의 의도가 아니라고 생각이 들었습니다.
set을 이용한 풀이
int answer = 0;
set<int> dice;
dice.insert(a);
dice.insert(b);
dice.insert(c);
dice.insert(d);
먼저 저는, set으로 접근을 시도했습니다.
set의 특성상, 같은 원소가 들어오면 중복처리되므로, set의 크기를 세면 간단하게 해결할 수 있을 거라 생각했습니다.
//case: a,a,a,a
if (dice.size() == 1)
{
answer = (*dice.begin()) * 1111;
}a,a,a,a인 경우에는, set의 크기가 1이므로 간단하게 처리할 수 있었습니다.
set의 크기가 2인 경우에는, 이제 문제가 생기게 됩니다.
1. a,a,b,b이거나
2. a,b,b,b인데, 둘다 set에서는 {a,b}이므로, 이 둘을 set이라는 자료구조만 이용해서 구분할 방법이 없습니다.
그래서 set을 선택한 것은 50%는 맞지만, 50%는 아니구나 생각했습니다.
어쩔 수 없이, 이 두 가지 경우는 직접 원소를 비교해서 해결하기로 했습니다.
else if (dice.size() == 2)
{
int x = *dice.begin();
int y = *next(dice.begin(), 1);
int abcd = a + b + c + d;
int xxxy = x + x + x + y;
int xyyy = x + y + y + y;
}
일단, a+b+c+d의 합을 구했습니다. 그리고 set의 x,y를 구해서 3x+y와 x+3y를 계산합니다.
쉽게 설명하기 위해 예를 들면, input={1,3,3,3}이라고 하겠습니다.
abcd=1+3+3+3=10
xxxy=3*1+3=6
xyyy=1*1+3*3=10이 됩니다.
만약 abbb거나 aaab인 경우, 반드시 abcd는 xxxy또는 xyyy와 값이 같습니다.
만약 aabb인 경우에는, abcd!=xyyy && abcd!=xxxy입니다.
그래서 이를 코드로 작성하면 다음과 같습니다.
int xxyy = x + x + y + y;
//case a,a,a,b
if (abcd == xxxy)
{
answer = (10 * x + y) * (10 * x + y);
}
//case a,b,b,b
else if (abcd == xyyy)
{
answer = (10 * y + x) * (10 * y + x);
}
//case a,a,b,b
else if (abcd == xxyy)
{
answer = (x + y) * abs(x - y);
}aaab와 abbb인 경우에 x,y를 바꾸면 두 가지 경우를 모두 핸들링 할 수 있고,
둘 다 해당이 되지 않는 경우는 a,a,b,b입니다.
num.size()==3인 경우입니다.
이 경우에는 a,a,b,c 형태로 인풋이 들어오게 됩니다.
중요한 건, num={a,b,c}인데, 이 중에 뭐가 두 번 들어왔는지는 역시 set으로 알 수가 없습니다.
(set말고 다른 방법으로도 도전해봤는데, 일단 이 방식도 동작은 해서 넣어봤습니다.)
auto it = dice.begin();
int x = *it;
int y = *next(it);
int z = *next(it, 2);
int x2yz = 2 * x + y + z;
int xy2z = x + 2 * y + z;
int xyz2 = x + y + 2 * z;아까와 비슷하게 aabc, abbc, abcc인 경우 3가지로 분기를 합니다.
int abcd = a + b + c + d;
if (x2yz == abcd)
{
answer = y * z;
}
else if (xy2z == abcd)
{
answer = x * z;
}
else if (xyz2 == abcd)
{
answer = x * y;
}
마지막으로 num.size()==4인 경우, abcd케이스 입니다.
else if (dice.size() == 4)
{
answer = min(min(a, b), min(c, d));
}a,b를 비교하고 c,d를 비교한 후에, 각각의 min을 계산해 주는 3번의 과정으로 가장 작은 원소를 찾을 수 있습니다.
댓글