[백준] 1138. 한 줄로 서기 풀이

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

 

처음 순서를 1, 2, 3, ... n 으로 정하고
앞의 숫자부터 해당 숫자의 앞에 그 숫자보다 더 큰 값이 몇개 있는지 확인하고
이 개수가 주어진 값(해당 숫자의 앞에 이 숫자보다 더 큰 숫자의 개수)보다 작으면
바로 뒤에 있는 숫자와 swap하면서 주어진 값이 될 때 까지 옮기는 과정을 반복한다.
문제에서 원하는 값의 순서가 될 때까지 반복...

 

---

C

더보기

#include <stdio.h>

void swap(int* a, int*b) {int t = *a; *a = *b; *b = t;}

int count(int v, int arr[], int order){
    int cnt = 0, i = 0;
    while(arr[i] != v){cnt += (arr[i] > v) ? 1 : 0; i++;}
    return (order == 0) ? cnt : i;
}

void adjust(int index, int l, int arr[]){
    int i = index + 1;
    while(l != 0){
        if(arr[i] > arr[index]) l--;
        swap(&arr[index++], &arr[i++]);
    }
}

int main(){
    int n; scanf("%d", &n);
    int v[n], res[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
        res[i] = i+1;
    }

    for(int i = 0; i < n*n; i++){
        int cnt = count((i % n) + 1, res, 0);
        int index = count((i % n) + 1, res, 1);
        if(cnt < v[i % n]) adjust(index, v[i % n] - cnt, res);
    }
    for(int i = 0; i < n; i++) printf("%d ", res[i]);
}

---

Python

더보기

def swap(a, b):
    global res
    t = res[a]; res[a] = res[b]; res[b] = t

def count(v, order):
    global res
    cnt = 0; i = 0
    while res[i] != v:
        cnt += 1 if res[i] > v else 0
        i += 1
    return cnt if order == 0 else i

def adjust(index, l):
    global res
    i = index + 1
    while l != 0:
        if res[i] > res[index]: l -= 1
        swap(index, i)
        i += 1; index += 1

n = int(input())
v = list(map(int, input().split())); res = list()
for i in range(n): res.append(i+1)

for i in range(n*n):
    cnt = count((i % n) + 1, 0)
    index = count((i % n) + 1, 1)
    if cnt < v[i % n]: adjust(index, v[i % n] - cnt)
for i in range(n): print("%d " % res[i], end='')