[Python] '모두 똑같이 만들기' 알고리즘

Srini Devadas의 '퍼즐로 배우는 알고리즘 with 파이썬'에서 첫 번째 퍼즐 '모두 똑같이 만들기'를 풀어보았습니다.

 

 

1. 연이어 서있는 같은 '특징'을 가진 사람들 찾기

 

앞을 향해 놓여진 모자(F)와 그 나머지(B)가 일렬로 배열되어 있을 때, '어떻게 효율적으로 같은 방향으로 정렬할 수 있을까?'라는 문제를 풀어보는 문제입니다.

 

cap1 = ['F', 'F', 'B', 'B', 'B','F', 'B', 'B', 'B','F', 'F', 'B','F']
cap2 = ['F', 'F', 'B', 'B', 'B','F', 'B', 'B', 'B','F', 'F', 'F','F']
 
def pleaseConform(caps):
    start = forward = backward = 0
    intervals = []
    for i in range(1, len(caps)):
        if caps[start] != caps[i]:
            intervals.append((start, i-1, caps[start]))
            if caps[start] == 'F':
                forward +=1
            else:
                backward += 1
            start = i
    
    intervals.append((start, len(caps)-1, caps[start]))
    
    if caps[start] == 'F':
        forward +=1
    else:
        backward +=1
    if forward < backward:
        flip = 'F'
    else:
        flip = 'B'
    for t in intervals:
        if t[2] == flip:
            print('People in positions', t[0], 'through', t[1], 'flip your caps!')        

여기서 16번째 줄~21번째 줄의 코드는 caps 내 마지막 구간에 대해 추가하는 작업을 수행하기 위해 덧붙인 코드입니다.

 

가장 위의 for문에서 구간을 intervals에 추가하는 작업은 해당 구간을 지나쳐저 방향이 변경된 것을 인식한 뒤에야 이루어지기 때문에 마지막 구가에 대해 추가하는 작업이 더 필요하기 때문입니다.

 

 

2. 알고리즘 최적화

 

어떤 방법을 사용해야 한 번만 줄을 훑고 내려가서 최소한의 입장객들에게 모자를 뒤집어달라고 할 수 있을까요? 

 

모자를 앞으로 쓴 구간의 수와 뒤로 쓴 구간의 수는 최대 1만큼 차이가 나며, 첫 번째 사람이 만약 앞으로(F) 모자를 썼다면 앞으로 모자를 쓴 구간의 수는 절대 뒤로 모자를 쓴 구간의 수보다 작을 수 없습니다.

 

['F', 'B', 'B', 'B']

['F', 'B', 'F', 'B']

['F', 'B', 'F', 'F']

 

즉, 첫 번째 사람이 'F'라면 이와 같은 수의 'B'가 나오기 위해서는 반드시 'F'가 선행해야 하므로 'B'의 구간 수는 'F'보다 절대 많을 수 없습니다. 즉, 항상 첫 번째 구간과 반대 방향으로 모자를 쓴 구간만 모자를 뒤집으라고 요청하는 것이 가장 효율적이라는 것입니다. 이런 성질을 활용하면 한 번의 반복문을 사용해서 정렬을 구현할 수 있습니다.

 

cap1 = ['F', 'F', 'B', 'B', 'B','F', 'B', 'B', 'B','F', 'F', 'B','F']
cap2 = ['F', 'F', 'B', 'B', 'B','F', 'B', 'B', 'B','F', 'F', 'F','F']
 
def pleaseConformOnepass(caps):
    caps = caps + [caps[0]]
    for i in range(1, len(caps)):
        if caps[i] != caps[i-1]:
            if caps[i] != caps[0]:
                print('People in positions', i, end=' ')
            else:
                print(' through', i-1, 'flip your caps!')

 또한 입력 리스트의 제일 마지막에 원소를 추가해서 본래의 입력 리스트의 마지막 모자 방향이 첫 번째 모자 방향인 caps[0]과 다르다면, 처음 소개했던 코드와는 다르게 한 번의 for문으로 마지막 구간도 출력될 수 있습니다.

 

(pleaseConformOnePass에서 caps에 원소를 추가할 때 append가 아닌 단순 이어붙이기(+)를 사용하는 이유는 append를 사용하게 되면 리스트의 변화가 리스트 자체에 영구적으로 영향을 주기 때문입니다.)

 

이 코드를 실행하면 결과는 다음과 같습니다.

두 번째 코드의 pleaseConformOnepass를 cap1, cap2에 적용한 결과

 

 

1명밖에 없는데 People in positions 11 through 11 flip your caps! 라고 나오는 부분을 해결하고 싶다면 아래와 같은 코드로 수정해주는 것도 한 방법이 될 수 있습니다.

def pleaseConformOnepass(caps):
    caps = caps + [caps[0]]
    start = []
    end = []
    for i in range(1, len(caps)):
        if caps[i] != caps[i-1]:
            if caps[i] != caps[0]:
                start.append(i)
            else:
                end.append(i-1)
 
    for j in range(len(start)):
        if start[j]!=end[j]:
            print(f"People in positions {start[j]} through {end[j]} flip your caps!")
        else:
            print(f"Person at position {start[j]} flip your cap!")