알루 코딩

맨 처음에, 솔직히 문제가 잘 이해가 가지 않았다. 일단 예제 입력을 그대로 문제에 적용해보면, 입력으로 주어진 배열 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 순으로 출력 될 것이다. 작성한 코드는 아래..

맨 처음에 문제를 이해하는데 시간이 좀 걸렸다. 이해한 바로는 이렇다. 「첫 줄에 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() → ..

백준 9012번 괄호 문제에서 소괄호 뿐만 아니라 대괄호도 추가되었다고 생각하면 된다. 입력의 종료조건으로 맨 마지막에 점 하나(".")만 들어온다고 했으니, 무한루프를 만들고, 입력이 점 하나(".")라면 프로그램이 종료되게 하고 그렇지 않으면 계속해서 입력을 하도록 구현하면 된다. 맨 처음에는 IndexError 가 났었다. (IndexError가 났었던 코드) stack = [] while(True): line = input() if(line == "."): break for s in line: if s == "(" or s == "[": stack.append(s) elif s == ")": if stack[-1] == "(": stack.pop() else: break elif s == "]":..

괄호 문제는 스택 문제중에서도 흔한 유형에 속한다. 여는 괄호와 닫힌 괄호가 쌍을 이루고, 짝이 맞는다면 올바른 괄호 문자열 (Valid PS, VPS) 인 것이다. (코드는 아래와 같다.-파이썬,python) import sys input = sys.stdin.readline testcase = int(input()) for i in range(testcase): bracket = [] stack = [] command = input() bracket.append(command) for j in command: if j == "(": stack.append(j) elif j == ")": if(len(stack) == 0): break else: stack.pop(-1) if(j == command[-..

전형적인 스택 문제이다. 파이썬에서는 스택을 구현할 때, 리스트를 활용하여 push 역할은 append() 로 구현하고 pop 역할은 pop() 으로 구현하면 된다. (코드는 아래와 같다. -python) k = int(input()) sum = 0 number_list = [] for i in range(k): n = int(input()) if n == 0: # 입력된 수가 0 이면 pop number_list.pop(-1) else: number_list.append(n) for answer in number_list: sum += answer print(sum) pop() 안에 따로 인덱스 인자를 안 넣어주면 맨 끝의 원소를 빼준다. (pop(-1) 이나 pop()이나 같은 역할이다.) (아래는 ..

파이썬에서 스택 자료구조 라이브러리를 따로 제공하지 않는다. 대신, 리스트를 스택으로 기능하도록 구현할 수 있다. 이 문제가 바로 그런 문제이다. 문제에서 주어진 다섯가지 명령을 함수로 만들어도 되는데, 우선 스택을 Class 로 만들어봤다. (코드는 아래와 같다.-python) import sys input = sys.stdin.readline class Stack: def __init__(self): self.stack = [] def __len__(self): # 스택의 길이(크기) return len(self.stack) def push(self, item):# 스택에 item 집어넣기 self.stack.append(item) def pop(self):# 스택의 가장 위에 있는 원소 빼내기 if..

일단, 문제 설명이 매우 짧다는 것은 어렵다는 소리일지도 모른다. 흔히 우리가 생각하는 방식으로 풀면 시간초과가 날 가능성이 높기 때문이다. 특히, 이 문제는 n,m 의 범위가 20억까지 들어올 수 있다는 설명을 보고 뭔가 다른 방식으로 풀어야 겠다는 생각이 들었다. '팩토리얼 0 의 개수' 문제처럼 끝자리 0의 개수를 출력하는 것은 맞지만, 이번에는 이항계수 개념이 도입된 문제였다. 이항계수(Binomial Coefficient)는 조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 일컫는다. 2를 상징하는 '이항'이라는 말이 붙은 이유는 하나의 아이템에 대해서는 '뽑거나' , '안 뽑거나' 두 가지의 선택만이 있기 때문이다. (출처 : shoark7.git..

시간제한이 2초여서 팩토리얼 함수를 재귀로 구현해도 무방한 문제 같았다. 주어진 n 에 따라 팩토리얼 함수로 n! 구하고 그 n! 을 string 화시켜서 뒤에서부터 0의 개수를 세면 되는 문제였다. (코드는 아래와 같다.-python) def factorial(n): # 팩토리얼을 구하는 재귀함수 if n == 0: return 1 elif n == 1: return 1 else: return factorial(n-1)*n def findzero(n): # 숫자 맨 뒤에 0이 몇개 있는지 출력하는 함수 cnt = 0 string_number = str(n) reverse_number = string_number[::-1] for s in reverse_number: if s != '0': break e..

문제를 이해하면서, 파이썬의 딕셔너리 개념을 사용해야 한다고 생각했다. 딕셔너리는 기본적으로 중괄호({}) 를 사용해서 데이터를 묶는 형태를 띄며, 키(key)와 밸류(value)가 하나의 아이템(item)을 구성하게 된다. 즉, 딕셔너리에는 특정한 key값과 value 값이 서로 짝지어서 저장된다고 이해하면 편하다.(해쉬처럼 말이다.) 파이썬을 공부하면서 문제를 풀다 보니, 딕셔너리를 어떻게 사용해야 할지 감이 잘 안 왔다. 처음에 풀었던 코드는 아래와 같았다. (런타임 오류가 났었던 코드) testcase = int(input()) for test in range(testcase): n = int(input()) clothes = {} # clothes 라는 빈 딕셔너리 생성 for i in rang..

전형적인 그리디 알고리즘 문제이다. 처음에는 계속 시간초과 문제를 해결하지 못했었다. 처음에 풀었던 코드는 이러했다. n = int(input()) roads = list(map(int, input().split())) prices = list(map(int, input().split())) total = prices[0] * roads[0] # 출발 도시의 기름가격 x 출발 도시와 두번째 도시 사이의 도로길이 previous_price = prices[0] # previous_price 에 우선 출발 도시의 가격 저장 # k 라는 변수를 1로 잡았다(두번째 도시와 세번째 도시 사이의 도로 길이 인덱스는 1 이므로) k = 1 # 도시 간격(도로 길이)를 나타내는 인덱스 for i in prices[1:..