[Programmers] #181894 - 2의 영역 [Java][C++][Python]

문제 링크

---

1. 아이디어

값 2가 모두 들어가는 가장 짧은 연속 구간은 첫 2와 마지막 2 사이의 구간이다. 그 바깥은 2를 포함하지 않으므로 잘라내도 되고, 그 안쪽은 양 끝이 2라서 더 줄일 수 없다. 앞에서부터 훑어 첫 2의 위치를, 뒤에서부터 훑어 마지막 2의 위치를 찾은 뒤 두 위치를 양끝으로 하는 구간을 반환한다. 2가 하나도 없으면 [-1]을 반환한다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = arr의 길이)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int[] solution(int[] arr) {
        int n = arr.length;
        int s = 0, e = n - 1;

        while (s < n && arr[s] != 2) {
            s++;
        }
        if (s == n) return new int[]{-1};

        while (arr[e] != 2) {
            e--;
        }

        return Arrays.copyOfRange(arr, s, e + 1);
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> arr) {
    int n = arr.size();
    int s = 0, e = n - 1;

    while (s < n && arr[s] != 2) s++;
    if (s == n) return {-1};

    while (arr[e] != 2) e--;

    return vector<int>(arr.begin() + s, arr.begin() + e + 1);
}

def solution(arr):
    idx = [i for i, x in enumerate(arr) if x == 2]
    if not idx:
        return [-1]
    return arr[idx[0] : idx[-1] + 1]

---