백준 17608 막대기 문제

아주 쉬운 기초 배열 문제입니다. 코테 기본을 까먹어서 걷기부터 다시 재활 중이라 한 번 풀어본 문제에요.

 

 

그리디부터 푸니 너무 어려워서 브론즈부터 재활하기로 마음을 먹었습니다.

 

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

 

 

 

 

아이디어는 간단하죠. 여러 막대 있을 때 오른쪽에서 본 게 몇개냐? 를 세는 문제입니다.

 

오른쪽에서부터 왼쪽 서치하면서 최댓값 갱신되는 횟수를 세면 되겠죠? 거기에 마지막 꺼 + 1

# 백준 17608 막대기

n = int(input())
answer = []
for j in range(n):
    answer.append(input())

cnt = 1
max = answer[-1]
for i in range(n-2, -1, -1):
    if max < answer[i]:
        cnt += 1
        max = answer[i]

print(cnt)

 

 

이 당연한 로직이 근데 틀리는 겁니다.

 

진짜 감 다죽었구나... 싶었죠. 이 문제는 결국 input을 받을 때 list형이랑 int형의 일치를 시켜주지 않아 발생한 문제였습니다.

 

예를 들어 3 9 9 10 이란 입력을 넣으면 1이 나와야하는데 2가 나오더라고요. 이 문제는 int 형으로 바꿔주니 해결이 되었지만, 시간 초과를 고려해야하는 문제였습니다.

 

# 백준 17608 막대기
# 시간초과
n = int(input())
answer = []
for j in range(n):
    answer.append(int(input()))

cnt = 1
max = answer[-1]
for i in range(n-2, -1, -1):
    if max < answer[i]:
        cnt += 1
        max = answer[i]

print(cnt)

 

이 코드는 예상 결과는 맞게 나오는데, 시간 초과가 뜹니다. 입력이 10만 단위라 그런가봐요.

 

딱히 스택 같은 걸 사용해도 크게? 시간을 줄일 만한 방법이 생각이 나지 않아서, 아 입력이 10만 단위일때 뭐 추가해야하지 않았나? 하고 sys 찾아서 readline 넣어줬습니다. 프로그래머스 같은 곳은 필요 없는데 백준에서 입력 여러 개 받을 때는 이걸 안해주면 시간초과가 뜨는 경우가 많습니다.

 

# 백준 17608 막대기

import sys
def input():
    return sys.stdin.readline().rstrip()

n = int(input())
answer = []
for j in range(n):
    answer.append(int(input()))

cnt = 1
max = answer[-1]
for i in range(n-2, -1, -1):
    if max < answer[i]:
        cnt += 1
        max = answer[i]

print(cnt)

 

휴, 브론즈 2 문제 버겹게 풀이 성공!

 

입력이 여러 개로 받을 때는 sys.stdin.readline().rstrip() 을 꼭 써줍시다...