The break statement, like in C, breaks out of the smallest enclosing for or while loop.
Loop statements may have an else clause; it is executed when the loop terminates through exhaustion of the list (with for) or when the condition becomes false (with while), but not when the loop is terminated by a break statement.
파이썬에서 for 나 while loop 와 함께 else 구문을 사용할 수 있다.
for loop 에서는 더이상 순회할 list 가 없을때 그리고 while loop에서는 조건문이 거짓이 될 때 else 구문이 실행된다. 하지만 loop 가 break 로 종료될 경우에는 실행되지 않는다.
This is exemplified by the following loop, which searches for prime numbers:
>>> for n in range(2, 10):
... for x in range(2, n): ... if n % x == 0: ... print n, 'equals', x, '*', n/x ... break ... else: ... # loop fell through without finding a factor ... print n, 'is a prime number' ... 2 is a prime number 3 is a prime number 4 equals 2 * 2 5 is a prime number 6 equals 2 * 3 7 is a prime number 8 equals 2 * 4 9 equals 3 * 3
Assume we need to look for the following 2D pattern:
876543 111111 111111
If we scan through the original array, we observe that the 2D pattern begins at the second row and the third column of the larger grid (the 88 in the second row and third column of the larger grid is the top-left corner of the pattern we are searching for).
So, a 2D pattern of PP digits is said to be present in a larger grid GG, if the latter contains a contiguous, rectangular 2D grid of digits matching with the pattern PP, similar to the example shown above.
Input Format
The first line contains an integer, TT, which is the number of test cases. TT test cases follow, each having a structure as described below:
The first line contains two space-separated integers, RR and CC, indicating the number of rows and columns in the grid GG, respectively.
This is followed by RR lines, each with a string of CC digits, which represent the grid GG.
The following line contains two space-separated integers, rr and cc, indicating the number of rows and columns in the pattern grid PP.
This is followed by rr lines, each with a string of cc digits, which represent the pattern PP.
Test Case Generation
Each individual test case has been generated by first specifying the size (RR and CC) of the large 2D matrix, and then randomly generating the digits in it. A limited number of digits in the larger matrix may be changed by the problem setter (no more than 5% of the total number of digits in the matrix). So the larger 2D matrix is almost-random. The pattern matrix has been manually-curated by the problem setter.
Output Format
Display 'YES' or 'NO', depending on whether (or not) you find that the larger grid GG contains the rectangular pattern PP. The evaluation will be case sensitive.
#!/bin/python3
import sys
def findPattern( grid, pattern ):
sLine = pattern[ 0 ]
for iRow, sGridLine in enumerate( grid ):
if iRow + len( pattern ) > len( grid ): break
iColumn = -1
while True:
iColumn = sGridLine.find( sLine, iColumn + 1 )
if iColumn < 0 or iColumn + len( sLine ) > len( sGridLine ):
break
for i, sPatternLine in enumerate( pattern[ 1: ] ):
if grid[ iRow + 1 + i ][ iColumn : iColumn + len( sPatternLine ) ] != sPatternLine:
break
else:
return True
return False
t = int(input().strip())
for a0 in range(t):
R,C = input().strip().split(' ')
R,C = [int(R),int(C)]
G = []
G_i = 0
for G_i in range(R):
G_t = str(input().strip())
G.append(G_t)
r,c = input().strip().split(' ')
r,c = [int(r),int(c)]
P = []
P_i = 0
for P_i in range(r):
P_t = str(input().strip())
P.append(P_t)
bFound = findPattern( G, P )
print('YES' if bFound else 'NO')
전체 배열을 순회하며 검색하여야할 배열의 첫째 열의 문자열을 포함하는지 알아본다.
포함하지 않는다면, 다음 전체 배열의 다음 줄로 간다.
포함한다면, 다음 열의 같은 행부터 검색할 배열의 문자열과 같은 길이의 문자열이 검색할 배열의 다음 열과 같은지 비교한다. 이것을 검색할 배열의 모든 열에 대하여 비교하고 이것이 모두 일치한다면, 검색하고자 하는 배열이 존재 하는 것이다.
주의하여야할 점은 검색할 배열의 문자열이 전체 배열의 같은 열에서 여러번 반될 수 있다. 위 코드에서 while True 부분이 같은 열에서 여러번 찾도록 해준다.
Given N ropes of lengths L1, L2, L3, L4, …, Ln, make an algorithm to join every rope to get a final rope of length L1 + L2 + … + Ln.
You can only join two ropes at a time and the cost of joining the two ropes would be the sum of two ropes i.e Li + Lj. Every time you join the ropes, the cost should be the minimum possible.
1. should use min heap. https://en.wikipedia.org/wiki/Binary_heap
2. Building minimum heap (min-heapify takes O( log n) and min-heapify is called n times = O( n log n ) )
3. using python 3.5 and heapq
import heapq
def join_ropes( _list ):
h = []
#build min heap
for i in a:
heapq.heappush( h, i)
# join ropes
while len( h ) > 1:
rope0 = heapq.heappop( h )
rope1 = heapq.heappop( h )
heapq.heappush( h, rope0 + rope1 )
return heapq.heappop( h )
