~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가 두번 나오면 안된다.)
시간 복잡도: Ο(n)
졸리점퍼임을 확인하는 2가지 조건
1. gap들의 각기 다른 크기여야한다.(ex)2가 두번 나오면 안된다.)
- binaryMap이라는 bool형 리스트를 사용하여 gap의 중복을 검사
시간 복잡도: Ο(n)