1138 한 줄로 서기

어 어케하지..? 고민을 했는데 일단 N이 10이다. 모든 경우의 수를 계산하더라도 문제가 없다는 뜻이지. 걍 마 다 돌려봐도 되겠다 싶었다. 

 

1. 모든 키 순서를 다 만들어본다 - 1번이 가장 큰 경우, 3번이 가장 큰 경우...

2. 해당 키 순서가 입력이랑 맞는지 확인해본다. 

 

-> 아 그런데 키 순서랑 어떻게 서있는지는 관련 없었다..

 

결국 머리 아파서 다른 사람의 풀이를 봤다. 

아래 순서로 구현하는 것 같다. 

 

1. 그냥 자신보다 키가 큰 사람 수만 확인하면 된다

2. 키가 큰 사람 수만큼 지난 위치에 배치한다. 

3. 만약 그 자리에 누가 있다면 좀 더 뒤로 넘어가서 빈자리에 배치한다. 

 

https://lovelyunsh.tistory.com/118

[백준] 1138 한 줄로 서기

 

이 분 글을 참고했는데 여기서 3번을 넣는 경우가 이해가 안 된다. 1, 2가 클 수 있는 거 아닌가...? 

 

일단 막혀서 그대로 둠 -> 아 이게 키가 1인 사람부터 정보가 주어진다. 나는 1 ~ n까지 중복이 없다는 뜻으로 이해했는데 아니었구나. 

 

시도1

아래처럼 풀었는데 틀렸다. 

이유 찾으려고 고민고민을 했는데 못 찾았다. 

 

도움 받아서 예외 케이스를 찾았다. 왜 다른 사람이 보면 문제가 잘 보이지? (머리 박박 때리는 중)

4 1 2 1 0 이거 답이 4 1 3 2가 나와야 하는데 내 코드에서는 4 1 2 3으로 나온다.

아... 맞다... 2라면 키 큰 자리 두 칸을 지나야 하는데 이건 그냥 빈 자리가 나올때까지 찾는다. 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int main() {
    int n;
    scanf("%d", &n);
    
    // 자리가 찾는지 기록하는 벡터
    vector<int> v(n + 1); 
    for (int i = 0; i < n; i++) {
        int in;
        scanf("%d", &in);
        
        while (in < n) {
            if (v[in] == 0) {
                v[in] = i + 1;
                break;
            }
            in++;
        }
    }
    
    for (int i = 0; i < n; i++) 
        printf("%d ", v[i]);
    
    return 0;
}

 

시도2

입력을 받으면 그 만큼 빈자리를 확인하는 부분을 추가했다. 통과! 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int main() {
    int n;
    scanf("%d", &n);
    
    // 자리가 찾는지 기록하는 벡터
    vector<int> v(n + 1); 
    for (int i = 0; i < n; i++) {
        int in;
        scanf("%d", &in);
        
        int bigger = 0;
        for (int j = 0; j < n; j++) {
            if (v[j] == 0)
                bigger++;
            
            if (bigger == in) {
                in = j + 1;
                break;
            }
        }
        
        while (in < n) {
            if (v[in] == 0) {
                v[in] = i + 1;
                break;
            }
            in++;
        }
    }
    
    for (int i = 0; i < n; i++) 
        printf("%d ", v[i]);
    
    return 0;
}