실버 23

[백준/알고리즘/python/java] 1417번 - 국회의원 선거

정답률이 낮은 이유는 아마 제출 수가 적은 것도 그렇지만, 예외처리 때문일 것이다.나도 한 2번 틀리고 반례를 발견했으니 말이다.우선, 시간제한도 2초로 넉넉한 편이어서 for문이나 while문 사용에 거부감이 없었다.이번 코드리뷰는 내가 제출했었던 코드들을 순차적으로 살펴보자. 맨 처음 제출해서 틀렸던 코드는 아래와 같다.import sysinput = sys.stdin.readlinen = int(input())vote_list = []count = 0for i in range(n): vote_list.append(int(input()))dasom = vote_list[0]not_dasom = sorted(vote_list[1:], reverse=True)print(not_dasom[0]-das..

[백준/알고리즘/python/java] 18870번 - 좌표 압축

이 문제도 처음에 시간제한에 걸려서 시간초과가 났었던 문제이다. 로직은 간단한데, 시간초과가 났다면, 분명 어떤 라이브러리를 사용하는 것이거나 더 효율적인 자료구조가 있는 것이다. 방법을 고수하지말고 바꿔야 하는 것을 명심하자. 문제마다 어떤 자료구조로 풀어야 효과적인지 판단하는 것도 중요한 것 같다. 맨 처음 풀었던 코드는 아래와 같다. import sys input = sys.stdin.readline N = int(input()) number_list = [int(num) for num in input().split()] sorted_number_list = sorted(number_list) for i in number_list: order = 0 seen = -1 for j in sorted_n..

[백준/알고리즘/python/java] 1764번 - 듣보잡

정답 비율이 높지 않아서, 뭔가 시간초과와 관련된 문제이겠거니 싶었다. 역시나 처음 풀었던 코드는 시간초과에 걸렸다. 아래는 처음 시간초과에 걸렸던 코드이다. import sys import collections input = sys.stdin.readline a, b = map(int, input().split()) answer = [] no_heard = [input().strip() for i in range(a)] no_seen = [input().strip() for i in range(b)] if a < b: for word in no_heard: if(word in no_seen): answer.append(word) else: for word in no_seen: if(word in no_..

[백준/알고리즘/python/java] 2164번 - 카드2

맨 처음에 시간초과가 났던 코드였다. 심지어 PyPy3로도 시간초과가 났었다. 로직은 단순한데, 시간초과가 났다면 다른 라이브러리의 힘을 빌려야 하는 순간이다. 기존 리스트로 카드 세트를 생성하고 처음엔 remove나 del 함수를 사용했지만, 단순히 pop 함수를 사용해도 되는데, 파이썬의 list는 중간에 있는 요소를 pop할 때 시간복잡도가 O(n)이지만, collections.deque는 시간복잡도가 O(1) 라고 한다. 먼저 맨 처음에 작성했던 코드는 아래와 같다. import sys input = sys.stdin.readline n = int(input()) card_list = [] for i in range(n, 0, -1): card_list.append(i) while(len(card..

[백준/알고리즘/python/java] 1015번 - 수열 정렬

맨 처음에, 솔직히 문제가 잘 이해가 가지 않았다. 일단 예제 입력을 그대로 문제에 적용해보면, 입력으로 주어진 배열 A의 원소 2 3 1 은 아래와 같이 표현할 수 있다. B[P[0]] = A[0]->B[1] = 2 B[P[1]] = A[1]->B[2] = 3 B[P[2]] = A[2]->B[0] = 1 다시한번, 문제를 잘 읽어보면, 여기서 B배열은 A배열의 비내림차순 배열이라는 것을 알 수 있었다. 우리는 A배열로부터 B배열을 만들었는데, 그럼 자연스럽게 P배열은 A배열의 원소 크기 순이라는 것을 알 수 있다. 여기서 만약, 동일한 크기의 원소라면, 앞서 있는 것을 먼저 출력하면 된다. 예를 들어 A 배열이 1 3 2 2 라고 하면 P배열은 0 3 1 2 순으로 출력 될 것이다. 작성한 코드는 아래..

[백준/알고리즘/python/java] 1874번 - 스택 수열

맨 처음에 문제를 이해하는데 시간이 좀 걸렸다. 이해한 바로는 이렇다. 「첫 줄에 n 이 입력되면, 둘째 줄 부터는 1부터 n 까지의 수를 차례로 입력한다. 그렇게 입력된 n 개의 수가 수열을 형성하도록 push 연산은 +, pop 연산은 - 로 표현하도록 출력하면 된다.」 이해가 안되면, 힌트를 보면 된다. 첫 번째 예제입력은 [4,3,6,8,7,5,2,1] 순으로 입력되었다. 이렇게 수열을 이루려면(출력이 예제입력처럼 되려면), 빈 stack = []에 차례로 push(1) → push(2) → push(3) → push(4) → pop() → pop() → push(5) → push(6) → pop() → push(7) → push(8) → pop() → pop() → pop() → pop() → ..

반응형