[BOJ] 1138번 한 줄로 서기

뚜비·2022년 5월 8일
0

BOJ

목록 보기
10/11

한 줄로 서기 << 문제 클릭!



✅문제 설명

: N명의 사람들이 고정된 자리로 한 줄로 선다.
: 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지 만을 기억
: N명의 사람이 있고 사람들의 키는 1부터 N까지 모두 다르다.
: 줄을 어떻게 서야 하는지 출력하는 프로그래믈 작성하라


  • 입력
    : 첫째 줄은 사람의 수 N(10보다 작은 자연수)
    : 둘째 줄은 키가 1인 사람부터 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있는가
    : i번째 수는 0보다 크거나 같고 N-i보다 작거나 같다.
    : i는 0부터 시작

  • 출력
    : 줄을 선 순서대로


❗핵심원리

: 예제에서 1번이 2명 2번이 1명 3번이 1며 4번이 0명이라고 말했다
: 제일 먼저 가장 작은 1번은 따라서 0123 번째 자리 중 2번에 배치, 2번은 1번째, 3번은 3번째, 4번은 0번째 자리에 배치하게 된다.

✅ 그리디로 생각했을 때 최적의 상황은?
키가 작은 사람부터 최대한 왼쪽의 사람 수 만큼 앞자리를 선택하는 것!



💻코드

  • 11로 초기화 한 배열에 자기보다 큰 수가 몇 개 있는지 count하면서 자리를 찾는다.
  • count와 temp(자신의 왼쪽에 있는 큰 사람의 수)가 같을 때 빈자리면 -> 루프 break
  • count < temp일 때 11이라면 -> count와 인덱스 증가
#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int N;
	cin >> N;

	int arr[10];
	fill(arr,arr+10,11); // 11로 초기화

	for (int i = 1; i <= N; i++) {
		/*초기화*/
		int temp = 0;
		int count = 0; // 나보다 왼쪽에 있는 사람 세기
		int j = 0; // 인덱스 

		cin >> temp; // 숫자를 받기 

		while (true) {
			
			if (count == temp) { // count와 temp가 같을 때 
				if (arr[j] != 11) { // 빈 자리가 아니면 
					j++;
				}
				else { // 빈자리면 
					break;
				}
			}
			else { // count와 temp가 같지 않을 때 
				if (arr[j] == 11) { // 자기 보다 큰 애가 있을때 
					count++;// 큰 애 count 
					j++; // 인덱스 증가
				}
				else { // 자기보다 큰 애가 아니면 
					j++; //인덱스 증가 
				}

			}
		}

		arr[j] = i; // 할당 
		
	}

	for (int i = 0; i < N; i++) {
		cout << arr[i] << " ";
	}

}


다른 분들의 풀이 출처

#include <iostream>

using namespace std;

 

const int MAX = 10;

 

int N;

int line[MAX];

 

int main(void)
{
        cin >> N;

        //키 순서

        for (int i = 0; i < N; i++)
        {
                 int left;
                 cin >> left;

                 //줄을 순회하는데
                 for (int j = 0; j < N; j++)
                         //자신의 자리가 마련되어있고 키 큰 사람들을 다 지나쳤다면
                         if (left == 0 && line[j] == 0)
                         {
                                 line[j] = i + 1;
                                 break;
                         }
                         //키 큰 사람이 있는 곳을 지나친다
                         else if (line[j] == 0)

                                 left--;

        }

       

        for (int i = 0; i < N; i++)

                 cout << line[i] << " ";

        cout << "\n";

        return 0;

}
  • 이 분은 이중 for문을 이용했다. left의 수를 감소시키면서 left가 0이고 자리가 있을 때 할당해주는 방식이다.
profile
SW Engineer 꿈나무 / 자의식이 있는 컴퓨터

0개의 댓글

관련 채용 정보

Powered by GraphCDN, the GraphQL CDN