developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 삼성코테자바꿀팁
  • 백준파이썬풀이
  • 통계분석
  • SW역량테스트파이썬풀이
  • 삼성코테구현풀이
  • 시계열
  • c++디자인패턴
  • 카카오코테
  • 삼성코테파이썬
  • 삼성코테자바풀이
  • AR모형
  • 삼성코테자바준비
  • 삼성코테기출자바풀이
  • 삼성코테기출
  • MA모형
  • 삼성코테파이썬준비
  • 데이터분석
  • 카카오코테java풀이
  • 삼성코테구현문제추천
  • ARIMA모형
  • 삼성코테파이썬풀이
  • 삼성코테준비
  • c++ 빌더 패턴
  • Arima
  • 코테파이썬
  • 운영체제인터럽트
  • 통계학
  • BOJ파이썬풀이
  • SW역량테스트파이썬
  • 시계열분석

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 탑 2493번 (python)

2021. 9. 23. 13:14

❓ 문제 - 백준 탑 2493번 - python 풀이법

출처 

(https://www.acmicpc.net/problem/2493)

 

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1

www.acmicpc.net

 

 

📝 문제해결법

1. 이 문제의 핵심은 시간복잡도를 고려하는 것이다. N의 범위가 N은 1 이상 500,000 이하이므로 O(N)으로 풀어야 한다.

2. 스택을 사용하여 해결하는 것이 특징이다.

  • 스택에 맨 오른쪽 탑부터 시작하여 스택에 해당 탑의 길이와 탑의 인덱스를 넣어줌
  • for문을 통해 stack의 top보다 큰 탑이 나온다면 answer 리스트의 해당 top값의 인덱스의 값을  큰 탑의 인덱스 값으로 변경
  • 만약 stack에 아무 값이 없다면 break

 

 

** 풀이 참조

(https://kyoung-jnn.tistory.com/entry/%EB%B0%B1%EC%A4%802493%EB%B2%88%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%ED%83%91-%EA%B7%B8%EB%A6%AC%EB%94%94-Greedy)

 

해당 블로그의 풀이법을 참조하여 공부하였습니다.

 

 

 

 

💻 소스코드

import sys

input = sys.stdin.readline
n = int(input())
data = list(map(int, input().split()))

stack = []
answer = [0] * n

for i in range(len(data)-1, -1, -1):
    if len(stack) == 0:
        stack.append([i, data[i]])
    else:
        while data[i] > stack[len(stack)-1][1]:
            top = stack.pop()
            answer[top[0]] = i+1
            if len(stack) == 0:
                break
        stack.append([i, data[i]])

for i in answer:
    print(i, end=' ')

 

 

🧐 Ellen's Thinking

이중 for문을 사용한다면 시간 복잡도는 O(N^2)이고, for문과 while문 stack을 잘 구현한다면 시간 복잡도를 O(N)으로 구현할 수 있다는 것을 깨달았다. 

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 연구소 14502번 (python)  (0) 2021.10.01
BOJ - 프린터 큐 1965번 (python)  (0) 2021.09.25
BOJ - 괄호 제거 2800번 (python)  (2) 2021.09.22
BOJ - 스택 수열 1874번 (python)  (0) 2021.09.06
BOJ - 상어 초등학교 21608번 (python)  (0) 2021.08.24
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 연구소 14502번 (python)
    • BOJ - 프린터 큐 1965번 (python)
    • BOJ - 괄호 제거 2800번 (python)
    • BOJ - 스택 수열 1874번 (python)
    developer-ellen
    developer-ellen

    티스토리툴바