티스토리 뷰
반응형
solved.ac 난이도: 골드 3
17299번: 오등큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
이문제를 그냥 2중 반복으로 풀면 시간 초과가 무조건 뜬다.
import sys
input=sys.stdin.readline
a=int(input())
l=[0]*(10000001)
t=list(map(int,input().split()))
o=0
for i in range(a):l[t[i]]+=1
for i in range(a):
o=0
for g in range(i+1,a):
if l[t[g]]>l[t[i]]:print(t[g],end=" ");o+=1;break
if o==0:print(-1,end=" ")
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
어떻게 하면 고칠 수 있을까?
이문제는 해당 값의 개수보다 많은 개수를 가지고 있는 가장 왼쪽 값을 출력하는 것이다. 그러면 구간의 가장 큰 값과 위치를 저장해서 위치까지 반복을 해주면 된다. 이유는 만약 한 위치에 개수가 가장 큰 값이 있다면 그다음으로는 무조건 나오지 않기 때문에 반복을 그 위치에서 멈춰주면 된다.
이렇게 바꿔주고
import sys
input=sys.stdin.readline
a=int(input())
l=[0]*(10000001)
p=[0]*(a+1)
t=list(map(int,input().split()))
o=0
end=[a,0]
for i in range(a):
l[t[i]]+=1
for i in range(a-2,-1,-1):
o=0
for g in range(i+1,end[0]):
if l[t[g]]>l[t[i]]:
if end[1]<l[t[g]]:
end=[g+1,l[t[g]]]
p[i]=t[g]
o=1
break
if o==0:
p[i]=-1
end=[i+1,l[t[i]]]
for i in range(a-1):
print(p[i],end=" ")
print(-1)
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
반응형
'ps' 카테고리의 다른 글
BOJ 1574(룩 어택)풀이 (0) | 2021.01.12 |
---|---|
BOJ 2505(두 번 뒤집기)풀이 (0) | 2021.01.12 |
BOJ 18282(해킹) 풀이 (0) | 2021.01.10 |
BOJ 18138(리유나는 세일러복을 좋아해) 풀이 (0) | 2021.01.08 |
BOJ 19851(버거운 버거)풀이 (0) | 2021.01.07 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 정렬
- 느리게 갱신되는 세그먼트 트리
- 그래프 탐색
- 다이나믹 프로그래밍
- 트리에서의 다이나믹 프로그래밍
- 알고리즘
- C++
- 잡봇
- 트리
- 깊이 우선 탐색
- 그래프 이론
- 이분매칭
- 세그먼트 트리
- BOJ
- Python
- 이분 탐색
- 최소 스패닝 트리
- codeforces
- 완전 탐색
- 그리디 알고리즘
- 구현
- 자료 구조
- 누적 합
- discord bot
- KOI
- 자료구조
- A Dance of Fire and Ice
- 수학
- 선분 교차 판정
- 개발
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
글 보관함