U E D R , A S I H C RSS

Jolly Jumpers/강희경

~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라고 인식하는 건가?? 그럼 완전 잘못된 거 아냐?? --재동
일단 해결!! 예외처리 덕분에 코드에서 냄새가 남...리팩토링 해야겠음--강희경

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0085 sec