삽질메모장

문제 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 난이도 : 실버 2 유형 : 자료 구조, 우선순위 큐 접근법 백준의 문제 유형에 우선순위 큐 라고 되어 있지만 이 문제를 java util class PriorityQueue 갖다 쓰는것은 풀이에 의미가 없다고 생각한다. 물론 우선순위큐는 최소힙으로 구현 되는구나 라는것을 알수도있다 하지만 내 생각에는 해당문제는 최소힙의 알고리즘을 직접 구현하며 이해하기 위함이라고 생각한다. 풀이를 끝내면 구글에 검색하여 다른 사람들은 어떤풀이를 했는지..

문제 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 난이도 : 실버2 유형 : 그리디, 파싱 접근법 식을 최솟값으로 만들어야 하므로 -기호가 붙은 수들 이후는 모두 합산을 해야한다. 그러므로 -기준으로 식을 분리하고 분리된 각각의 식들은 최대한의 음수가 되기위해 합산해준다 1. 입력된 식을 StringTokenizer으로 받아 "-" 기준으로 식을 분리한다. 2. 분리된 각각의 토큰(식) 들을 합산한다. 3. 식의 첫번째값은 Integer.MAX_VALUE 와 같다면(식이 처음 입력되었다면) 대입, 이..

문제 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 난이도 : 실버 1 유형 : 그래프, BFS 접근법 1. 방문여부와 이동시간를 저장하는 배열 check 변수를 100,001의 범위로 생성한다. 이 변수를 이용해 이전이동값에서 +1 하는 방식으로 이동시간을 측정한다. 2. 큐에 처음위치를 추가하고, 큐에서 하나의 요소를 꺼낼때마다 해당요소에 +1, -1, *2 연산의 값을 큐에 저장한다. 이때 연산값은 0이상 100,001 이하 check[연산값] == 0 로 범위와 방문여부를 ..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 난이도 : 골드5 유형 : 구현, 자료구조, 덱, 문자열 접근법 처음 아이디어로 역순연산을 실제로 바꾸는 형식으로 짯으나 입력되는 배열의 길이가 길수록 엄청난 비효율을 나타대며 시간초과 에러가 나왓다. 다른 사람의 풀이를 슬쩍보니 역방향 연산을 하지않고 Boolean 변수로 역방향 여부만 체크한뒤 'D' 명령이 들어왔을때 덱의 앞부분 요소를 제거할지 뒷부분 요소를 제거할지 정하여 처리하였다. 그리고 16% 에서 틀린경우는 덱이 빈경우 error를 ..