-
Notifications
You must be signed in to change notification settings - Fork 5
algorithm problem 9
Jongbin Oh edited this page Jun 8, 2013
·
1 revision
-
Jolly.java
import java.io.*; public class Jolly { public static void main(String args[]) { Jolly j = new Jolly(); String[] token = new String[3000]; token = j.ReadLine().split(" "); if(Integer.parseInt(token[0]) < 0 || Integer.parseInt(token[0]) > 3000) return; if( j.ParseInput(token) ) System.out.println("Jolly"); else System.out.println("Not Jolly"); } public boolean ParseInput(String[] token) { boolean IsJully = true; int subResult; //System.out.print("Input : "+input+",Result :"); for(int i=0; i < token.length; i++) { //System.out.println(i + " :" + Integer.parseInt(t[i])); if( i != 0 ) { subResult = Math.abs(Integer.parseInt(token[i])-Integer.parseInt(token[i-1])); //System.out.print(" "+subResult); if(!IsContainData(token,subResult)) { IsJully = false; break; } } } //System.out.println("\nIsJully : " + IsJully); return IsJully; } public boolean IsContainData(String[] source, int data) { boolean result = false; for(int i=0; i< source.length; i++) { if( Integer.parseInt(source[i]) == data ) { result = true; break; } } return result; } public String ReadLine() { String data = null; try { BufferedReader is = new BufferedReader(new InputStreamReader(System.in)); data = is.readLine(); } catch(IOException e) { System.out.println("IOException " +e); } return data; } } -
JollyTest.java
import junit.framework.TestCase; public class JollyTest extends TestCase { Jolly j = new Jolly(); public void testParseInput() { assertEquals("Result1",j.ParseInput("1 2 3".split(" ")),true); assertEquals("Result2",j.ParseInput("1 9 10".split(" ")),false); assertEquals("Result3",j.ParseInput("1 5 3".split(" ")),false); assertEquals("Result4",j.ParseInput("1 2 5 3".split(" ")),true); assertEquals("Result5",j.ParseInput("1 50 -30".split(" ")),false); assertEquals("Result6",j.ParseInput("1 -1 1 2".split(" ")),true); assertEquals("Result7",j.ParseInput("4 1 4 2 3".split(" ")),true); assertEquals("Result8",j.ParseInput("5 1 4 2 -1 6".split(" ")),false); assertEquals("Result9",j.ParseInput("0 100 99".split(" ")),false); } public void testIsContainData() { assertEquals("Result1",j.IsContainData("1 2 3 7".split(" "),7),true); assertEquals("Result1",j.IsContainData("1 2 3 7".split(" "),3),true); assertEquals("Result1",j.IsContainData("1 2 3 7".split(" "),-4),false); assertEquals("Result2",j.IsContainData("1 2 3 7".split(" "),4),false); } }
-
JollyMain.java
import java.io.*; public class JollyMain { public static void main(String[] args) { JollyMain j = new JollyMain(); String[] data = j.readLine().split(" "); if(j.parseData(data)) System.out.println("Jolly"); else System.out.println("Not jolly"); } public static boolean parseData(String[] data) { int[] intList = new int[data.length]; boolean[] checkMap= new boolean[data.length]; for(boolean curItem : checkMap){ curItem = false; } int sub; boolean result = false; if( data.length == 1) return false; for(int j=0; j < data.length ;j++) { intList[j] = Integer.parseInt(data[j]); } for(int i=0; i < intList.length -1 ; i++) { sub = Math.abs(intList[i] - intList[i+1]); if(isArrayBound(intList, sub)){ checkMap[sub] = true; } } result = isContain(checkMap); return result; } public static boolean isArrayBound(int[] data, int sub) { return sub>0 && sub < data.length; } public static boolean isContain(boolean [] data) { for(int i=1 ;i<data.length; i++) { if(!data[i]){ return false; } } return true; } public String readLine() { String data = null; try { BufferedReader is = new BufferedReader(new InputStreamReader(System.in)); data = is.readLine(); } catch(IOException e) { } return data; } } -
JollyMainTest.java
import junit.framework.TestCase; public class JollyMainTest extends TestCase { public void testMain() { } public void testParseData() { assertEquals("1",JollyMain.parseData(new String[]{"1","2","3","4"}),false); assertEquals("2",JollyMain.parseData(new String[]{"1","5","3","2"}),false); assertEquals("3",JollyMain.parseData(new String[]{"1","-1","10","2"}),false); assertEquals("4",JollyMain.parseData(new String[]{"1","4","2","3"}),true); assertEquals("5",JollyMain.parseData(new String[]{"1","4","2","-1","6"}),false); } public void testIsContain() { // assertEquals("1",JollyMain.isContain(new int[]{1,2,3,4},2),true); // assertEquals("2",JollyMain.isContain(new int[]{1,2,3,4},5),false); // assertEquals("3",JollyMain.isContain(new int[]{1,2,3,4},1),true); assertTrue(JollyMain.isContain(new boolean[]{true,true})); assertFalse(JollyMain.isContain(new boolean[]{true,false})); } public void testIsArrayBound(){ int [] checkArray = new int[]{1,2,3,4}; assertFalse(JollyMain.isArrayBound(checkArray, 4)); assertTrue(JollyMain.isArrayBound(checkArray, 3)); assertFalse(JollyMain.isArrayBound(checkArray, 0)); assertFalse(JollyMain.isArrayBound(checkArray, -1)); assertFalse(JollyMain.isArrayBound(checkArray, 44855)); } }
-
Accept 한번 받아 보겠다고... Accept 받는 데 딱 1시간 30분 걸렸네요.
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool IsJollyJumpers(vector<int> &vSeq) { if(vSeq.size() == 0) return false; if(vSeq.size() == 1) return true; vector<int> vDiff; for(int i = 0; i < vSeq.size() - 1; i++) { vDiff.push_back(abs(vSeq[i] - vSeq[i + 1])); } sort(vDiff.begin(), vDiff.end()); for(int i = 0; i < vDiff.size(); i++) { if(vDiff[i] != (i + 1)) return false; } return true; } int main() { int n = 0; vector<int> vSeq; while(cin >> n) { if(n < 0 || n > 3000) continue; int temp = 0; for(int i = 0; i < n; i++) { cin >> temp; vSeq.push_back(temp); } while(cin.get() != '\n'); bool bRet = IsJollyJumpers(vSeq); cout << (bRet == true ? "Jolly" : "Not jolly") << endl; vSeq.clear(); } return 0; }
- 웹사이트에서 테스트는 성공하지 못했습니다. 이거 꼭 웹상에서 테스트를 성공시키는데 시간과 노력을 들일 필요가 있는지 잘 모르겠네요. 몇번 올리기를 반복하자니 승질만 ... --a;;;
import java.util.*;
import java.io.*;
public class JollyJumper {
public static void main(String args[]) throws IOException
{
// 데이터 읽기
BufferedReader reader = new BufferedReader( new InputStreamReader( System.in));
String line = reader.readLine();
// 데이터 파싱
int[] param = getParam(line);
if (param[0] <= 0 || param[0] > 3000)
{
System.out.println("Error: invalid range of data");
return;
}
// Jumper 객체 생성 및 초기화
Jumper jumper = new Jumper(param[0]);
// Jolly Jumper 체크
for (int i=1; i<param[0]-1; i++)
{
int distance = Math.abs(param[i] - param[i+1]);
if (jumper.isEnable(distance))
jumper.setDisable(distance);
else
{
System.out.println("Not Jolly");
return;
}
}
System.out.println("Jolly Jumper");
return;
}
static int[] getParam(String line)
{
StringTokenizer tokens = new StringTokenizer(line, " ");
int size = tokens.countTokens();
int[] param = new int[size+1];
int i=0;
while (tokens.hasMoreTokens())
{
int value = Integer.parseInt(tokens.nextToken());
param[i] = value;
i++;
}
return param;
}
}
public class Jumper {
private boolean[] bitBox;
private int length;
Jumper(int size)
{
length = size;
bitBox = new boolean[size];
for (int i=0; i<size; i++)
{
bitBox[i] = true;
}
bitBox[0] = false;
}
boolean isEnable(int distance)
{
if (isValidIndex(distance) && bitBox[distance])
return true;
return false;
}
void setDisable(int distance)
{
bitBox[distance] = false;
}
boolean isValidIndex(int distance)
{
if (distance > 0 && distance < length)
return true;
return false;
}
}
- 이거 UVa 어디에서 submit 할 수 있나요?
- Browse Problems 에서 못 찾겠네요.
- Jolly Jumpers
- 찾는 요령이라도 있으신거에요? 검색해도 안 나오던데...
/* @JUDGE_ID:parkpd 10038 C "test" */
/* @BEGIN_OF_SOURCE_CODE */
#include <iostream>
#include <vector>
#include <set>
#include <strstream>
using namespace std;
//#define _UNIT_TEST
#ifdef _UNIT_TEST
#include "../../UnitTest++/src/UnitTest++.h"
int main()
{
UnitTest::RunAllTests();
char temp;
cin >> temp;
return 0;
}
#endif
class CJollyJumpers
{
public:
CJollyJumpers() {}
bool IsJollyJumper(string s);
bool IsJollyJumper(int count, istream& input);
protected:
vector<int> m_Nums;
set<int> m_Diffs;
};
bool CJollyJumpers::IsJollyJumper(string s)
{
istrstream input(s.c_str());
int count = 0;
input >> count;
// count > 0 이상임은 문제에서 보장하고 있다.
return IsJollyJumper(count, input);
}
bool CJollyJumpers::IsJollyJumper(int count, istream& input)
{
int num = 0;
int old = 0;
input >> num;
m_Nums.push_back(num);
old = num;
for (int i = 1; i < count; ++i)
{
input >> num;
m_Nums.push_back(num);
m_Diffs.insert(abs(num - old));
old = num;
}
// Jolly Jumper 인지를 확인하는 방법.
return (m_Diffs.size() + 1) == count;
}
#ifndef _UNIT_TEST
char s[10000000];
int main()
{
int count;
while (cin >> count)
{
CJollyJumpers jumper;
if (jumper.IsJollyJumper(count, cin))
{
cout << "Jolly\n";
}
else
{
cout << "Not Jolly\n";
}
}
return 0;
}
#else
TEST_FIXTURE(CJollyJumpers, m_Nums)
{
m_Nums.push_back(1);
CHECK_EQUAL(1, m_Nums.size());
}
TEST_FIXTURE(CJollyJumpers, IsJollyJumper_1)
{
string input = "4 1 4 2 3";
CHECK(IsJollyJumper(input));
CHECK_EQUAL(4, m_Nums.size());
CHECK_EQUAL(3, m_Diffs.size());
}
TEST_FIXTURE(CJollyJumpers, IsJollyJumper_2)
{
string input = "5 1 4 2 -1 6";
CHECK(!IsJollyJumper(input));
CHECK_EQUAL(5, m_Nums.size());
CHECK_EQUAL(3, m_Diffs.size());
}
TEST_FIXTURE(CJollyJumpers, IsJollyJumper_3)
{
string input = "1 1";
CHECK(IsJollyJumper(input));
CHECK_EQUAL(1, m_Nums.size());
CHECK_EQUAL(0, m_Diffs.size());
}
#endif
/* @END_OF_SOURCE_CODE */
-- Library
function fwrite (fmt, ...)
return io.write(string.format(fmt, unpack(arg)))
end
function SwapBySize(i1, i2)
if (i2 < i1) then
return i2, i1
end
return i1, i2
end
function IsBetween(i, i1, i2)
i1, i2 = SwapBySize(i1, i2)
return i1 <= i and i <= i2
end
-- UnitTest
UnitTest = {test = 0, success = 0, failed = 0}
function UnitTest:new(o)
o = o or {}
setmetatable(o, self)
self.__index = self
return o
end
function UnitTest:ShowResult()
if UnitTest.failed == 0 then
fwrite("Success : %d tests passed\n", UnitTest.success)
else
fwrite("Failed : %d in tests %d\n", UnitTest.failed, UnitTest.test)
end
end
function Check(name, actual)
UnitTest.test = UnitTest.test + 1
if not actual then
fwrite("Check Failed in %s\n", name)
UnitTest.failed = UnitTest.failed + 1
else
UnitTest.success = UnitTest.success + 1
end
end
function CheckEqual(name, expect, actual)
UnitTest.test = UnitTest.test + 1
if (expect ~= actual) then
fwrite("CheckEqual Failed in %s. %s expected but actual is %s\n", name, tostring(expect), tostring(actual))
UnitTest.failed = UnitTest.failed + 1
else
UnitTest.success = UnitTest.success + 1
end
end
-- Algorithm
Solver = {m_Count = 0, m_Nums = {}}
function Solver:new(o)
o = o or {m_Count = 0}
-- 일종의 자식 클래스용 멤버 변수 정의. lua 에서의 class 개념을 숙지할 것
o.m_Nums = {}
setmetatable(o, self)
self.__index = self
return o
end
function Solver:PushNum(o)
self.m_Nums[#self.m_Nums + 1] = o
end
function Solver:PrintResult()
diffs = {}
-- lua 에서는 for i = 2, 1 do 해도 loop 을 돌기 때문에
-- 이런 if 문이 필요하다. 이거 없앨 수 있는 방법은?
-- if 문 필요없음. 뭔가 다른게 문제였구만...
if (2 <= #self.m_Nums) then
for i = 2, #self.m_Nums do
diff = math.abs(self.m_Nums[i - 1] - self.m_Nums[i])
if (IsBetween(diff, 1, self.m_Count - 1)) then
diffs[diff] = 1
end
end
end
if (#diffs == self.m_Count - 1) then
return "Jolly"
else
return "Not jolly"
end
end
-- test part
do
local c = Solver:new{}
CheckEqual("m_Count", 0, c.m_Count)
--- PushNum
c:PushNum(1)
c:PushNum(3)
CheckEqual("PushNum1", 1, c.m_Nums[1])
CheckEqual("PushNum3", 3, c.m_Nums[2])
--- IsBetween
Check("IsBetween 2 1 3", IsBetween(2, 1, 3))
Check("IsBetween 7 2 3", not IsBetween(7, 2, 3))
Check("IsBetween 2 3 1", IsBetween(2, 3, 1))
Check("IsBetween 5 3 1", not IsBetween(5, 3, 1))
end
do
local c = Solver:new{m_Count = 4}
c:PushNum(1)
c:PushNum(4)
c:PushNum(2)
c:PushNum(3)
CheckEqual("size1", 4, #c.m_Nums)
--- PrintResult
CheckEqual("PrintResult1", "Jolly", c:PrintResult())
end
do
local c = Solver:new{m_Count = 5}
c:PushNum(1)
c:PushNum(4)
c:PushNum(2)
c:PushNum(-1)
c:PushNum(6)
CheckEqual("size2", 5, #c.m_Nums)
--- PrintResult
CheckEqual("PrintResult2", "Not jolly", c:PrintResult())
end
do
local c = Solver:new{m_Count = 1}
c:PushNum(1)
CheckEqual("size3", 1, #c.m_Nums)
--- PrintResult
CheckEqual("PrintResult3", "Jolly", c:PrintResult())
end
UnitTest:ShowResult()
-- input part
while 1 do
local count = io.read("*number")
if count == nil then
break
end
local c = Solver:new{m_Count = count}
for i = 1, count do
c:PushNum(io.read("*number"))
end
print(c:PrintResult())
end
-
흑 아무리 해봐도 wrong answer이네요 ㅠㅠ
-
일단 올립니다.
-
소스 코드
import java.util.ArrayList; import java.util.Scanner; class Main implements Runnable{ public static void main(String args[]) // entry point from OS { Main myWork = new Main(); // Construct the bootloader myWork.run(); // execute } public void run() { Problem9 pro = new Problem9(); pro.run(); } } class Problem9 implements Runnable{ public ArrayList<Integer> parserLine(String line){ if(line == null) return null; String [] numbers = line.split(" "); ArrayList<Integer> result = new ArrayList<Integer>(numbers.length); for(String row: numbers){ if( !row.equals("")){ result.add(Integer.parseInt(row)); } } return result; } public boolean isJollyJumper(ArrayList<Integer> list){ if(list == null) return false; int length = list.size(); if(length<2 || length>3000) return false; boolean [] mark = new boolean[length]; for(int i =0; i<mark.length;i++){ mark[i] = false; } for(int i=0;i<length-1;i++) { int index = list.get(i) - list.get(i+1); index = Math.abs(index); if(index >0 && index < length && !mark[index]){ mark[index] = true; }else{ return false; } } return true; } public void run() { Scanner scan = new Scanner(System.in); while(scan.hasNextInt()){ int n = scan.nextInt(); ArrayList<Integer> nums = new ArrayList<Integer>(n); for(int i=0;i<n;i++){ int temp = scan.nextInt(); nums.add(temp); } //System.out.println(nums); String result; if(isJollyJumper(nums)){ result = "Jolly"; }else{ result = "Not jolly"; } System.out.println(result); } } } -
테스트 코드
package org.and.algo; import java.util.ArrayList; import junit.framework.TestCase; public class Problem9TestCase extends TestCase { public void testParseLine(){ Problem proble9 = new Problem(); String line = "3 2 1 0"; ArrayList<Integer> result = proble9.parserLine(line); assertEquals(result.size(), 4); assertEquals(result.get(0), new Integer(3)); assertEquals(result.get(1), new Integer(2)); line = "100 -1 5 10 5"; result = proble9.parserLine(line); assertEquals(result.size(), 5); assertEquals(result.get(1), new Integer(-1)); } public void testJollyJumper(){ Problem proble9 = new Problem(); String line = "4 3 2 1 0"; ArrayList<Integer> list = proble9.parserLine(line); assertFalse(proble9.isJollyJumper(list)); line = "4 1 4 2 3"; list = proble9.parserLine(line); assertTrue(proble9.isJollyJumper(list)); line = "5 1 4 2 -1 3"; list = proble9.parserLine(line); assertFalse(proble9.isJollyJumper(list)); } }
-
문제를 이해하는게 아직은 어렵다.
#ifdef _UNIT_TEST #include "UnitTest++.h" #endif #include <iostream> #include <list> #include <set> class CJollySeries { public: CJollySeries(){}; void Clear() { m_Series.clear(); m_DiffSet.clear(); } void AddNumber( int number ) { m_Series.push_back( number ); } bool IsJolly() { int seriesCount = m_Series.size(); if( seriesCount == 0 ) return false; if( seriesCount == 1 ) return true; std::list<int>::iterator begin = m_Series.begin(); int prev = *begin; ++begin; for( ;begin != m_Series.end(); ++begin ) { int cur = *begin; int diff = abs(cur - prev); if( diff <= 0 || diff >= seriesCount ) return false; std::pair< std::set<int>::iterator, bool > result = m_DiffSet.insert( diff ); if( result.second == false ) return false; prev = cur; } return true; } private: std::set< int > m_DiffSet; std::list< int > m_Series; }; int main() { #ifdef _UNIT_TEST if( UnitTest::RunAllTests() ) { ; } #endif CJollySeries jollySeries; std::string buf; int count; while( scanf("%d", &count) == 1 ) { jollySeries.Clear(); int number; while( count-- ) { std::cin >> number; jollySeries.AddNumber( number ); } if( jollySeries.IsJolly() ) std::cout << "Jolly" << std::endl; else std::cout << "Not jolly" << std::endl; char buf[10000]; gets(buf); } return 0; } #ifdef _UNIT_TEST TEST( jolly ) { CJollySeries jolly; jolly.Clear(); jolly.AddNumber( 1 ); jolly.AddNumber( 4 ); jolly.AddNumber( 2 ); jolly.AddNumber( 3 ); CHECK_EQUAL( true, jolly.IsJolly() ); jolly.Clear(); jolly.AddNumber( 1 ); jolly.AddNumber( 4 ); jolly.AddNumber( 2 ); jolly.AddNumber( -1 ); jolly.AddNumber( 6 ); CHECK_EQUAL( false, jolly.IsJolly() ); jolly.Clear(); jolly.AddNumber( 1 ); jolly.AddNumber( 4 ); jolly.AddNumber( 2 ); jolly.AddNumber( 3 ); jolly.AddNumber( 1 ); CHECK_EQUAL( false, jolly.IsJolly() ); jolly.Clear(); jolly.AddNumber( 1 ); jolly.AddNumber( 4 ); jolly.AddNumber( 2 ); jolly.AddNumber( 3 ); jolly.AddNumber( 3 ); CHECK_EQUAL( false, jolly.IsJolly() ); jolly.Clear(); jolly.AddNumber( 1 ); jolly.AddNumber( 4 ); jolly.AddNumber( 2 ); jolly.AddNumber( 3 ); jolly.AddNumber( 2 ); CHECK_EQUAL( false, jolly.IsJolly() ); } #endif