백준 : 1620 (Python)

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

1. 내가 한 풀이(틀렸음)

import sys
n, m = map(int, sys.stdin.readline().split())
list1 = []
list2 = []
for _ in range(n):
    list1.append(sys.stdin.readline())

for _ in range(m):
    list2.append(sys.stdin.readline())

for i in list2:
    if i.isdigit():
        print(list1[int(i)-1])
    else:
        print(list1.index(i)+1)

정리하자면 리스트(O(n))는 딕셔너리(O(1))보다 시간복잡도가 더 복잡하기 때문에 시간초과를 해결할 수 없었다.

# 문제를 풀면서 얻어간 것

1. 숫자 판별 - isdigit()

2. 요소를 매개변수로 index 숫자(int형)을 추출할 수 있는 함수 - .index()

https://trey-de.tistory.com/7

백준 1620번: 나는야 포켓몬 마스터 - 파이썬

(참고한 사이트)

따라서 딕셔너리를 이용해서 문제를 풀어보았다.

 

 

* 추가로 공부해볼 내용

1. 시간복잡도와 공간복잡도 개념

앞으로 더 깊게 알고리즘 공부를 하기 위해서는 위의 개념을 이해해야 단순히 문제의 출력값을 내는 것 뿐만 아니라 조건에 맞게 코딩을 할 수 있을 것이다.

2. 인덱스 탐색이나 특정 문자를 검색할 때, dictionary를 사용하는 것이 유리할 수 있는데, 그 이유는 Python dictionary가 hash table을 사용한 것으로, 읽을 때 시간복잡도가 O(1)이기 때문이다.

이 두 가지의 내용은 따로 블로그에 글을 올려보면서 공부해보도록 하겠다.