백준 문제: 1193 분수찾기 (Python)

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

import sys

n = int(sys.stdin.readline())
l1 = []
for i in range(n):
    l = []
    for j in range(1, i+1):
        l.append('%d/%d' % (i+1-j, j))
    l1.append(l)
l1 = l1[1:]
for i in range(len(l1)):
    if i % 2 == 1:
        l1[i] = list(reversed(l1[i]))
li = []
for i in range(len(l1)):
    li += l1[i]

print(li[n-2])

시간초과 오류

---

+수정

미해결이었다가 해결했다.
거의 하루를 다 투자 한듯...
집중 못한게 컸던 것 같다.

먼저 이 문제에서 가장 중요한것은 내 경험상으로는 시간 초과가 매우 자주 일어났다.
이 문제에서 시간초과를 피하기 위해서는 파이썬의 시간 복잡도를 참고하는 것이 좋다.
https://wiki.python.org/moin/TimeComplexity
파이썬의 내장함수는 매우 많은 시간을 소요하는 경우가 많은데, 나 같은 경우는 리스트를 사용하여 계속 시간 초과가 뜨고, 메모리 초과가 뜨는 경우였다.

import sys
n = int(sys.stdin.readline()) #입력 받기
j = 0 #이 변수는 계속해서 증가해서, 우리가 출력할때 알맞은 값을 표현 해주는 역할을 한다.
stage = 1 #나는 이 문제를 각 분수마다, 단계를 구분하여 생각하였다.
for i in range(n):
    j += 1
    if i == n-1: #i가 n-1과 같은 값을 가지게 된다면, 내가 원하는 값을 가지게 된것이므로, 이제 값을 출력할 차례이다.
        if stage % 2 == 0: #스테이지값이 짝수일 경우
            print('%d/%d' % (j, stage-j+1))
        else:#스테이지 값이 홀수 일 경우
            print('%d/%d' % (stage-j+1, j))
    if stage == j: #stage값이 j와 같아지면 j는 초기화해서 다시 처음부터 증가되어야 하고, stage는 1 증가하여야 한다.
        j = 0
        stage += 1