๐ฅ Bronze1
https://www.acmicpc.net/problem/16466
โ ์ ๋ตํ์ด
import sys
input = sys.stdin.readline
N = int(input())
first_tickets = sorted(map(int, input().split()))
isEnd=True
for i in range(N): #0 1 2 3 4
if i+1!=first_tickets[i]:
print(i+1)
isEnd=False
break
#1์ฐจ์์ ๋คํ๋ฆฐ ๊ฒฝ์ฐ
if isEnd:
print(N+1)
๋ฉ๋ชจ๋ฆฌ | ์คํ์๊ฐ |
155528 | 340 |
์ฒ์์ list๋ฅผ ์ํํ๋ฉด์ in์ฐ์ฐ์๋ก ์ฒดํฌ๋ฅผ ํด๋ณด๋ ๋ฐฉ์์ผ๋ก ํ์๋๋ฐ, ์๊ฐ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค..
๊ทธ๋์ in ์ฐ์ฐ์๊ฐ ๋ชจ๋ ์์๋ฅผ ์์ฐจ์ ์ผ๋ก ํ์ํ๊ธฐ ๋๋ฌธ์ ์๊ฐ์ด๊ณผ๊ฐ ๋ฐ์ํ๋๊ฒ ๊ฐ์ ๋จ์ํ ์ ์๋น๊ต๋ก ๋ฐ๊ฟ์คฌ๋๋ ํด๊ฒฐ๋์๋ค.
set
ํ์๋ค ์ฝ๋๋ฅผ ๋ณด๋, ๋๊ฐ์ ๋ก์ง์ผ๋ก set์ผ๋ก ํ์ดํ ๊ฒฝ์ฐ๊ฐ ์์๋ค.
์ค๋ ๋ฌธ์ ๋ค์ ํ๋ฉด์ ์๊ฒ๋ ์ฌ์ค์ธ๋ฐ,
์ํ๋ฅผ ํ๋ฉด์ search๋ฅผ ํด์ผํ ๋ list๋ณด๋ค set์ด ๋ ๋น ๋ฅด๋ค.
์ด ๋ฌธ์ ๋ํ, list๋ก ํ์ด๋ฅผ ํ๋ฉด ์๊ฐ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค๊ณ ํ๋ค.
set ์๋ฃ๊ตฌ์กฐ๋ ํด์ ํ ์ด๋ธ์ ๊ตฌ์กฐ๋ก ๊ตฌํ๋๊ธฐ ๋๋ฌธ์, ํด์ ํจ์๋ก ํด์๊ฐ์ผ๋ก ๋ณํ๋๊ธฐ ๋๋ฌธ์ ํ์, ์ฝ์ , ์ญ์ ์์ O(1)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค๊ณ ํ๋ค.
set์ผ๋ก ํ์ด๋ณด๋ฉด 430ms์ ์คํ์๊ฐ์ธ๊ฒ์ ํ์ธํ ์ ์์๋ค.
'๋ฐฑ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-Python] ๊ฒ์ : 1072๋ฒ (0) | 2024.06.08 |
---|---|
[๋ฐฑ์ค-Python] ์ขํ ์์ถ : 18870๋ฒ (0) | 2024.06.07 |
[๋ฐฑ์ค-Python] ๋์ ์๋ฅด๊ธฐ : 1654๋ฒ (0) | 2024.06.07 |
[๋ฐฑ์ค-Python] ๋จ์ด ์ ๋ ฌ : 1181๋ฒ (0) | 2024.06.07 |
[๋ฐฑ์ค-Python] ํ์ ํ๋ ํ : 1021๋ฒ (0) | 2024.06.05 |