[코딩테스트C++] 한 줄로 서기

오늘의 문제

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

한 줄로 서기

접근 법

• 입력이 10밖에 안되고 시간도 2초다. 아이디어만 발견하면 바로 풀 수 있는 문제다.
• 친절하게도 키 순서대로 키 더큰 사람수를 알려준다. 1번부터 배정을 하면 된다.
• 작은 사람부터 배정을 하면 풀 수 있는 이유는, 이 다음은 모두 지금 배정하는 사람보다 큰 사람일것이니까, 제일 작은사람이 말한 만큼의 idx에 배치하면 되는 것.
• 여기서 idx는 이미 배치되지 않은 공간에 대한 count이다.

나의 풀이

#include <iostream>
using namespace std;
int n;
const int MAX = 10;
int arr[MAX];
int res[MAX] = {0, };

// 행렬
void solution(){
    for(int i=0;i<n;i++){
        int idx = arr[i];
        int cnt = 0;
        for(int j=0;j<n;j++){
            if(res[j] == 0){
                if(cnt == idx){
                    res[j] = i+1;
                    break;
                }
                cnt++;
            }
        }
    }
}

다른 풀이

#include <cstdio>

int main(void) {
	int n;
	int temp;
	int line[10]{};
	size_t pos;

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		scanf("%d", &temp);

		pos = 0;
		while (line[pos])
			pos++;

		while (temp--)
			while (line[++pos]);
		
		line[pos] = i;
	}

	for (int i = 0; i < n; i++)
		printf("%d ", line[i]);

	return 0;
}

배울 점

• idx를 찾는것을 아주 간단하게 찾는다.