실전 문제 질문 하나만 드립니다 ㅠ

Question

강사님 안녕하세요, 제가 이번에 모 유니콘 기업에 코딩테스트를 보게 되었는데요. 1반과 2반을 키순대로 나열하는데, 키순이 안맞는 곳만 상대방 반의 같은 index 위치의 학생과 교환이 가능합니다. 최소한 몇번 교환을 해야 만족하는지 구하는게 전부입니다. 너무 간단해 보여서 저는 키순이 안맞는 위치를 체크한 후, 같은 index 위치의 다른 반 애를 데려왔을때, 키순이 앞뒤로 안맞는지 체크, 안맞으면 안바꿈 이런식으로만 했는데, 테스트 케이스 다 틀리네요 ㅠ 얘는 그냥 구현일가요? 아니면 어떤 알고리즘이 있는걸가요? 예제1) int[] height1 = {150, 170, 180, 180}; int[] height2 = {150, 160, 170, 190}; 답 : 횟수 1 (3번 인덱스 끼리만 교환)   예제2) int[] height1 = {130, 140}; int[] height2 = {130, 140}; 답 : 횟수 0

김태원 · Answer

안녕하세요^^ jangkeya님의 논리로는 반례가 많아 보입니다. 이 문제는 다이나믹으로 해결가능해 보입니다. 이 문제의 다이나믹 정의는 다음과 같습니다. dy[i][0] : i번 인덱스를 교환해서 0번부터 i번까지 두 배열이 정렬되는 최소 교환횟수 dy[i][1] : i번 인덱스를 교환하지 않고 0번부터 i번까지 두 배열이 정렬되는 최소 교환횟수 최종적으로 답은 dy[n-1][0]과 dy[n-1][1] 중 작은 값을 답으로 하면 될 것 같습니다. 한 번 도전해 보세요. 안되면 답글 다세요. 제가 한 번 시도해 볼께요.