div><\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/33756\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"div>\" \/>\n<meta property=\"og:description\" content=\"Problem Description There are N students, each having an integer height (the height can range from 1 to 200). We want to line up these students in ascending order based on their heights. Given the students’ heights, the problem is to determine the minimum number of swaps needed to arrange the students in order. A … \ub354 \ubcf4\uae30 "div>\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33756\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:20:00+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:46:49+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33756\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33756\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"div>\",\"datePublished\":\"2024-11-01T09:20:00+00:00\",\"dateModified\":\"2024-11-01T11:46:49+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33756\/\"},\"wordCount\":1,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Python Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33756\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33756\/\",\"name\":\"div>\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:20:00+00:00\",\"dateModified\":\"2024-11-01T11:46:49+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33756\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33756\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33756\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"div>\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n","yoast_head_json":{"title":"div>","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/33756\/","og_locale":"ko_KR","og_type":"article","og_title":"div>","og_description":"Problem Description There are N students, each having an integer height (the height can range from 1 to 200). We want to line up these students in ascending order based on their heights. Given the students’ heights, the problem is to determine the minimum number of swaps needed to arrange the students in order. A … \ub354 \ubcf4\uae30 \"div>","og_url":"https:\/\/atmokpo.com\/w\/33756\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:20:00+00:00","article_modified_time":"2024-11-01T11:46:49+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33756\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33756\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"div>","datePublished":"2024-11-01T09:20:00+00:00","dateModified":"2024-11-01T11:46:49+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33756\/"},"wordCount":1,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Python Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33756\/","url":"https:\/\/atmokpo.com\/w\/33756\/","name":"div>","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:20:00+00:00","dateModified":"2024-11-01T11:46:49+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33756\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33756\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33756\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"div>"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33756","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=33756"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33756\/revisions"}],"predecessor-version":[{"id":33757,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33756\/revisions\/33757"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33756"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33756"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33756"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

{"id":33756,"date":"2024-11-01T09:20:00","date_gmt":"2024-11-01T09:20:00","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33756"},"modified":"2024-11-01T11:46:49","modified_gmt":"2024-11-01T11:46:49","slug":"div","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33756\/","title":{"rendered":"div> <\/div"},"content":{"rendered":"

<\/p>\n

Problem Description<\/h2>\n
\n There are N students, each having an integer height (the height can range from 1 to 200).
\n We want to line up these students in ascending order based on their heights.
\n Given the students’ heights, the problem is to determine the minimum number of swaps needed to arrange the students in order.
\n A swap refers to exchanging the positions of two students.\n <\/p>\n

Input Format<\/h3>\n

The first line contains the number of students N. (1 \u2264 N \u2264 200)<\/li>\n

The next line contains the students’ heights separated by spaces.<\/li>\n<\/ul>\n

Output Format<\/h3>\n
Print the minimum number of swaps.<\/p>\n

Example<\/h2>\n

Input<\/h3>\n

\n5\n5 3 1 4 2\n    <\/pre>\nOutput<\/h3>\n\n4\n    <\/pre>\nSolution<\/h2>\n\n        To solve this problem, we can sort the given array and calculate the number of swaps needed.
\n        The basic idea is to compare the number at the current position with its position in the sorted array to perform the swaps.
\n        By utilizing cycles in this process, we can compute the minimum number of swaps required.\n    <\/p>\n
Approach<\/h3>\n\n        1. Sort the students’ heights to find the ideal order.
\n        2. Compare the current array with the sorted array to identify each height’s current index and target index.
\n        3. Traverse each element and check if it has been visited. For unvisited elements, explore the cycle to calculate
\n        its size. If the size of each cycle is k, then the number of swaps needed is (k – 1).
\n        4. Repeat this process for all elements to calculate the final number of swaps.\n    <\/p>\n
Code Implementation<\/h3>\n\ndef min_swaps(arr):\n    n = len(arr)\n    # Create a sorted array and combine it with index information.\n    sorted_arr = sorted(enumerate(arr), key=lambda x: x[1])\n    \n    # Initialize visited array and swap count.\n    visited = [False] * n\n    swap_count = 0\n    \n    for i in range(n):\n        # Skip already visited indices.\n        if visited[i] or sorted_arr[i][0] == i:\n            continue\n        \n        # Explore the cycle.\n        cycle_size = 0\n        j = i\n        \n        while not visited[j]:\n            visited[j] = True\n            j = sorted_arr[j][0]\n            cycle_size += 1\n            \n        if cycle_size > 0:\n            swap_count += (cycle_size - 1)\n    \n    return swap_count\n\n# Take input.\nN = int(input())\narr = list(map(int, input().split()))\n\n# Print the result.\nprint(min_swaps(arr))\n    <\/pre>\nExplanation<\/h2>\n\n        This algorithm has a time complexity of O(N log N) and calculates the number of swaps based on
\n        the size of cycles using the indices of the sorted array.
\n        Thus, it provides an efficient way to compute all swaps.\n    <\/p>\n
Time Complexity Analysis<\/h3>\n\n        – It takes O(N log N) time to sort the array.
\n        – In the worst case, visiting all elements once to calculate cycles takes O(N) time.
\nThus, the overall time complexity of the algorithm is O(N log N).<\/strong>\n<\/p>\n
Space Complexity Analysis<\/h3>\n\n        – O(N) space is needed for the sorted array, and the visited array also requires O(N) space.
\nThus, the overall space complexity is O(N).<\/strong>\n<\/p>\n
Conclusion<\/h2>\n\n        Through this problem, we learned a method to minimize swaps, which is more than just a simple sorting problem in algorithms.
\n        By utilizing sorting and the cycle approach, we can develop efficient solutions.
\n        It’s important to cultivate problem-solving skills through engineering thinking, so I encourage you to practice more with other examples.\n    <\/p>\n
References<\/h2>\n\nBaekjoon Algorithm Problem: ACM ICPC<\/a><\/li>\n
Data Structures and Algorithms<\/li>\n
Books related to Competitive Programming<\/li>\n<\/ul>\n<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Description There are N students, each having an integer height (the height can range from 1 to 200). We want to line up these students in ascending order based on their heights. Given the students’ heights, the problem is to determine the minimum number of swaps needed to arrange the students in order. A … \ub354 \ubcf4\uae30 “div>  <\/div\"<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[145],"tags":[],"class_list":["post-33756","post","type-post","status-publish","format-standard","hentry","category-python-coding-test"],"yoast_head":"\ndiv><\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/33756\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"div>\" \/>\n<meta property=\"og:description\" content=\"Problem Description There are N students, each having an integer height (the height can range from 1 to 200). We want to line up these students in ascending order based on their heights. Given the students’ heights, the problem is to determine the minimum number of swaps needed to arrange the students in order. A … \ub354 \ubcf4\uae30 "div>\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33756\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:20:00+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:46:49+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33756\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33756\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"div>\",\"datePublished\":\"2024-11-01T09:20:00+00:00\",\"dateModified\":\"2024-11-01T11:46:49+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33756\/\"},\"wordCount\":1,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Python Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33756\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33756\/\",\"name\":\"div>\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:20:00+00:00\",\"dateModified\":\"2024-11-01T11:46:49+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33756\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33756\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33756\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"div>\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"div>","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/33756\/","og_locale":"ko_KR","og_type":"article","og_title":"div>","og_description":"Problem Description There are N students, each having an integer height (the height can range from 1 to 200). We want to line up these students in ascending order based on their heights. Given the students’ heights, the problem is to determine the minimum number of swaps needed to arrange the students in order. A … \ub354 \ubcf4\uae30 \"div>","og_url":"https:\/\/atmokpo.com\/w\/33756\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:20:00+00:00","article_modified_time":"2024-11-01T11:46:49+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33756\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33756\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"div>","datePublished":"2024-11-01T09:20:00+00:00","dateModified":"2024-11-01T11:46:49+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33756\/"},"wordCount":1,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Python Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33756\/","url":"https:\/\/atmokpo.com\/w\/33756\/","name":"div>","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:20:00+00:00","dateModified":"2024-11-01T11:46:49+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33756\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33756\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33756\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"div>"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33756","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=33756"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33756\/revisions"}],"predecessor-version":[{"id":33757,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33756\/revisions\/33757"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33756"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33756"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33756"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

Output Format<\/h3>\n
Print the minimum number of swaps.<\/p>\n

Example<\/h2>\n

Explanation<\/h2>\n
\n This algorithm has a time complexity of O(N log N) and calculates the number of swaps based on
\n the size of cycles using the indices of the sorted array.
\n Thus, it provides an efficient way to compute all swaps.\n <\/p>\n

Time Complexity Analysis<\/h3>\n
\n – It takes O(N log N) time to sort the array.
\n – In the worst case, visiting all elements once to calculate cycles takes O(N) time.
\nThus, the overall time complexity of the algorithm is O(N log N).<\/strong>\n<\/p>\n

Output Format<\/h3>\nPrint the minimum number of swaps.<\/p>\n

Example<\/h2>\n

Explanation<\/h2>\n\n This algorithm has a time complexity of O(N log N) and calculates the number of swaps based on\n the size of cycles using the indices of the sorted array.\n Thus, it provides an efficient way to compute all swaps.\n <\/p>\n

Time Complexity Analysis<\/h3>\n\n – It takes O(N log N) time to sort the array.\n – In the worst case, visiting all elements once to calculate cycles takes O(N) time.\nThus, the overall time complexity of the algorithm is O(N log N).<\/strong>\n<\/p>\n

Output Format<\/h3>\n
Print the minimum number of swaps.<\/p>\n

Explanation<\/h2>\n
\n This algorithm has a time complexity of O(N log N) and calculates the number of swaps based on
\n the size of cycles using the indices of the sorted array.
\n Thus, it provides an efficient way to compute all swaps.\n <\/p>\n

Time Complexity Analysis<\/h3>\n
\n – It takes O(N log N) time to sort the array.
\n – In the worst case, visiting all elements once to calculate cycles takes O(N) time.
\nThus, the overall time complexity of the algorithm is O(N log N).<\/strong>\n<\/p>\n