[baekjoon]python #2469 사다리 타기

https://www.acmicpc.net/problem/2469

2469번: 사다리 타기

 

#처음에 생각했던 방법

처음과 도착의 이동된 위치의 갯수를 각각 체크해 이동된 숫자를 더해 2로 나누었다.

위의 숫자와 ladder에 받은 '-'와 비교해 그 차이가 '??'에 들어가는 '-'의 갯수인 점을 발견했다.

만약 ladder의 '-'의 갯수가 체크된 수보다 작다면 ''??'에는 'xx'가 들어가게 되고,

같다면 '**'로 채워지는 로직.. 그러나 ??에 '-','*'의 배치에 어려움이 있는 코드라 결국 폐기했다.

k = int(input()) # 사람수
n = int(input()) # 사다리줄 수

result = list(map(ord,input()))
ladder = [list(map(str,input())) for _ in range(n)]

alp = []
for i in range(k):
    alp.append(ord('A')+i)

vs = []
for j in range(k):
    a = alp[j]-result[j]
    vs.append(a)

sumV=0
for v in vs:
    if v >0:
        sumV+=v

cnt=0
for y in range(len(ladder)):
    for x in range(len(ladder[y])):
        if ladder[y][x] == '-':
            cnt+=1

output_cnt = cnt-sumV
if output_cnt <0:
    print('x'*(k-1))
elif output_cnt == 0:
    print('*'*(k-1))
else:
    pass  #내가 구현하지 못한 부분...

print(vs)

 

#최종 코드

스터디원의 아이디어를 디벨롭했다.

물음표 위와 물음표 아래를 비교해서 '??'부분에 넣어주는 방법

처음에는 ladder배열에서 사다리를 직접 타야하나 했지만,

start배열과 result배열을 직접 swap하여 비교하면 되는 문제였다.

def find():
    global ladder,result,k,n
    start = [] #시작점의 ABCD... 넣어 주기위한 빈 리스트
    for i in range(k):
        start.append(chr(ord('A') + i))
    mark = 0 #물음표 있는 줄

    #물음표 위 알파벳
    for y in range(n):
        if ladder[y][0] == '?':
            mark = y
            break
        else:
            for x in range(k-1):
                if ladder[y][x] == '-':
                    start[x],start[x+1] = start[x+1],start[x]

    #물음표 아래 알파벳
    for y in reversed(range(mark+1,n)): #아래부터 위로!
        if ladder[y][0] == '?':
            break
        else:
            for x in range(k-1):
                if ladder[y][x] == '-':
                    result[x],result[x+1] = result[x+1],result[x]

    answer=[]
    #물음표 위와 아래 비교
    for i in range(k-1):
        if start[i] == result[i]: #같을때
            answer.append('*')
        else: #다를때
            if start[i] == result[i+1]: #옆(오른쪽) 인덱스랑 같으면
                answer.append('-')
            elif i!=0 and start[i]==result[i-1]: #옆(왼쪽) 인덱스랑 같으면, out of index 방지를 위해 i가 0인걸 배제
                answer.append('*')
            else: #어떤 구성으로도 만들 수 없을 때
                return (''.join(['x' for _ in range(k - 1)]))

    return ''.join(answer)



k = int(input()) # 사람수
n = int(input()) # 사다리줄 수
result = list(map(str,input())) #도착했을 때
ladder = [list(map(str,input())) for _ in range(n)] #사다리의 배열

ret = find()
print(ret)