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

문제 풀이

문제에서도 한눈에 알 수 있듯이 그래프 탐색을 하는 문제다.

문제를 간략하게 다시 설명하자면 0은 비어있는 땅, 1은 배추가 있는 땅이고 각 케이스마다 배추가 이어져있는 구역을 세서 출력하면 된다.

그래프를 탐색하는 방법은 스택을 쓰는지, 큐를 쓰는지에 따라 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)으로 나뉘는데 둘 다 시간 복잡도는 비슷하므로 편한 방식으로 구현하면 된다.

필자는 최단 거리를 찾을 때 BFS가 유리하므로 보통 BFS로 구현한다.

바로 전체 코드를 확인해 보자.

testcase=int(input())
dir=[[-1,0],[0,1],[1,0],[0,-1]]
for i in range(testcase):
    queue=[]
    res=0
    M,N,K=map(int,input().split())
    graph=[[0 for j in range(M)]for k in range(N)]
    for j in range(K):
        tempm,tempn=map(int,input().split())
        graph[tempn][tempm]=1
    for j in range(N):
        for k in range(M):
            if graph[j][k]==1:
                res+=1
                queue.append([j,k])
                graph[j][k]=0
                while len(queue)>0:
                    tempn,tempm=queue.pop(0)
                    for a in range(len(dir)):
                        dx=tempn+dir[a][0]
                        dy=tempm+dir[a][1]
                        if 0<=dx<N and 0<=dy<M and graph[dx][dy]==1:
                            graph[dx][dy]=0
                            queue.append([dx,dy])
    print(res)

1번째 줄은 테스트 케이스만큼 반복하기 위한 변수이고 2번째 줄은 각 노드에서 탐색 방향(위, 오른쪽, 아래, 왼쪽)을 묶어놓은 리스트이다.

이렇게 방향을 리스트로 묶으면 4가지 방향을 탐색할 때 반복문으로 해결할 수 있다는 장점이 있기에 꼭 잊지 말길 바란다.

대부분은 4가지 방향이지만 가끔 대각선도 고려하는 8가지 방향 문제도 있는데 단순하게 방향을 고려해서 8개의 리스트를 넣으면 된다.

4번째 줄의 queue는 큐를 사용함으로써 BFS 방식을 쓰기 위해 선언한 리스트이다.

가끔 리스트를 큐 방식으로 쓸 때 시간 초과가 나는 경우가 있는데 이는 pop() 함수에서 마지막 원소부터 탐색하기 때문에 첫 번째 원소를 제거하기 위해서는 O(n)의 시간 복잡도가 걸리기 때문이다.

그럴 경우엔 deque 모듈을 사용하면 O(1)로 첫 번째 원소에 삽입하고 삭제할 수 있다.

8번째 줄은 배추의 위치를 갱신하는 반복문이고 11번째 줄부터는 그래프를 전체 탐색하면서 배추 구역을 카운트하는 반복문이다.

13번째 줄은 배추가 있을 경우 카운트를 하고 인접한 배추 구역을 0으로 바꾸는 작업이다.

보통 원본 그래프를 변경하지 않기 위해 visited로 그래프와 똑같은 크기의 리스트를 선언하고 방문한 노드인지 아닌지 체크하여 중복된 방문을 방지하는데 해당 문제에서는 단지 배추 구역만 세면 되므로 원본 리스트를 변경해도 상관없어서 아예 0으로 바꿨다.

또한 20, 21번째 줄에서 탐색할 노드의 위치를 계산하여 따로 변수에 저장하는 이유는 미리 값을 저장해놔야 그래프 크기 안인지 배추가 있는 노드인지 체크할 때 불필요한 연산 횟수를 줄일 수 있기 때문에 값을 저장하는 것을 추천한다.

탐색 방향을 고려할 필요도 없고 단지 구역만 세면 되기 때문에 그래프 문제 중에서도 꽤 쉬운 편에 속한다고 생각한다.

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

문제 풀이

2차원 그래프에서도 상당히 쉬운 편에 속하는 문제였다.

그림의 가로길이는 짝수이며 접었을 때 물감이 겹치는 부분도 없다고 하니 그냥 구간을 절반으로 나눠 물감이 있으면 반대편에도 추가하는 방식으로 풀면 되는 브론즈다운 문제였다.

상당히 쉬우니 바로 전체 코드로 넘어가겠다.

n,m=map(int,input().split())
graph=[]
for i in range(n):
    temp=list(input())
    for j in range(m//2):
        if temp[j]!='.':
            temp[m-j-1]=temp[j]
        elif temp[m-j-1]!='.':
            temp[j]=temp[m-j-1]
    graph.append(temp)
    
for i in range(len(graph)):
    for j in range(len(graph[i])):
        print(graph[i][j],end="")
    print()

각 줄을 입력받으면서 바로 물감을 갱신한 뒤 그래프에 추가하여 출력하는 방식으로 구현했다.

5번째 줄이 물감을 갱신하는 반복문이며 구간을 절반으로 나눠 6번째 줄은 첫 문자부터 절반 부분까지, 8번째 줄은 뒷 문자부터 절반 부분까지 물감이 있으면 반대편에 추가하고 완료되면 그래프에 추가했다.

그리고 완전 탐색을 통해 그래프 출력만 하면 되는 쉬운 문제였다.

만약에 인덱싱 부분이 헷갈린다면 작은 숫자를 몇 개 대입해보면 쉽게 해결할 수 있을 것이다.

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

문제 풀이

전형적으로 이진 트리(Binary Tree)와 트리 순회(Tree Traversal)에 대한 문제다.

만약 이진 트리에 대해 처음 듣거나 익숙하지 않은 사람은 이전 포스팅을 참고하여 이해하고 오는 것이 좋을 것 같다.

https://khsung0.tistory.com/24

문제는 전위 순회한 결과가 주어지고 이를 후위 순회한 결과를 출력하면 된다.

알고리즘 외적으로도 고려해야 할 부분이 많아서 상당히 골치 아팠던 문제기도 하다.

처음 생각한 풀이법은 노드의 수는 10,000개 이하고 전위 순회의 결과가 입력으로 주어지니 전위 순회 순서대로 트리에 삽입하여 완성된 트리를 후위 순회하여 출력하는 방식을 생각했었다.

하지만 생각치 못하게 시간 초과와 메모리 초과가 떠서 틀렸었다.

다음은 불합격한 코드이다.

import sys
sys.setrecursionlimit(10**6)

binary_tree={}        #이진 트리를 위한 딕셔너리 선언
while True:
    try:
        num=int(input())
        if len(binary_tree)==0:        #빈 트리일 때
            root=num                   #루트로 설정
            binary_tree[root]=['*','*']
        else:
            curr=root
            while True:
                #왼쪽 서브 트리일 때
                if num<curr:
                    #왼쪽 노드가 없을 때
                    if binary_tree[curr][0]=='*':
                        binary_tree[curr][0]=num
                        binary_tree[num]=['*','*']
                        break
                    #왼쪽 자식 노드로 이동
                    else:
                        curr=binary_tree[curr][0]
                #오른쪽 서브 트리일 때
                else:
                    #오른쪽 노드가 없을 때
                    if binary_tree[curr][1]=='*':
                        binary_tree[curr][1]=num
                        binary_tree[num]=['*','*']
                        break
                    #오른쪽 자식 노드로 이동
                    else:
                        curr=binary_tree[curr][1]
    except:
        break

def postorder(curr):
    #왼쪽 자식 노드로 이동
    if binary_tree[curr][0]!='*':
        postorder(binary_tree[curr][0])
    #오른쪽 자식 노드로 이동
    if binary_tree[curr][1]!='*':
        postorder(binary_tree[curr][1])
    #현재 노드 출력
    print(curr)

postorder(root)

2번째 줄은 파이썬에서 기본 재귀 깊이 제한이 1000이기 때문에 1000000으로 세팅하는 코드이다.

이 때문에 런타임 에러(Recursion Error)가 뜬 것이다.

또한 입력받는 부분에서 어디까지 받는다는 제한이 없으므로 try except 구문을 사용하여 예외가 발생하기 전까지 입력을 받고 트리에 추가하는 방식으로 하였다.

예외가 발생하면 그대로 트리를 후위 순회하여 출력했는데 불합격한 것을 보니 다른 방식을 생각해야 했다.

고민하던 중에 전위 순회는 현재 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순으로 탐색하고 후위 순회는 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 현재 노드 순으로 탐색하기 때문에 현재 노드를 출력하는 타이밍을 조절해야겠다는 생각이 들었고 현재 노드보다 작은 숫자는 왼쪽 서브 트리, 큰 숫자는 오른쪽 서브 트리로 구분 지을 수 있겠다는 생각이 들었다.

따라서 리스트를 기준으로 첫 번째 원소는 현재 노드라 마지막에 출력하고 현재 노드보다 작은 원소들의 리스트는 왼쪽 서브 트리로 여겨 재귀 호출, 큰 원소들의 리스트는 오른쪽 서브 트리로 여겨 재귀 호출하면 차례대로 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 현재 노드 순으로 출력될 것이라 생각했고 역시 통과했다.

다음은 통과한 전체 코드이다.

import sys
sys.setrecursionlimit(10**6)

#입력받을 원소 리스트
num_list=[]
while True:
    try:
        num=int(input())
        num_list.append(num)
    except:
        break

def postorder(left,right):
    #순서 역전시 종료
    if left>right:
        return
    else:
        mid=right+1        #분할 기준
        for i in range(left+1,right+1):
            #해당 원소가 현재 노드보다 크다면 그 전까지는 왼쪽 서브 트리,
            #해당 원소 이후는 오른쪽 서브 트리이다.
            if num_list[left]<num_list[i]:
                mid=i
                break
        postorder(left+1,mid-1)
        postorder(mid,right)
        print(num_list[left])

postorder(0,len(num_list)-1)

트리 생성이 아닌 단순히 리스트에 원소를 입력 받으므로 입력 받는 부분은 전보다 더 간단해졌다.

시작은 전체 리스트의 길이부터 시작하고 가장 첫 번째 원소는 현재 노드, 그 이후부터 반복문을 돌면서 현재 노드보다 큰 원소가 있다면 그 전까지는 왼쪽 서브 트리, 큰 원소부터 이후는 오른쪽 서브 트리로 구분지어 재귀호출한다.

만약 큰 원소가 없을 경우를 대비해 mid=right+1을 함으로써 없으면 현재 노드를 제외한 나머지를 왼쪽 서브 트리로 보내고 두 번째 호출하는 재귀 함수는 순서가 역전되어 종료되도록 구현하였다.

인덱스를 접근하고 관리하는 방법에서 다소 헷갈리는 부분이 있고 알고리즘 외적으로도 재귀 깊이를 변경한다든지 입력받는데 처리해줘야 하는 부분이 있는 문제였다.

또한 해당 코드를 PyPy3로 제출하면 메모리 초과가 뜬다.

PyPy3가 Python3보다 연산이 빠르기에 안전하게 하기 위해 PyPy3로 먼저 제출했었는데 자료를 찾아보니 PyPy3는 최대 재귀 깊이는 제한이 없으나 10만 단위 이상으로 들어가면 Stack Overflow가 발생하여 재귀에 약하다는 정보를 얻을 수 있었다.

따라서 시간 초과가 뜬다면 PyPy3로, 재귀를 사용하여 메모리 초과가 뜬다면 Python3으로 제출해야한다는 지식을 알게 되었다.

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

문제 풀이

전형적으로 백트래킹을 이용하면 풀 수 있는 문제다.

지문에서 N번째 숫자를 묻고 N은 1,000,000(백만) 이하의 자연수 혹은 0이므로 상당히 큰 숫자들을 비교해야 할 것 같지만 정작 주의해야 할 조건은 딱 하나다.

1. 앞 자릿수부터 뒤로 갈수록 숫자가 작아져야 한다.

예시에 나온 322처럼 같은 숫자가 연속해서 등장해도 감소하는 수가 아니므로 생각 가능한 최대 숫자는 9876543210이다.

물론 이 숫자 또한 90억이 넘는 숫자이므로 0부터 9876543210까지 차례대로(선형적으로) 감소하는 숫자인지 판단하려면 엄청난 연산 횟수가 나올 수밖에 없다.

하지만 이 숫자들을 자릿수를 기준으로 비교한다면 얘기가 달라진다.

즉, 1자리 수부터 10자리 수까지 앞자리보다 작은 숫자들만 이어 붙여준다면 불필요한 연산을 획기적으로 줄일 수 있다.

이 과정에서 백 트래킹을 재귀로 구현하며 무한 루프에 빠지지 않도록 탈출 조건을 잊지 않도록 한다.

아이디어만 떠올린다면 구현 자체는 어렵지 않은 문제이므로 전체 코드를 보면서 설명하겠다.

def add_digit(digit,num):    #자리수에 따라 증가
    if digit==1:
        decreasing.append(num)
    else:
        for i in range(num%10):
            add_digit(digit-1,num*10+i)

def backtracking(digit):    #백트래킹 시작
    for i in range(digit-1,10):
        add_digit(digit,i)
    
decreasing=[]        #감소하는 숫자 리스트
for i in range(1,11):
    backtracking(i)

n=int(input())
if n>=len(decreasing):        #감소하는 숫자가 없을 때
    print(-1)
else:
    print(decreasing[n])

크게 구성을 함수 두 개, 메인으로 나누었다.

물론 메인에서 중첩 for문을 통해 1자리 수부터 10자리 수까지 가능한 숫자들을 매개변수로 보낸다면 하나의 함수만 써도 되지만 직관적인 이해를 돕기 위해 기능을 분리하여 함수 두 개로 구현하였다.

첫 번째 함수 add_digit은 특정 자릿수까지 감소하는 숫자를 이어 붙이는 함수고 두 번째 함수 backtracking은 1 자릿수부터 10 자릿수까지 백 트래킹을 반복하는 함수다.

함수의 특성상 먼저 선언되어있어야 호출 가능하므로 조금 복잡하지만 함수의 흐름대로 설명하겠다.

먼저 12번째 줄에 decreasing으로 감소하는 숫자들을 넣을 리스트를 선언했다.

그리고 13번째 줄은 자릿수를 매개변수로 백 트래킹을 시작하기 위한 반복문이고 이해가 쉽도록 1부터 10까지 반복한다.

즉 1 자릿수부터 10자리 수까지 찾겠다는 의미이다.

그럼 8번째 줄인 backtracking 함수로 넘어가는데 이미 받은 digit변수와 같이 0부터 9까지 숫자를 파라미터로 넘긴다.

이 0부터 9는 실제 감소하는 수가 될 숫자들이다.

그렇게 add_digit으로 넘어가면 digit이 1자리일 때는 더 이상 추가할 숫자가 없으므로 decreasing 리스트에 숫자를 넣고 함수가 자동 종료된다.

만약 digit이 2 이상일 땐 뒷자리에 숫자를 추가해야 하므로 반복문을 통해 digit을 감소시킨 후 재귀 호출한다.

이때 추가해야 할 숫자가 바로 앞자리 숫자보다 작아야 하므로 num%10을 통해 바로 앞자리 숫자를 구하고 해당 숫자 미만까지만 반복문을 돌린다.

물론 2자리 수 이상부터는 첫자리에 0이 올 수 없지만 num%10은 0이라 for문을 수행하지 않아서 고려하지 않아도 된다.

또한 뒷자리에 숫자를 이어 붙이므로 원래 숫자인 num에 10을 곱해서 자릿수를 늘린 후 i를 더하면 원하는 숫자가 된다.

위의 재귀가 끝나면 decreasing 리스트에는 0부터 9876543210까지 감소하는 수가 들어가게 되고 N을 입력받아서 리스트의 인덱스를 벗어나면 불가능한 수이므로 -1을 출력, 벗어나지 않으면 해당 인덱스의 숫자를 출력하면 통과한다.

아무래도 이 문제가 골드로 측정된 것은 숫자를 자릿수로 비교하는 생각의 전환, 백 트래킹 적용 때문인 것 같다.

비교적 코드도 짧고 구현도 쉬운 편이기 때문이다.

아마 다양한 문제를 접하다 보면 이 정도 아이디어와 구현은 쉽게 떠올리고 구현할 수 있을 것이다.

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

문제 풀이

대문자 하나에 대응하는 소문자 문자열이 정해져 있으므로 Python의 딕셔너리를 사용하면 쉽게 해결할 수 있다.

대응하는 문자들을 딕셔너리에 저장하고 압축된 문자열이 들어왔을 때 차례대로 소문자 문자열로 치환하면 쉽게 풀 수 있는 문제다.

바로 전체 코드로 넘어가겠다.

n=int(input())
word={}
res=""
for i in range(n):
    temp=list(input().split())
    word[temp[1]]=temp[0]
question=input()

for i in question:
    res+=word[i]
num=list(map(int,input().split()))
print(res[num[0]-1:num[1]])

2번째 word는 딕셔너리를 선언했고 for문을 돌면서 입력받은 값을 저장하면 된다.

이때 주의해야 할 점은 압축된 문자열을 풀어야 하므로 입력받은 대문자를 딕셔너리의 키, 소문자 문자열 패턴을 딕셔너리의 값으로 저장해야 한다는 것이다.

res에 치환한 문자열을 저장하고 입력받은 인덱스를 기준으로 출력하면 쉽게 풀 수 있다.

인덱스로 범위 출력 시 왼쪽 인덱스는 포함, 오른쪽 인덱스는 미만까지 출력하는 점을 주의해야 한다.

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

전형적으로 이진 탐색을 사용하는 문제이다.

혹시 이진 탐색을 처음 접하거나 익숙하지 않다면 관련 포스팅을 보고 이해한 뒤 문제를 푸는게 좋을 것 같다.

2021.12.02 - [알고리즘/알고리즘 강의] - (알고리즘) 이진탐색 / 이분탐색 (Binary Search)

문제 풀이

문제에서 전체 게임 횟수 : X, 이긴 게임 횟수 : Y, 승률 : Z이다.

주의해야 할 조건은 3가지다.

1. 승률을 뜻하는 Z는 소수점을 버린다.(반올림이 아니다)
2. Z가 절대 변하지 않으면 -1을 출력한다.
3. X는 최대 1,000,000,000 (10억)까지 가능하다.

Z에 대한 식을 나타내 보면 Z=(Y*100)/X이고 a만큼 수행했을 때 Z+1=((Y+a)*100)/(X+a)가 성립하는 최소 a를 구하는 문제이다. (승률 = 이긴 횟수/전체 횟수)

참고로 Python의 계산 방식 때문인지 처음에 Z=(Y//X)*100로 작성했더니 틀렸었다.

꼭 Z=(Y*100)//X로 작성해야하고 이 부분에 대해서 정확히 아시는 분이 계시다면 피드백 해주시면 감사합니다!!

이때 Z가 99 이상이라면 승률은 절대 변하지 않으므로 -1을 출력하고 98일 때 생각하면 X번만큼 추가할 때 99로 변하기 때문에 최대 X번까지만 반복하면 된다는 것을 알 수 있다.

이때 X는 최대 10억까지 가능하므로 순차적으로 탐색하는 O(n)의 시간 복잡도를 적용한다면 반드시 시간 초과가 날 수밖에 없다.

즉 1부터 X까지 오름차순인 상태에서 탐색 가능한 이분 탐색(이진 탐색)을 적용하면 풀 수 있을 것이다.

다음은 전체 코드다.

x,y=map(int,input().split()) 
z=(100*y)//x 
left=0 
right=x 
res=x 
if z>=99: 
    print(-1)
else: 
    while left<=right: 
        mid=(left+right)//2 
        if (100*(y+mid))//(x+mid)>z: 
            res=mid 
            right=mid-1 
        else: 
            left=mid+1
    print(res)

res는 정답인 최소 게임 수를 의미하는 변수로 최대 X번을 저장해놓고 더 작은 수가 있으면 갱신하는 방식으로 구현하였다.

승률이 99 이상이면 바로 -1을 출력하고 98 이하라면 이진 탐색을 실행한다.

초기 left는 0, right는 X로 설정하고 left와 right가 역전되지 않을 때까지 반복한다.

이때 left와 right 중간값을 기준으로 승률(Z)이 변하면 res를 갱신한 뒤 right는 중간값-1로, 변하지 않으면 left를 중간값+1로 변경함으로써 탐색해야 되는 범위를 절반씩 줄여준다.

즉 탐색 범위가 N이라면 범위를 절반씩 줄이므로 O(logn)의 시간 복잡도를 갖고, 10억의 Input이 들어와도 충분히 연산 가능해진다.

※조건을 잘 보고 Input의 크기에 따라 적절한 알고리즘을 적용하는 것이 중요한 것 같다.※

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

문제 풀이

눈여겨봐야 할 점은 3가지다.

1. 버스 노선의 개수인 N은 20만 이하이다.
2. 한 점 이상에서 겹쳐지면 연장 가능한 노선이다.
3. 개편된 노선의 요금은 개편할 때 사용된 노선의 최소 요금을 적용한다.

문제와 그림을 보고 바로 떠오른 생각은 노선의 정보를 오름차순으로 정렬한 뒤 개편된 노선과 겹친다면 포함하는 노선, 겹치는 부분이 없다면 새로운 개편된 노선으로 판단하는 방식이다.

이 방식대로 연산하면 Sort를 이용하여 정렬할 때 O(nlogn), 오름차순 된 노선 정보를 처음부터 훑을 때 O(n)으로 총 O(nlogn)의 시간 복잡도가 걸린다고 생각했다.

따라서 소스 코드는 다음과 같다.

n=int(input())
bus=[]
res=[]
for i in range(n):
    bus.append(list(map(int,input().split())))
bus.sort(key=lambda x:(x[0],x[1]))
check=True
for i in bus:
    if check:
        res.append(i)
        check=False
    else:
        if i[0]<=res[len(res)-1][1]:
            if i[1]>res[len(res)-1][1]:
                res[len(res)-1][1]=i[1]
            if res[len(res)-1][2]>i[2]:
                res[len(res)-1][2]=i[2]
        else:
            res.append(i)
print(len(res))
for i in res:
    print(i[0],i[1],i[2])

bus는 기존 노선 정보를 저장하고 res는 개편된 노선 정보를 저장할 리스트이다.

6번째 줄에서 lambda를 키로 이용하여 0번째 원소, 1번째 원소를 기준으로 오름차순 정렬한다는 뜻이다.

check 변수를 통해 첫 노선을 개편된 노선으로 잡았고 겹치는 부분이 있을 경우로 나눠 14번째 if문은 현재 노선 정보가 개편된 노선보다 길어서 연장해야 될 때, 16번째 if문은 최소 요금으로 갱신하는 문장이다.

또한 겹치는 부분이 없으면 기존 노선을 개편된 노선으로 추가한다.

한 줄씩 원리를 따라가 보면 쉽게 이해할 수 있을 것이다.

Python으로 제출하면 시간 초과가 뜨길래 PyPy로 제출했더니 통과했다.

PyPy는 한 줄씩 해석하는 인터프리터 방식인 Python의 느린 동작에서 컴파일 방식을 개선하여 나온 언어로 상당히 빠른 수행 속도가 특징이다.

따라서 동일한 문법이기에 애초에 시간 복잡도를 비효율적으로 작성한 경우가 아니라면 Python으론 시간 초과 뜨는 코드가 PyPy로 통과하는 경우가 많다.

즉 올바르게 작성한 것 같은데 시간 초과가 뜬다면 PyPy로 제출하길 추천한다.

https://www.acmicpc.net/contest/problem/725/1

문제 풀이

눈여겨봐야 할 조건은 3가지다.

1. 보이는 대로 읽어야 할 알파벳과 다르게 읽어야 할 알파벳이 구분되어있다.
2. 최대 100글자의 단어가 주어진다.
3. 영어 소문자로 나타내 출력해야 한다.

다르게 읽어야 할 알파벳은 다음과 같다.

B->v, E->ye, H->n, P->r, C->s, Y->u, X->h

해당 부분은 파이썬의 딕셔너리(Dictionary)를 사용하면 쉽게 치환 가능하다.

최대 100글자이므로 시간 복잡도는 고려할 필요가 없을 정도로 Input Size가 작다.

입력이 대문자로 들어오고 출력은 소문자로 해야 하므로 보이는 대로 읽어야 할 알파벳은 소문자로 치환시켜야 된다.

다음은 전체 코드이다.

word=input()
russ={"B":"v","E":"ye","H":"n","P":"r","C":"s","Y":"u","X":"h"}
res=""
for i in word:
    if i in russ:
        res+=russ[i]
    else:
        res+=i.lower()
print(res)

먼저 russ란 딕셔너리에 치환해야 될 알파벳들을 넣어 놓고 Input 문자열을 하나씩 반복한다.

만약 딕셔너리에 있는 문자라면 해당 값을 res에 이어 붙이고 없는 문자라면 lower() 함수를 이용하여 대문자를 소문자로 치환한 다음 이어 붙인다.

완성된 문자열을 출력하면 정답이다.

파이썬의 딕셔너리를 사용해야겠다는 생각만 떠올리면 복잡한 인덱싱 과정도 필요 없기에 쉽게 풀 수 있는 문제였다.