개발/python

Train Timetable

Dsp 2009. 8. 22. 01:03
이번에는 두번째 문제인 기차시간표입니다.

문제는 다음과 같습니다.


제일 가까운 기차들을 모두 이어주고,
앞뒤로 이어지지 않은 기차들을 카운트해주면 됩니다.

소스코드는 다음과 같습니다.

  1. import sys
  2. import datetime
  3.  
  4. class train:
  5.   def __init__(self, row, dir):
  6.     st = row.split(' ')[0]
  7.     end = row.split(' ')[1]    
  8.     self.start = datetime.datetime( 2009,1,1, int(st.split(':')[0]), int(st.split(':')[1]) )
  9.     self.end = datetime.datetime( 2009,1,1, int(end.split(':')[0]), int(end.split(':')[1]) )
  10.     self.dir = dir
  11.     self.reserved1 = 0
  12.     self.reserved2 = 0
  13.  
  14. def asc_start(a,b):
  15.   if a.start < b.start:
  16.     return -1
  17.   else:
  18.     return 1
  19.  
  20. def desc_end(a,b):
  21.   if a.end < b.end:
  22.     return 1
  23.   else:
  24.     return -1
  25.  
  26. if __name__=="__main__":
  27.   if len(sys.argv)>1:
  28.     inp = sys.argv[1]
  29.   else:
  30.     print "append an input file param"
  31.     sys.exit()
  32.  
  33.   f = open( inp, 'rt' )
  34.   nTC = int( f.readline() )
  35.   print 'the number of tc :', nTC
  36.  
  37.   output_file = inp.split('.')[0]+"_output.txt"
  38.   fout = open( output_file, 'wt')
  39.  
  40.   for i in range(0,nTC):
  41.     turnaround = int( f.readline() )
  42.    
  43.     NA_NB = f.readline()
  44.     NA = int( NA_NB.split(' ')[0] )
  45.     NB = int( NA_NB.split(' ')[1] )
  46.    
  47.     trains = []
  48.     for n in range(0,NA):
  49.       row = f.readline()
  50.       trains.append( train( row, 'A' ) )
  51.     for n in range(0,NB):
  52.       row = f.readline()
  53.       trains.append( train( row,'B') )
  54.  
  55.     trains.sort(desc_end)
  56.    
  57.     #process
  58.     ta = datetime.timedelta( 0, turnaround*60 )
  59.    
  60.     for t1 in trains:
  61.       if t1.reserved2>0: continue
  62.       cands = []
  63.       for t2 in trains:
  64.         if t2.reserved1>0: continue
  65.          
  66.         if ( t1.end + ta <= t2.start ) and (t1.dir != t2.dir):
  67.           cands.append( t2 )
  68.          
  69.       if cands:
  70.         cands.sort( asc_start )
  71.         min = cands[0]
  72.         #print t1.start, t1.end, t1.dir
  73.         #print '\t',min.start, min.end, min.dir
  74.        
  75.         t1.reserved2 = min.reserved1 = 1
  76.  
  77.     NA = NB = 0
  78.     for t in trains:
  79.       if t.reserved1==0:
  80.         if t.dir=='A':
  81.           NA+=1
  82.         else:
  83.           NB+=1
  84.  
  85.     # result
  86.     print 'Case #'+str(i+1)+':' ,NA, NB
  87.     fout.write( 'Case #'+str(i+1)+': ' +str(NA) + ' '+str( NB)+'\n')
  88.  
  89.   f.close()
  90.   fout.close()


실행결과는 다음과 같으며, 모두 Correct입니다.