2008년 02월 16일
그다지 유쾌하지 않은 Jolly Jumper
이피님 블로그에 갔다가 Jolly Jumper in Erlang 버전을 보고 그다지 유쾌하지 않았던 Jolly Jumper의 추억(?)을 떠올려본다.
이 유쾌하지 않은 추억의 서막은 Programming Challenges라는 책을 구입하면서 부터 시작됐다. 이 책의 저자는 무척 친절하게도 이 책에 나온 문제를 푼 소스코드가 맞았는지 틀렸는지 알 수 있도록 판정해주는 사이트를 제공하고 있었는데 (사이트에가면 문제의 내용도 모두 볼 수 있다.) 책에 나오는 문제를 하나씩 풀면서 나는 저자와는 달리 불친절한 판정(judge) 결과 때문에 머리를 쥐어뜯지 않을 수 없었다.
판정 결과는 단 한줄만 나오고 어떤 입력 데이터가 들어왔을 때 결과가 틀렸는지 따위는 결코 가르쳐주지 않았다. (어쩌라고..ㅠ_ㅠ)
거기다 문제들이 일관성 없이 어떤 때는 종료조건이 주어지고 어떤 경우에는 주어지질 않아서 헷갈렸던 적도 많고 문제를 풀 때 유의해야할 게 명시되지 않은 것을 예측해서 풀지 않도록 주의하라고 하는데 경우에 따라서는 주어진 내용만 가지고는 결과를 판단하기 어려운 문제도 있어서 그런 경우에는 나름 대로 예측해서 프로그램을 짤 수 밖에 없었다. 결국 프로그래밍 도전에 대한 나의 도전은 호주식 투표법에서 좌절을 맛보고는 그 이후에는 책을 펴보지도 않았다는 전설이 있습니다... 그려..
아.. 원래 하려던 이야기가 이건 아니고.. 다시 유쾌하지 않았던 Jolly Jumper에 대한 이야기를 시작 해보면...
때는 바야흐로.. 2006년 11월의 어느 날... 당시 나는 부운영자로 활동 중이던 C언어 카페의 부흥을 노리고자 Programming Challenges에 대한 도전을 카페에 제안하여 게시판을 하나 운영 중이었다. 당시 11월 셋째주 문제로 선택했던 것이 바로 이 Jolly Jumper!
문제는 다음과 같았다.
그리고 투쟁의 흔적들... (2008년 2월껀 오늘 다시 코드 수정하면서 얻은 결과..)
이러한 히스토리가.. -_-;
소스코드는 그 때 짠걸 봤는데.. 다시 보니 이건 왜 이렇게 짜놓은거야.. 하고 얼굴이 화끈화끈.. -_-;;
그래서 코드를 좀 정리해보았다. (이전 코드에는 로직과 입출력 루틴이 마구마구 섞여있었다..)
여기서 좀 또 웃긴게 있는데-_-;;;
예전 코드를 정리하다보니 정확한 히스토리가 기억이 안나서 n = 0; 해주는 부분을 뺐더니 시간 초과(Time limit exceeded) 가 걸려버렸다.
추측컨데 아마도 결과 판정 사이트는 소스를 올리면 소스를 올린 서버에서 실행파일을 컴파일하고
실행파일 < 입력데이터
이런 식으로 indirection을 이용해서 실행하는듯 한데 실제 데이터 파일 마지막이 0은 아니고 빈문자열이 들어있어 빈문자열이 입력되면 다음에 종료 판별루틴에서 n = 0으로 처리하여 프로그램이 종료되는 것으로 보인다. (판정을 받아본 것은 아닌데 입력 데이터 파일에 enter만 입력하고 저장한 후 위와 같이 실행했을 때 프로그램이 종료되었다. 나중에 수정해서 확인해봐야겠다..)
뭐 이렇게.. 다시금 Jolly Jumper에 대한 기억을 되돌려 보고 옛날에 짜둔 코드를 읽으면서 나의 프로그래밍 스타일의 변화를 살펴보니 내가 조금은 괜찮은 프로그래머가 되어가고 있나 하는 생각을 해본다..(아니면 그 당시 너무 형편없었거나..)
진짜로.. 갈 길이 멀구나~
참고 사이트
이 유쾌하지 않은 추억의 서막은 Programming Challenges라는 책을 구입하면서 부터 시작됐다. 이 책의 저자는 무척 친절하게도 이 책에 나온 문제를 푼 소스코드가 맞았는지 틀렸는지 알 수 있도록 판정해주는 사이트를 제공하고 있었는데 (사이트에가면 문제의 내용도 모두 볼 수 있다.) 책에 나오는 문제를 하나씩 풀면서 나는 저자와는 달리 불친절한 판정(judge) 결과 때문에 머리를 쥐어뜯지 않을 수 없었다.
판정 결과는 단 한줄만 나오고 어떤 입력 데이터가 들어왔을 때 결과가 틀렸는지 따위는 결코 가르쳐주지 않았다. (어쩌라고..ㅠ_ㅠ)
거기다 문제들이 일관성 없이 어떤 때는 종료조건이 주어지고 어떤 경우에는 주어지질 않아서 헷갈렸던 적도 많고 문제를 풀 때 유의해야할 게 명시되지 않은 것을 예측해서 풀지 않도록 주의하라고 하는데 경우에 따라서는 주어진 내용만 가지고는 결과를 판단하기 어려운 문제도 있어서 그런 경우에는 나름 대로 예측해서 프로그램을 짤 수 밖에 없었다. 결국 프로그래밍 도전에 대한 나의 도전은 호주식 투표법에서 좌절을 맛보고는 그 이후에는 책을 펴보지도 않았다는 전설이 있습니다... 그려..
아.. 원래 하려던 이야기가 이건 아니고.. 다시 유쾌하지 않았던 Jolly Jumper에 대한 이야기를 시작 해보면...
때는 바야흐로.. 2006년 11월의 어느 날... 당시 나는 부운영자로 활동 중이던 C언어 카페의 부흥을 노리고자 Programming Challenges에 대한 도전을 카페에 제안하여 게시판을 하나 운영 중이었다. 당시 11월 셋째주 문제로 선택했던 것이 바로 이 Jolly Jumper!
문제는 다음과 같았다.
유쾌한 점퍼, Jolly Jumper
n 개의 정수 (n>0)로 이루어진 수열에 대해 서로 인접해 있는 두 수의 차가 1에서 n-1까지의 값을 모두
가지면 그 수열을 유쾌한 점퍼라고 부른다. 예를 들어 다음과 같은 수열에서
1 4 2 3
앞뒤에 있는 숫자 차의 절대 값이 각각 3, 2, 1이므로 이 수열은 유쾌한 점퍼가 된다. 어떤 수열이 유쾌한
점퍼인지 판단할 수 있는 프로그램을 작성하라.
입력
각 줄 맨 앞에는 3,000 이하의 정수가 있으며 그 뒤에는 수열을 나타내는 n개의 정수가 입력된다.
출력
입력된 각 줄에 대해 "Jolly" 또는 "Not jolly"를 한 줄씩 출력한다.
입력 예
4 1 4 2 3
5 1 4 2 -1 6
출력 예
Jolly
Not jolly
그리고 투쟁의 흔적들... (2008년 2월껀 오늘 다시 코드 수정하면서 얻은 결과..)
그 당시 해답을 올리면서 썼던 글..
////////////////
Jolly Jumper를 구현하실 때 참고 사항
1. 프로그램의 종료 조건은 0 < n <= 3000 이 아닌 n이 입력된 경우
2. n = 1 일 때, 결과는 그 뒤 수열값과 상관없이 Jolly !!
먼저 고백하자면.. 예전에(대략 2년 전쯤) Jolly Jumper 문제를 C언어로 짠 적이 있습니다.
하도 삽질, 삽질하다가.. 그 때 해결한 기억이 나서 소스를 컨닝(?) 했습니다...-_-;;
제가 생각할 때 로직은 이상이 없는 것 같은데 자꾸 Wrong answer가 떠서..
경계 조건이나 좀 애매한 사항에 대해서 참고를 했죠..;;;;
PC 문제들 보면 0이 입력이 들어오면 프로그램이 종료된다던지 하는 설명이 있는 문제들도
있는데 그런 거 없으면 종료 조건 체크하는 게 참으로 모호하게 됩니다.
예전에 풀었던 어떤 문제는 문제에 언급된 입력 값의 범위로 체크를 했는데 계속 안되서 봤
더니 입력이 있는지 없는지 (표준입력에 데이터가 있는지 없는지)로 종료 조건을 체크해서
한참 삽질을 했었는데.. 이번 문제에도 특별한 언급이 없길래 (내가 두번 속으랴.. 하는 생각에)
표준입력 조사해서 프로그램이 종료될지 말지 구현했는데 계속 안되는 겁니다.. -_-;;
이번 문제는 n의 범위를 검사해서 범위 밖의 값이면 프로그램이 종료되어야 하더군요.
그리고 또 애매한 것 한 가지가 n 값으로 1이 입력되는 경우인데..
원래 문제 대로라면 n 다음 입력되는 인접한 수열의 차의 절대 값이 1부터 n-1까지 값을
가져야 jolly jumper가 되는데 n이 1이면 값의 범위가 1 ~ 0이 되버리는 황당한 시츄에이숀!
그래서 1이 입력되는 경우는 무조건 Not jolly가 되게 했는데..
예전에 푼거 대로라면 1이 입력되면 그 다음 숫자는 머 든 상관없이 Jolly가 되더군요...
1이 입력 될 때 jolly여야 하는지 Not jolly여야 하는지는 저도 잘 모르겠습니다...
(확인해 본 바로는 1인 경우는 Jolly어야 Solved가 되더군요..)
암튼 이 두가지 때문에 엄청 삽질 했네요.-_-;
결론...
1. 프로그램의 종료 조건은 0 < n <= 3000 이 아닌 n이 입력된 경우
2. n = 1 일 때, 결과는 그 뒤 수열값과 상관없이 Jolly !!
아.. 그리고.. 요새 STL을 공부 중이라 STL을 이용해서 구현해 보았습니다.
(STL 쓸 때도, 범위 잘못 지정해서 엄청 삽질 했답니다... 쯥..-_-;;)
sort() 쓰고, 집합 관계 검사하는 includes() 함수 까지 썼더니 C언어로 짰던 거 보다
성능이 2배 가량 떨어지네요-_-;;;
나중에 C언어로 짰던 것도 올리겠습니다.
(유쾌한 점퍼를 짰는데.. 이 유쾌하지 않은 기분이란..-_-;;;)
소스코드는 그 때 짠걸 봤는데.. 다시 보니 이건 왜 이렇게 짜놓은거야.. 하고 얼굴이 화끈화끈.. -_-;;
그래서 코드를 좀 정리해보았다. (이전 코드에는 로직과 입출력 루틴이 마구마구 섞여있었다..)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_NUMBER = 3000;
void sequence(
int start,
int end,
vector<int> & numbers
)
{
for ( int i = start ; i < end ; ++i )
numbers.push_back( i );
}
inline void readNumber( int & n )
{
cin >> n;
}
void readData(
int n,
vector<int> & input
)
{
int t;
for ( int i = 0 ; i < n ; ++i )
{
cin >> t;
input.push_back( t );
}
}
bool isEnd( int n )
{
return ( n < 1 || n > MAX_NUMBER );
}
void difference( vector<int> & v )
{
for ( unsigned int i = 0 ; i < v.size() - 1 ; ++i )
v[i] = abs( v[i] - v[i + 1] );
v.pop_back(); // remove the last input number
}
bool isJollyJumper(
int n,
vector<int> & numbers,
vector<int> & result
)
{
if ( n == 1 )
return true;
difference( result );
sort( result.begin(), result.end() );
return includes( result.begin(), result.end(),
numbers.begin(), numbers.begin() + n - 1 );
}
inline void printResult( bool jolly )
{
cout << ( jolly ? "Jolly" : "Not jolly" ) << endl;
}
int main()
{
int n;
vector<int> seq, data;
data.reserve( MAX_NUMBER );
seq.reserve( MAX_NUMBER - 1 );
// Generate a sequence 1 ~ 2999
sequence( 1, MAX_NUMBER, seq );
while ( 1 )
{
readNumber( n );
if ( isEnd( n ) ) break;
readData( n, data );
printResult( isJollyJumper( n, seq, data ) );
n = 0;
data.clear();
}
return 0;
}
여기서 좀 또 웃긴게 있는데-_-;;;
예전 코드를 정리하다보니 정확한 히스토리가 기억이 안나서 n = 0; 해주는 부분을 뺐더니 시간 초과(Time limit exceeded) 가 걸려버렸다.
추측컨데 아마도 결과 판정 사이트는 소스를 올리면 소스를 올린 서버에서 실행파일을 컴파일하고
실행파일 < 입력데이터
이런 식으로 indirection을 이용해서 실행하는듯 한데 실제 데이터 파일 마지막이 0은 아니고 빈문자열이 들어있어 빈문자열이 입력되면 다음에 종료 판별루틴에서 n = 0으로 처리하여 프로그램이 종료되는 것으로 보인다. (판정을 받아본 것은 아닌데 입력 데이터 파일에 enter만 입력하고 저장한 후 위와 같이 실행했을 때 프로그램이 종료되었다. 나중에 수정해서 확인해봐야겠다..)
뭐 이렇게.. 다시금 Jolly Jumper에 대한 기억을 되돌려 보고 옛날에 짜둔 코드를 읽으면서 나의 프로그래밍 스타일의 변화를 살펴보니 내가 조금은 괜찮은 프로그래머가 되어가고 있나 하는 생각을 해본다..(아니면 그 당시 너무 형편없었거나..)
진짜로.. 갈 길이 멀구나~
참고 사이트
# by | 2008/02/16 23:36 | 공부 | 트랙백 | 덧글(6)
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]