태야

상황 - 오류 없는 빈 값 조회

현재 개인 사이드 프로젝트에서 Supabse를 사용해서 백엔드를 구성하고 있다. 사용자 프로필 정보를 담는 profiles 테이블을 만들었다. 이 propfiles 테이블의 데이터를 조회할 때, 본인꺼만 조회할 수 있도록 RLS 정책을 지정해 놓았다. 개발 중 웹훅 수신 로직에서 사용자 이메일 값을 기반으로 profile에서 사용자 id를 파싱 해야하는 상황이 생겼다. 이때 profiles에 접근해서 응답을 보니 항상 빈 배열 값이 나오는 문제가 생겼다.

원인 분석

• Supabse의 profiles 테이블에 RLS(행 수준 보안)가 적용되어 있다.
• RLS 정책이 "본인(로그인된 유저)만 자신의 profile을 select 할 수 있다."로 되어 있으면, 서버에서 웹훅(즉, 외부 시스템)이 호출할 때는 인증된 유저가 없으므로, 어떤 profile도 조회할 수 없다.

해결 방법

1. Service Role Key 사용

• Supabse의 Service Role Key(서버 전용 시크릿 키)를 사용하면, RLS를 무시하고 모든 데이터에 접근이 가능했다.
• 현재는 Service Role Key를 사용하지 않는 supabse 객체를 클라이언트, 서버단 2개로 나누어서 사용 중이다.
• 이 방식은 서버에서만 사용해야 하며, 클라이언트에서는 절대 노출하면 안 된다.

import { supabaseAdmin } from '@/lib/supabase-server'; // Service Role Key 사용

const { data: userProfile } = await supabaseAdmin
  .from('profiles')
  .select('id')
  .eq('email', attr.user_email)
  .single();

2. 웹훅 전용 RLS 정책 추가

• 만약 Service Role Key를 사용하지 않고, 일반 API Key로만 접근해야 한다면,
• 웹훅에서 오는 요청의 IP나 특정 헤더, 혹은 별도의 인증 토큰을 기반으로 RLS 정책을 완화할 수 있다.
• 하지만, Service Role Key를 사용하는 것이 더 쉽고 안전하다.

결론

• 웹훅 등 서버에서 RLS를 우회해야 할 때는 Service Role Key를 사용하는 supabase client로 쿼리하기(쉽게 말해, 관리자용 supabse client)
• 모든 곳에서 Service Role Key를 사용하는 supabase client로 하지말고, 필요한 부분에서만 사용하기

적용 예시

import { supabaseAdmin } from '@/lib/supabase-server'; // Service Role Key 사용

let userId = '';
if (attr.user_email) {
  const { data: userProfile } = await supabaseAdmin
    .from('profiles')
    .select('id')
    .eq('email', attr.user_email)
    .single();
  userId = userProfile?.id ?? '';
}

개념

CORS는 Cross-Origin Resource Sharing의 약자로, 서로 다른 출처 간의 리소스 요청을 제어하기 위한 보안 기능이다. 브라우저는 보안상의 이유로 스크립트가 다른 도메인에 있는 리소스에 접근하는 것을 기본적으로 차단한다. 이 기본적인 보안 제한을 ‘동일 출처 정책(Same-Origin Policy)’라고 한다.

CORS는 이러한 동일 출처 정책의 제한을 우회할 수 있도록 서버에서 명시적으로 설정해, 브라우저가 다른 도메인에서 리소스를 요청하는 것을 허용하게 만드는 방법이다.

• 출처(Origin): 도메인, 프로토콜, 포트를 포함한 것을 의미한다. 예를 들어, http://example.com:3000과https://example.com:3000은 서로 다른 출처다.
• 동일 출처 정책 (Same-Origin Policy): 웹 페이지가 자신과 다른 출처의 리소스를 로드하는 것을 제한하는 브라우저의 보안 정책이다.

원인

클라이언트가 웹 서버에 다른 출처의 리소스에 접근하려고 할 때 발생한다. 브라우저가 서버에 요청을 보내고, 서버가 올바른 CORS 헤더를 포함하지 않으면 브라우저에서 요청이 차단된다.

• 예를 들어, 웹 애플리케이션의 클라이언트가 http://localhost:3000에서 실행 중이고, http://api.example.com으로 API 요청을 보내려고 할 때, 출처가 다르기 때문에 브라우저는 보안 정책에 의해 요청을 차단할 수 있다.

동작 방식

CORS 동작 방식은 브라우저와 서버 간의 HTTP 요청 및 응답 헤더를 통해, 서로 다른 출처에서 리소스를 공유하는 과정을 제어하는 것이다.

1. Simple Request(단순 요청)

특정 조건을 만족할 때 preflight 요청을 보내지 않고 바로 요청이 이루어진다. 특정 조건은 아래와 같다.

• HTTP 메서드는 GET, POST, 또는 HEAD 여야 한다.
• Content-Type 헤더가 다음과 같은 POST 요청
  • application/x-www-form-urlencoded
  • multipart/form-data
  • text/plain
• 헤더는 브라우저가 자동으로 추가하는 안전한 헤더여야 하며, 여기에는 다음과 같은 제한이 있다.
  • Accept, Accept-Language, Content-Language, Content-Type (application/x-www-form-urlencoded, multipart/form-data, text/plain 중 하나).

단순 요청에서는 브라우저가 요청을 보낼 때 Origin 헤더를 추가한다. 서버는 응답 시 해당 요청을 허용할지 여부를 결정하고, 다음과 같은 CORS 관련 헤더를 응답에 포함한다.

• Access-Control-Allow-Origin: 요청을 허용할 출처를 지정( * 또는 특정 도메인).
• Access-Control-Expose-Headers (선택적): 클라이언트에서 접근 가능한 응답 헤더 목록을 지정.

브라우저는 서버의 응답에 Access-Control-Allow-Origin 헤더가 포함되어 있는지 확인하고, 클라이언트가 해당 출처의 리소스에 접근하는 것을 허용할지 결정한다.

2. Preflight Request(사전 요청)

브라우저가 보안 확인을 위해 실제 요청을 보내기 전에 서버에 미리 허락을 구하는 요청이다. 주로 민감한 요청에 대해 사용되며, 다음과 같은 경우에 발생한다.

• 요청 메서드가 GET, POST, HEAD가 아닌 다른 메서드인 경우 (PUT, DELETE, OPTIONS 등)
• 요청 헤더가 안전하지 않은 커스텀 헤더를 포함하는 경우 (예: Authorization, Content-Type이 JSON 등)
• 요청에 Credentials (쿠키, 인증 토큰 등)이 포함된 경우

프리플라이트 요청은 OPTIONS 메서드를 사용해 서버에 보내진다. 이 요청은 브라우저가 실제 요청을 보내도 안전한지 확인하기 위해 서버에게 허락을 구하는 과정이다. 프리플라이트 요청에서는 다음과 같은 헤더가 사용된다.

Request Header(브라우저 → 서버)

• Origin: 요청을 보낸 출처.
• Access-Control-Request-Method: 실제 요청에서 사용하려는 HTTP 메서드.
• Access-Control-Request-Headers (선택적): 실제 요청에서 사용될 추가 헤더 목록.

서버는 이러한 프리플라이트 요청에 대해 다음과 같은 응답을 보내야 한다.

Response Header(서버 → 브라우저)

• Access-Control-Allow-Origin: 허용된 출처(* 또는 특정 도메인)
• Access-Control-Allow-Methods: 클라이언트가 사용할 수 있는 HTTP 메서드 목록 (GET, POST, PUT 등).
• Access-Control-Allow-Headers: 허용된 헤더 목록 (예: Authorization, Content-Type).
• Access-Control-Max-Age (선택적): 클라이언트가 프리플라이트 응답을 캐시할 시간 (초 단위).
• Access-Control-Allow-Credentials: 클라이언트가 쿠키를 전송할 수 있도록 허용

서버가 프리플라이트 요청에 대해 성공적으로 응답하면, 브라우저는 실제 요청을 서버로 전송하게 된다!

CORS 요청 예시

브라우저가 CORS 요청을 보내고, 서버가 응답하는 예시다.

1. Simple Request 예시

• 클라이언트가 GET 요청을 보내는 경우
  • 여기서 브라우저는 응답에 포함된 Access-Control-Allow-Origin 헤더를 확인하여 클라이언트에서 이 데이터를 사용할 수 있게 한다.

// 요청(client -> Server)
GET /api/data HTTP/1.1
Host: api.example.com
Origin: http://localhost:3000

// 응답(Server -> Client)
HTTP/1.1 200 OK
Access-Control-Allow-Origin: http://localhost:3000
Content-Type: application/json

{
  "message": "CORS 요청 성공"
}

2. Preflight Request 예시

// Preflight 요청(client -> Server)
OPTIONS /api/data HTTP/1.1
Host: api.example.com
Origin: http://localhost:3000
Access-Control-Request-Method: DELETE
Access-Control-Request-Headers: Authorization

// Preflight 응답(Server -> Client)
HTTP/1.1 204 No Content
Access-Control-Allow-Origin: http://localhost:3000
Access-Control-Allow-Methods: GET, POST, PUT, DELETE
Access-Control-Allow-Headers: Authorization
Access-Control-Max-Age: 86400

• Access-Control-Allow-Origin: 해당 요청을 허용할 출처를 명시 (http://localhost:3000).
• Access-Control-Allow-Methods: 허용 가능한 메서드(GET, POST, PUT, DELETE).
• Access-Control-Allow-Headers: Authorization 헤더가 허용됨을 명시.
• Access-Control-Max-Age: 86400초 동안 프리플라이트 응답을 캐시함.

Preflight 요청에 대한 성공적인 응답을 받은 후, 클라이언트는 실제 요청을 보낸다.

// 실제 요청(client -> Server)
DELETE /api/data HTTP/1.1
Host: api.example.com
Origin: http://localhost:3000
Authorization: Bearer token123

// 실제 응답(Server -> Client)
HTTP/1.1 200 OK
Access-Control-Allow-Origin: http://localhost:3000
Content-Type: application/json

{
  "message": "리소스가 삭제되었습니다"
}

CORS 관련 주요 HTTP 헤더 요약

1. Access-Control-Allow-Origin: 허용할 출처를 지정 (은 모든 출처를 허용).
2. Access-Control-Allow-Methods: 클라이언트가 사용할 수 있는 HTTP 메서드를 지정.
3. Access-Control-Allow-Headers: 클라이언트가 사용할 수 있는 추가 헤더를 지정.
4. Access-Control-Allow-Credentials: 클라이언트가 쿠키나 인증 정보를 서버로 전송할 수 있도록 허용.
5. Access-Control-Max-Age: 프리플라이트 요청의 응답을 캐시할 수 있는 시간을 지정 (초 단위).
6. Access-Control-Expose-Headers: 클라이언트에서 접근 가능한 응답 헤더를 지정.

해결 방법

1.서버 측에서 CORS 설정

• 서버가 올바른 CORS 헤더를 포함하도록 설정하는 것이 가장 일반적인 해결 방법이다.
• 예를 들어, Node.js/Express 서버에서는 다음과 같이 설정할 수 있다.

const express = require('express');
const cors = require('cors');
const app = express();

app.use(cors()); // 모든 출처에 대해 CORS 허용
// 또는 특정 출처만 허용하고 싶다면:
// app.use(cors({ origin: 'http://localhost:3000' }));

app.get('/api/data', (req, res) => {
  res.json({ message: 'CORS 설정 성공' });
});

app.listen(5000, () => {
  console.log('Server is running on port 5000');
});

2.프록시 서버 사용

• 클라이언트와 서버 간에 프록시 서버를 두어 요청을 중계함으로써 동일 출처 정책을 회피하는 방법이다.
• 개발 환겨에서 주로 사용되며, 예를 들어 React에서는 package.json 에 proxy 설정을 추가해 사용할 수 있다.

{
  "proxy": "http://api.example.com"
}

3.브라우저 확장 프로그램 사용(개발 환경)

• Chrome 등 브라우저에서 제공하는 CORS 해제 확장 프로그램을 사용해 에러를 일시적으로 해결할 수 있다.
• 하지만, 이 방법은 개발 환경에서만 사용하는 것이 좋다. 보안상 이유로 운영 환경에서는 권장되지 않는다!

4.서버 설정 변경

• Apache 또는 Nginx 같은 웹 서버를 사용하는 경우, 서버 설정 파일에서 CORS 헤더를 추가해야 한다.
• Nginx의 경우

add_header 'Access-Control-Allow-Origin' '*';
add_header 'Access-Control-Allow-Methods' 'GET, POST, OPTIONS';

Access-Control-Allow-Credentials 사용 시 주의

• 클라이언트가 쿠키 또는 인증 정보를 서버로 보내기 위해서는 Access-Control-Allow-Credentials: true를 설정하고, Access-Control-Allow-Origin에 * 대신 특정 출처를 명시해야 한다.

정리

• CORS는 브라우저 보안 정책으로 인해 발생하는 문제로, 클라이언트가 다른 출처의 리소스에 접근하려고 할 때 발생한다.
• 서버에서 CORS 헤더를 적절히 설정함으로써 이를 해결할 수 있다.
• 프록시 서버 사용이나 브라우저 확장 프로그램 같은 해결책이 있지만, 이는 개발 환경에서 주로 사용되며, 운영 환경에서는 서버에서 CORS 정책을 설정하는 것이 가장 바람직한 방법이다.

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

import sys

input = sys.stdin.readline

N = int(input().rstrip())
for _ in range(N):
    M = int(input().rstrip())
    clothes = {}

    for _ in range(M):
        (item, cloth_type) = list(input().rstrip().split())
        clothes[cloth_type] = clothes.get(cloth_type, 0) + 1

    result = 1
    for count in clothes.values():
        result *= (count + 1) #해당 종류의 의상을 선택하지 않는 경우 포함

    print(result - 1) # 아무 옷도 안 입는 경우 제외

의상 타입별 고르지 않는 경우도 카운트하는게 중요하다.

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

1번째 풀이 - O(N^2)

import sys

input = sys.stdin.readline

S = input().rstrip()

for i in range(len(S)):
    if S[i] in result:
        result[S[i]] += 1
    else:
        result[S[i]] = 1

    if i == len(S) - 1:
        break

    current_string = S[i]

    for j in range(i + 1, len(S)):
        current_string = current_string + S[j]
        if current_string in result:
            result[current_string] += 1
        else:
            result[current_string] = 1

print(len(result))

시간복잡도 O(n^2)이 걸리는 풀이로 작성했다. 해당 코드를 python의 set 자료형을 활용하면 간단하게 작성할 수 있다. 

python set() 활용 풀이 - O(N^2)

import sys

input = sys.stdin.readline

S = input().rstrip()

result = set()

for i in range(len(S)):
    for j in range(i + 1, len(S) + 1):
        result.add(S[i:j])
print(len(result))

set(집합) 자료형은 집합의 중복을 제거하고 순서를 보장하지 않는 리터럴 객체를 생성한다.

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

1차 풀이

from collections import deque
import sys
input = sys.stdin.readline
[N, K] = list(map(int, input().strip().split()))

def get_answer():
    numbers = deque(range(1, N+1, 1))
    deleted_numbers = []

    i = -1
    count = 0
    while len(deleted_numbers) != N:
        i += 1

        if i >= N:
            i = 0

        if numbers[i] not in deleted_numbers:
            count += 1
            if count == K:
                count = 0
                deleted_numbers.append(numbers[i])
                continue
    return "<" + ", ".join(map(str, deleted_numbers)) + ">"

print(get_answer())

문제점

- 효율성 문제

• 삭제 여부 확인 방식:
  코드에서는 원래의 numbers 데크에서 값을 제거하지 않고, 별도의 deleted_numbers 리스트에 추가한 후, 매번 if numbers[i] not in deleted_numbers:로 삭제 여부를 확인한다. 이 방식은 리스트의 멤버십 검사가 O(n) 시간 복잡도를 가지므로, N이 5000과 같이 큰 경우 불필요하게 많은 연산을 수행하게 되어 성능 문제가 발생할 수 있다.
• 불필요한 자료구조 사용:
  데크(deque)를 선언해두었지만, 데크의 효율적인 회전(rotate) 기능이나 popleft() 등을 활용하지 않고 단순히 인덱스 접근 방식으로 사용하고 있습니다

개선된 코드

from collections import deque
import sys
input = sys.stdin.readline
[N, K] = list(map(int, input().strip().split()))

def get_answer():
    dq = deque(range(1, N+1, 1))
    result = []

    while dq:
        for _ in range(K - 1):
            dq.append(dq.popleft())
        result.append(dq.popleft())


    return "<" + ", ".join(map(str, result)) + ">"

print(get_answer())

개선 효과

- 매번 불필요한 인덱스 접근이나 멤버십 검사를 하지 않아 시간 복잡도를 O(N)으로 줄일 수 있다.

Python rotate 메서드 활용 코드

from collections import deque
import sys

input = sys.stdin.readline
N, K = map(int, input().split())
dq = deque(range(1, N + 1))
result = []

while dq:
    dq.rotate(-(K - 1))  # K-1번 왼쪽으로 회전
    result.append(dq.popleft())

print("<" + ", ".join(map(str, result)) + ">")

요세푸스 문제는 원형 구조를 활용해 특정 규칙에 따라 요소들을 제거하는 시뮬레이션 문제인데, 그 개념 자체는 원형 연결 리스트 (circular linked list)와 매우 유사하다.

주요 포인트

• 원형 연결 리스트:
  노드들이 원형으로 연결되어 있어 마지막 노드의 다음이 첫 번째 노드가 된다. 요세푸스 문제에서는 이 구조를 통해 K번째 원소를 계속해서 찾아 제거하는 과정을 구현한다.
• 시뮬레이션:
  문제의 해결 방법은 실제로 원형 연결 리스트를 사용해 구현할 수도 있고, Python의 deque 같은 자료구조를 이용해 원형 큐의 동작(회전 및 제거)을 시뮬레이션하는 방식으로도 구현할 수 있다.
  예를 들어, deque를 사용하면 rotate()나 popleft() 같은 메서드로 간단하게 원형 구조를 흉내낼 수 있다.
• 알고리즘 선택:
  요세푸스 문제는 원형 연결 리스트를 이용하는 시뮬레이션 문제로 접근할 수 있지만, 경우에 따라 수학적인 공식을 활용해 더 효율적으로 풀 수도 있다. 단, 일반적으로 K가 임의의 값일 때는 시뮬레이션 방법이 가장 직관적이다.

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

import sys

input = sys.stdin.readline
N = int(input().strip())
heights = list(int(input().strip()) for _ in range(N))

def get_answer():
    stack = [] #(높이, 동일 높이 연속 개수) 집합
    result = 0
    for h in heights:
        same_count = 1
        #현재 h보다 작은 사람들은 볼 수 없으므로 pop하고, 그들이 형성헀던 쌍의 수를 더함
        while stack and stack[-1][0] < h:
            result += stack[-1][1]
            stack.pop()

        # 같은 높이의 경우, 같은 높이 그룹의 사람들과는 모두 볼 수 있음
        if stack and stack[-1][0] == h:
            cnt = stack[-1][1]
            stack.pop()
            result += cnt # 같은 높이 사람들과의 쌍 추가

            # 만약 스택에 아직 사람이 남아 있다면, 그 다음 높이 같은 사람과도 볼 수 있음
            if stack:
                result += 1
            same_count = cnt + 1
        else:
            # 스택이 비어있지 않다면, 바로 앞 사람과는 항상 볼 수 있음
            if stack:
                result += 1
        stack.append((h, same_count))
    return result

print(get_answer())

이 알고리즘의 핵심은:

• 왼쪽부터 순회하면서 스택에 (높이, 동일 높이 연속 개수)를 저장한다.
• 현재 사람보다 작은 사람들은 pop하여 그동안 형성된 쌍을 결과에 더하고,
  동일한 높이의 사람들은 하나의 그룹으로 묶어 개수를 관리한다.
• 남아 있는 스택의 최상단이 있다면 그 사람과는 볼 수 있으므로 1을 더한다.

이 방식은 각 사람을 한 번씩만 처리하여 O(N) 시간 내에 해결할 수 있다.

배열이나 리스트에서 각 원소에 대해 오른쪽에 있는 원소들 중 자신보다 크거나 같은(또는 보통은 '큰' 경우가 많지만, 변형으로 '크거나 같은' 조건을 쓰기도 한다) 첫 번째 원소를 찾는 문제다.

예시 문제 설명

예를 들어, 배열 A가 주어졌을 때A = [3, 5, 2, 7, 5]각 원소에 대해 오른쪽으로 이동하며, 처음 만나는 자신보다 크거나 같은 원소를 찾습니다.

- 3의 오른쪽에는 5, 2, 7, 5가 있는데, 처음으로 3보다 크거나 같은 수는 5입니다.
- 5의 오른쪽에는 2, 7, 5가 있는데, 2는 작으므로 건너뛰고, 다음 7은 5보다 크므로 7이 됩니다.
- 2의 오른쪽에는 7, 5가 있으므로 7이 첫 번째 큰(또는 같은) 수입니다.
- 7의 오른쪽에는 5만 있으나 5는 7보다 작으므로, 7은 오른쪽에 조건을 만족하는 원소가 없는 것으로 처리합니다.
- 마지막 원소인 5는 오른쪽에 아무 원소도 없으므로 조건을 만족하는 원소가 없습니다.

보통 조건을 만족하는 원소가 없을 경우 -1 또는 0 등 특정 값을 반환합니다.

단순하게 이중 반복문을 사용하면, 각 원소마다 오른쪽의 모든 원소를 확인해야 하므로 시간복잡도가 O(n^2)가 된다. 하지만 스택(stack)을 이용하면, 한 번의 순회로 각 원소를 효율적으로 처리할 수 있다.

스택을 사용하는 이유

• 스택의 특징
  
  • 스택은 후입선출(LIFO) 구조다. 이 특성을 이용하면, 배열을 한 번 순회하면서 "아직 답을 찾지 못한 원소들의 인덱스"를 스택에 저장해 두고, 새로운 원소가 들어올 때마다 이전 원소들과 비교하여 조건(큰 혹은 큰/같은)을 만족하는지 빠르게 확인할 수 있다.
• 시간복잡도
  • 각 원소는 스택에 한 번 push되고, 조건이 맞으면 pop되므로 각 원소가 스택에 들어가고 나오는 과정이 한 번씩 이루어집니다. 따라서 전체 시간 복잡도는 O(n)이 됩니다.

알고리즘 동작 과정

1. 초기화:
   빈 스택을 준비하고, 결과를 저장할 배열을 초기화한다. 결과 배열은 각 원소의 "다음 큰(또는 같은) 수"의 인덱스나 값을 저장할 수 있다.
2. 배열 순회:
   배열의 인덱스를 0부터 n-1까지 순회한다.
   • 현재 원소와 비교:
     현재 원소(A[i])가 들어왔을 때, 스택의 최상단에 있는 인덱스(예: j)를 확인한다.
     • 만약 A[i]가 A[j]보다 크거나(또는 크거나 같은) 하면, A[i]는 A[j]의 조건(다음 큰 또는 같은 수)을 만족하는 원소가 된다.
       따라서 결과 배열의 j번째 위치에 A[i] 또는 인덱스 i를 저장하고, 스택에서 j를 pop한다.
     • 이 과정을 스택이 비거나, 스택의 최상단 원소가 현재 원소보다 크거나 같은 조건을 만족할 때까지 반복한다.
   • 현재 인덱스 push:
     그 후, 현재 인덱스 i를 스택에 push한다.
3. 후처리:
   배열 순회가 끝난 후에도 스택에 남아있는 인덱스들은 오른쪽에 조건을 만족하는 원소가 없는 경우다. 이 경우, 결과 배열에 -1 또는 0을 기록한다.

Python 코드 예시

def next_greater_or_equal(arr):
    n = len(arr)
    result = [-1] * n  # 조건을 만족하는 원소가 없으면 -1로 처리
    stack = []  # 인덱스를 저장하는 스택

    for i in range(n):
        # 현재 원소 arr[i]가 스택의 최상단 원소보다 크거나 같으면 조건을 만족
        while stack and arr[stack[-1]] <= arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
    
    return result

# 예시 실행
A = [3, 5, 2, 7, 5]
print(next_greater_or_equal(A))  # 출력 예: [5, 7, 7, -1, -1]

위 글을 요약하자면 다음과 같다.

• 문제: 각 원소에 대해 오른쪽에서 처음으로 자신보다 크거나 같은 원소를 찾는 문제.
• 단순 방법: 이중 반복문을 사용하면 O(n^2) 시간복잡도.
• 스택 사용: 스택을 이용하면 각 원소가 한 번씩만 처리되므로 O(n) 시간복잡도로 해결 가능.
• 핵심: 스택에 아직 답을 찾지 못한 원소의 인덱스를 저장하고, 새 원소가 들어올 때마다 조건에 맞는 이전 원소들을 처리.

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

이 문제는 "다음 큰(또는 같은) 수(Next Greater or Equal Element)" 문제다. 배열이나 리스트에서 각 원소에 대해 오른쪽에 있는 원소들 중 자신보다 크거나 같은(또는 보통은 '큰' 경우가 많지만, 변형으로 '크거나 같은' 조건을 쓰기도 한다) 첫 번째 원소를 찾는 문제이다.

1. 단순 탐색 풀이 - O(n^2)

from functools import reduce
import sys

input = sys.stdin.readline
N = int(input().strip())
heights = list(int(input().strip()) for _ in range(N))

def get_answer():
    results = []

    while heights:
        height = heights.pop(0)
        count = 0
        for i in range(len(heights)):
            if heights[i] < height:
                count += 1
            else:
                break
        results.append(count)
    print(reduce(lambda acc, value: acc + value, results))

2. 스택 이용 최적화 풀이 - O(n)

from functools import reduce
import sys

input = sys.stdin.readline
N = int(input().strip())
heights = list(int(input().strip()) for _ in range(N))

def get_answer():
    stack = []
    total_visible = 0

    for i in range(N - 1, -1, -1):
        # 현재 빌딩보다 낮은 빌딩들은 스택에서 제거
        while stack and heights[stack[-1]] < heights[i]:
            stack.pop()

        # 스택에 차단 빌딩이 있으면 그 위치까지 빌딩 수 계산
        if stack:
            visible = stack[-1] - i - 1
        else:
            # 오른쪽의 모든 빌딩이 보이는 경우
            visible = N - i - 1
        total_visible += visible

        # 현재 빌딩 인덱스를 추가
        stack.append(i)

    return total_visible

print(get_answer())

• 스택을 활용하면 오른쪽에서 왼쪽으로 한 번의 순회로 각 빌딩의 보이는 옥상 수를 구할 수 있어 전체 시간복잡도를 O(n)으로 최적화할 수 있다.
• 이 방법은 각 빌딩이 스택에 단 한 번 들어가고 한 번씩만 제거되므로 효율적이다.