https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 열심히 종이에 그려가면서 구하려고 했는데 너무 복잡하게 생각한 탓인지 못풀었다. 결국 해설을 듣고 알게되었는데, 내가 처음에 잠깐 생각한 '행별로 누적합 구해서 더하기'가 맞았다. 시간초과날 것 같아서 안해봤는데.. 시간초과 각오하고 시도해보는 것도 좋을 것 같다라는 생각이 들었다. 괜히 시간초과 날 것 같다고 다른 방법 생각하다가 더 복잡하게 생각하고 ..

https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 부분문자열을 구하는 문제로 처음에는 for문을 중첩해서 구하는 방법을 생각했다. 하지만 시간초과가 났다. 입력되는 문자열의 길이가 최대 1,000,000(백만)이다. for문을 중첩해서 돌린다면 O(n^2) 약 1,000,000(백만) * 1,000,000(백만) = 억 단위가 넘어가서 1초 안에 풀지 못한다... 실패 import java.io.BufferedReader;..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이전에 한 번 푼 적이 있어서 풀이법을 떠올리는 건 쉬웠다. 1.정렬 : 우선 끝나는 시간을 기준으로 오름차순 정렬을 하고, 끝나는 시간이 같은 경우에는 시작 시간을 기준으로 오름차순 정렬을 한다. 2. 모든 시간에 대해서 끝나는 시간을 기준으로 하여 가능한 다음 회의 시작 시간을 찾는다. 2차원 배열을 정렬하는데, Arrays.sort와 Comparator 사용이 아직 미숙하다. 코드 import java.io.BufferedReader; import java.io.IOException; import java...

https://www.acmicpc.net/problem/2563 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 처음에는 좌표를 가지고 사칙연산을 통해 넓이를 구하려고 했다. 하지만 넓이를 2차원 배열로 생각하고 색종이를 붙일 때마다 덮게 되는 부분에 1을 넣어주고, 최종적으로 넓이를 구할 때 1인 부분을 카운딩해주면 된다. 이렇게 생각하면 간단한 문제! 복잡하게 생각하지 말자. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.I..

https://programmers.co.kr/learn/courses/30/lessons/76502 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 괄호 문제는 Stack을 활용하는 것으로 유명하다. 이전에 백준에서 풀어본적이 있었다. 하지만 이 문제는 괄호가 (, [, {로 종류가 다양해서 각 종류마다 처리를 해줘야 해서 경우의 수를 잘 따져야 한다. 또한 판별하기 전에 추가로 회전처리도 해줘야 한다. 두 부분으로 나누어서 구현했다. 1. 매번 왼쪽으로 한 칸씩 회전을 하는 함수 rotate(s) (x가 1이상일 때) -> 1~s.length까지 문자들을 결합하고, 뒤에 0번째 문자를 붙인 새로운 문자열을 반환. 2. 올바른 괄호 문자열인지 판변하는 함수 isCorrect(s) ->..

https://programmers.co.kr/learn/courses/30/lessons/12985 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 간단해보이는데 은근 까다로웠다. 모든 테스트 케이스를 통과하지 못해 삽질을 좀 했다... n은 이용할 필요없이, a와 b를 나눗셈 연산을 이용해서 관계를 파악해서 풀면 된다. 같은 대진에서 붙으려면, (자신의 수 + 1) / 2 가 같아야 한다. 종료조건은 a와 b가 같이 묶여있을 때를 저렇게 표현했다. 코드 class Solution ..