happyso
study with happyso
happyso
전체 방문자
오늘
어제
  • 분류 전체보기 (300)
    • GIT (3)
    • 컴퓨터 기본 개념 (29)
    • 알고리즘 (125)
      • 알고리즘 문제 (115)
      • 알고리즘 개념 (10)
    • Go (2)
    • 클라우드 (53)
      • DevOps (3)
      • Kubernetes(쿠버네티스) (33)
      • AWS (6)
      • CKA (8)
    • 리눅스(Linux) (18)
      • 컨테이너(Container) (8)
    • Front (22)
      • JavaScript (2)
      • React (20)
    • Python (21)
      • Python 웹 크롤링 (11)
      • Django (7)
      • MachineLearning (3)
    • 데이터베이스 (6)
      • MariaDB (2)
      • MongoDB (4)
    • C언어 (5)
    • Trouble Shooting (2)
    • 네트워크 (8)
      • CCNA (5)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Patch
  • apply
  • 18
  • kubernetes
  • 15
  • replace
  • edit

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
happyso

study with happyso

알고리즘/알고리즘 문제

[python] 프로그래머스 > 뒤에 있는 큰 수 찾기

2023. 5. 18. 08:36

문제

https://school.programmers.co.kr/learn/courses/30/lessons/154539

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

[나의풀이 1번째] - 시간초과 실패

from collections import deque

def solution(numbers):
    answer = []
    dqList = deque(numbers)
    for i in list(dqList):
        dqList.popleft()
        isExist = False
        for j in list(dqList):
            if j > i:
                answer.append(j)
                isExist = True
                break
        if not isExist:
            answer.append(-1)
    return answer

[나의풀이 2번째] - 시간초과 실패

def solution(numbers):
    answer = []
    for i in range(len(numbers)):
        isExist = False
        for j in numbers[i+1:]:
            if j > numbers[i]:
                answer.append(j)
                isExist = True
                break
        if not isExist:
            answer.append(-1)
    return answer
def solution(numbers):
    answer = len(numbers) * [-1]
    for i in range(len(numbers)):
        for j in numbers[i+1:]:
            if j > numbers[i]:
                answer[i] = j
                break
    return answer

문제 해석

  • 정확이 어떤 알고리즘의 문제인지 몰랐는데, 스택문제 라고 한다.
  • 자신보다 큰 수를 찾는 유형은 스택 유형인 경우가 많다고 한다.
  • 순서대로 삽입하고, 조건에 충족한 수 (자기보다 큰 수)가 들어올 경우 스택을 비우면 된다.

문제 풀이

  1. 스택에 순서대로 수를 삽입한다.
  2. 스택 끝 수보다 큰 수가 들어오면 해당 위치에 큰 수를 대입하고 해당 스택을 비운다.
  3. while 조건을 만족할 때 까지 순차적으로 스택을 비운다.
def solution(numbers):
    answer = [-1] * len(numbers)
    stack = []
    for i in range(len(numbers)):
        while stack and numbers[i] > numbers[stack[-1]]:
            answer[stack.pop()] = numbers[i]
        stack.append(i)
    return answer

 

저작자표시 비영리

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

[python] 프로그래머스 > H-index  (0) 2023.05.23
[python] 프로그래머스 > 이진변환반복하기  (0) 2023.05.18
[python] 백준 > 그리디 > 회의실 배정(1931)  (0) 2021.03.30
[python] 백준 > BFS > 토마토(7576)  (0) 2021.03.22
[python] 백준 > 그래프 > 바이러스(2606)  (0) 2021.03.19
    '알고리즘/알고리즘 문제' 카테고리의 다른 글
    • [python] 프로그래머스 > H-index
    • [python] 프로그래머스 > 이진변환반복하기
    • [python] 백준 > 그리디 > 회의실 배정(1931)
    • [python] 백준 > BFS > 토마토(7576)
    happyso
    happyso

    티스토리툴바