BOJ 1620. 나는야 포켓몬 마스터 이다솜 1620번: 나는야 포켓몬 마스터 이다솜 (acmicpc.net) 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이 딕셔너리(dictionary)를 이용해서 풀면 된다. for문을 돌며 인덱스-문자열을 매치시켜 저장하고 이를 문제에 맞게 프린트 해주면 된다. 문제의 핵심은, 딕셔너리의 키-값을 번호-포켓몬이름으로 저장하면 포켓몬 이름, 즉 문자열이 나왔을때는 어떻게 값으로 키를 뽑아낼 것인가? int 형이 문제로 들어왔을때와 str..

BOJ 11723. 집합 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 풀이 set() 쓰면 되는데 쉽지~ 하면서 풀기 시작했는데 수많은 메모리 초과와 마주해야 했다.. 이유는 pypy3로 제출하였기 때문이였다. 지금껏 pypy3가 속도면에서 더 빠르다고 해서 계속 pypy3로 제출해왔는데 메모리면에서 이렇게 손해이면 python3로 제출하고 속도를 개선 할 방법을 찾는게 더 공부에 좋을지도 모르겠다. 스스로 속도를 개선하는것은 좋은 것이니. 또, command의 길이에 따라 ..

BOJ 11866. 요세푸스 문제 0 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 풀이 먼저 위의 그림처럼 그려보면서 문제를 이해하면 빠르다. 문제의 핵심은 원인 점과, 계속 3번째 사람을 구해야 하는데, 제거된 사람이 있는 자리는 건너 뛰어야 한다는 것이다. 나는 리스트를 이용해서, 제거된 사람을 -1로 표시하여 건너 뛰도록 하는 방법으로 구했다. for _ in range(N): cur %= N next = 0 cur은 현재 위치이다. for 루프를 돌 때 마다 cur %= N을 해주어 cur이 항상 N보다 작게 해주어 ..

BOJ 10828. 스택 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 어려운 문제는 아니나, 파이썬으로 풀이를 할 때 pop() 함수에 파이썬 내장함수 pop()을 사용하면 재귀호출을 하는 불상사가 생긴다. 이것이 유일하게? 주의할 점이다. 그래서 stack_top 변수로 스택의 사이즈를 관리하고, pop할때는 임시변수에 담았다가 del을 이용해 리스트에서 삭제하고, 임시변수에 담은것을 return 해 주었다. if ..

BOJ 10816. 숫자 카드 2 10816번: 숫자 카드 2 (acmicpc.net) 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 N개의 숫자카드 리스트에서 각 카드가 몇 장 있는지 알아내기 위해서 collections 모듈의 defaultdict 을 사용해 각 카드에 적인 정수를 키, 카드의 갯수를 값으로 설정한 딕셔너리를 생성했다. cards_dict = defaultdict(int) for n in cards_list: cards_dict[n] += 1 coll..

BOJ 9012. 괄호 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 여는괄호 '(' 면 스택에 담는다. 닫는괄호 ')' 면 스택에서 pop()한다. 만약 중간에 '('가 아닐 때, 스택이 비어있으면 괄호가 맞지 않는 것이므로 답은 "NO"이다. 루프가 종료되고 스택이 비어있으면 괄호가 맞는 것이므로 "YES" 루프가 종료되어도 스택에 무언가가 남아있다면 괄호가 맞지 않는 것이므로 "NO"이다. 소스코드 i..