[백준] 5883번 : 아이폰 9S (C++)

5883번 : 아이폰 9S

---

문제)

오늘은 애플의 아이폰 9S가 출시되는 날이다. N(1 ≤ N ≤ 1000)명의 사람들은 새 아이폰을 누구보다 먼저 구매하기 위해서 애플 스토어 앞에 한 줄로 서있다. 아이폰 9S는 구매자가 용량을 마음대로 정할 수 있다. 즉, 지금까지 아이폰은 16/32/64GB와 같이 용량의 크기가 미리 정해져 있었다. 하지만, 9S는 자신이 원하는 용량의 크기 B(i)를 점원에게 말하면, 정확하게 그 용량을 가진 아이폰 9S를 그 자리에서 만들어 구매하는 방식이다.

애플 스토어의 점원 상근이는 같은 용량을 원하는 사람들이 연속되어 있으면, 더 보기 좋을 것이라고 생각한다. 따라서, 특정 사람을 고르고, 그 사람이 원하는 용량을 원하는 사람을 줄에서 모두 빼버리려고 한다.

어떤 용량을 원하는 사람을 줄에서 빼 버리면, 같은 용량을 원하는 사람들이 연속되어 있는 구간의 길이중 가장 긴 값이 최대가 되는지 구하는 프로그램을 작성하시오.

 

 

입력 :

첫째 줄에 N이 주어진다. 둘째 줄부터 N개 줄에는 줄을 서 있는 순서대로 각 사람이 원하는 용량 B(i)가 주어진다. B(i)는 0보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. 항상 두 개 이상의 서로 다른 B(i)가 존재한다.

 

 

 

출력 :

상근이가 만들 수 있는 가장 길이가 긴 같은 용량을 원하는 사람의 연속 구간의 길이를 출력한다.

 

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n;
bool check[1000010];
vector<int> vec;
 
// 사람들이 원하는 용량이 0 ~ 1,000,000 이고,
// n의 최댓값이 1000이므로 
// 모든 경우의 수를 확인하더라도
// 1,000,000,000. 즉 10억이다.
// 따라서 이 문제는 일일이 모두 확인하더라도 시간초과가가 나지 않은다.
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
    int temp;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        vec.push_back(temp);
        check[temp] = 1;
    }
 
    
    int ans = 0;
 
    // 사람들이 요구했던 모든 용량 중 하나를 골라
    // 제외한 후 최대 길이를 측정한다.
    for (int i = 0; i < 1000001; i++)
    {    // 특정 용량을 원하는 사람을 제외한다.
        if (check[i])
        {
            int m = vec[0];
            int m_cnt = 0;
            for (int j = 0; j < n; j++)
            {
                if (vec[j] == i) continue;
                if (m == vec[j]) m_cnt++;
                else if (m != vec[j])
                {
                    m = vec[j];
                    m_cnt = 1;
                }
                else if (j == n - 1)
                {
                    m_cnt++;
                }
                ans = max(ans, m_cnt);
            }
        }
    }
 
    cout << ans;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/5883 

5883번: 아이폰 9S