HelloMinchan
처음처럼
HelloMinchan
LinkedIn
전체 방문자
오늘
어제
  • 분류 전체보기 (306)
    • Backend (4)
      • NestJS (1)
      • Express (1)
      • Spring (2)
    • Infrastructure (1)
      • AWS (1)
    • Frontend (1)
      • Next.js (1)
    • Language & Runtime (4)
      • Java (2)
      • Node.js (2)
    • Computer Science (8)
      • Computer Networks (3)
      • Operating Systems (4)
      • OOP (1)
    • 독서 (4)
      • 데이터 중심 애플리케이션 설계 (3)
      • 객체지향의 사실과 오해 (1)
    • 회고 (4)
      • Project (2)
      • Career (2)
    • Deprecated (280)

채널

  • GitHub
  • LinkedIn

최근 글

태그

  • 개발자
  • front-end
  • 프로그래머스
  • 백준
  • 데이터베이스
  • 백준Go
  • 프로그래머스Python
  • 알고스팟Python
  • programmers
  • back-end
  • Database
  • Algospot
  • 백엔드
  • 백준C++
  • 프로그래밍
  • 프로그래머스C++
  • 백준Python
  • 알고스팟
  • Baekjoon Online Judge
  • 코딩

최근 댓글

인기 글

hELLO
HelloMinchan
Deprecated

[Baekjoon Online Judge] 백준 11003번 탑(Python)

[Baekjoon Online Judge] 백준 11003번 탑(Python)
Deprecated

[Baekjoon Online Judge] 백준 11003번 탑(Python)

2020. 5. 13. 18:09

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 11003번 탑

(Python)

(글쓴날 : 2020.05.13)

 


* Baekjoon Online Judge, 백준 11003번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.


 

 

백준 11003번 탑


1) 문제

문제 링크 : https://www.acmicpc.net/problem/2493

 

2493번: 탑

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

www.acmicpc.net


2) 풀이 과정

* 시간 복잡도 : O(n)

 

높이가 각기 다른 N개의 탑들이 주어지고 오른쪽 탑부터 왼쪽으로 레이저를 발사할 때, 레이저 수신이 가능한 자신보다 높은 탑의 번호를 구하는 문제입니다.

단, 자신보다 높은 탑이 없을 경우 0을 출력합니다.

 

저의 경우, 스택을 이용했으며, Python을 사용했습니다.

N의 최댓값이 500,000이므로 완전 탐색으로 풀 시 시간 초과가 나게 됩니다.

이에 따라 정렬, 이분 탐색 등 여러 방면으로 풀어보려고 노력했으나 결국 찾지 못했고, 질문 검색을 찾아본 결과 스택으로 푼다는 것을 확인했습니다.

탑들을 차례대로 탐색하여 스택이 비었을 경우 탑의 번호와 높이를 튜플 형태로 스택에 저장하고 스택에 탑이 있을 경우 탐색 중인 탑과 비교하여 만약 크다면 스택 안에 있는 탑의 번호를 출력 후 현재 탑을 스택에 저장하고, 만약 작다면 스택에서 탑들을 계속 꺼내어 비교하는 식으로 문제를 해결했습니다.

왼쪽에서 오른쪽으로 탐색하며 탐색된 탑보다 왼쪽에 작은 탑이 있을 시 탐색 대상에서 제외된다는 원리는 알았지만 어떻게 구현해야 할지를 몰랐는데, 스택을 사용하여 구현할 수 있다는 것을 떠올리지 못한 것이 아쉬웠던 문제였습니다.


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
input = sys.stdin.readline
 
N = int(input())
tower = list(map(int, input().split()))
stack = []
 
for i in range(N):
    while(True):
        if not len(stack):
            print(0, end=" ")
            stack.append((i + 1, tower[i]))
            break
        if stack[-1][1] > tower[i]:
            print(stack[-1][0], end=" ")
            stack.append((i + 1, tower[i]))
            break
        stack.pop()

 

저작자표시 비영리 변경금지 (새창열림)

'Deprecated' 카테고리의 다른 글

[Baekjoon Online Judge] 백준 11003번 최솟값 찾기(Python)  (0) 2020.05.15
[Baekjoon Online Judge] 백준 6198번 옥상 정원 꾸미기(Python)  (0) 2020.05.13
[Algorithm] 투 포인터  (0) 2020.05.13
[Baekjoon Online Judge] 백준 2003번 수들의 합 2(Python)  (0) 2020.05.13
[Baekjoon Online Judge] 백준 16287번 Parcel(Python)  (0) 2020.05.13
  • [Baekjoon Online Judge] 백준 11003번 탑
  • (Python)
  • 백준 11003번 탑
'Deprecated' 카테고리의 다른 글
  • [Baekjoon Online Judge] 백준 11003번 최솟값 찾기(Python)
  • [Baekjoon Online Judge] 백준 6198번 옥상 정원 꾸미기(Python)
  • [Algorithm] 투 포인터
  • [Baekjoon Online Judge] 백준 2003번 수들의 합 2(Python)
HelloMinchan
HelloMinchan
Though you should not fear failure, You should do your very best to avoid it.

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.