~cpp
#include<iostream>
using namespace std;
int* InputList();
bool Judge(int* aList);
void OutputJudgement(bool aIsIt);
int GetSumOfGoalGap(int aN);
bool isCorrectInput;
void main()
{
isCorrectInput = true;
OutputJudgement(Judge(InputList()));
}
int* InputList(){
bool isInputStart = false;
int numberOfInputFactor;
int* inputedList;
do{
if(!isInputStart){
if(cin >> numberOfInputFactor){
inputedList = new int[numberOfInputFactor+1];
inputedList[0] = numberOfInputFactor;
isInputStart = true;
if(numberOfInputFactor < 2){
isCorrectInput = false;
numberOfInputFactor = 0;
}
}
else{
isCorrectInput = false;
numberOfInputFactor = 0;
}
}
else{
if(!(cin >> inputedList[inputedList[0] - numberOfInputFactor])){
isCorrectInput = false;
numberOfInputFactor = 0;
}
}
numberOfInputFactor--;
}while(numberOfInputFactor >= 0);
char temp;
cin.get(temp);
if(temp != '\n')
isCorrectInput = false;
return inputedList;
}
bool Judge(int* aList)
{
if(!isCorrectInput)
return false;
int gap;
bool* binaryMap = new bool[aList[0]-1];
for(int i = 0; i < aList[0]-1; i++)
binaryMap[i] = false;
for(i = 1; i < aList[0]; i++){
gap = abs(aList[i] - aList[i+1]);
if(gap >= aList[0] || gap == 0 || binaryMap[gap-1]){
delete aList;
delete binaryMap;
return false;
}
else
binaryMap[gap-1] = true;
}
delete aList;
delete binaryMap;
return true;
}
void OutputJudgement(bool aIsIt)
{
if(aIsIt)
cout << "JollyJumpers\n";
else
cout << "Nothing\n";
}
생각 ¶
성능(performance)을 최적화하기 위해 여러가지 생각을 해보았음.
졸리점퍼임을 확인하는 2가지 조건
1. gap들의 각기 다른 크기여야한다.(ex)2가 두번 나오면 안된다.)
- binaryMap이라는 bool형 리스트를 사용하여 gap의 중복을 검사
2. 각각의 gap은 0보다 크고 n보다 작아야한다.
시간 복잡도: Ο(n)
고칠점 ¶
2 2 3 4의 입력을 받는 경우 2 2 3만 인식하여 졸리점퍼라고 판단하게 된다. 현재는 고칠 생각없음
그럼 2 2 3 10에서도
JollyJumper라고 인식하는 건가?? 그럼 완전 잘못된 거 아냐?? --재동
일단 해결!! 예외처리 덕분에 코드에서 냄새가 남...리팩토링 해야겠음--
강희경