public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
int nNum = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
pq.offer(Integer.parseInt(st.nextToken()));
}
}
while (n-- > 0) {
nNum = pq.poll();
}
System.out.println(nNum);
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
MinHeap minHeap = new MinHeap();
while (n-- > 0) {
int x = Integer.parseInt(br.readLine());
if (x != 0) minHeap.offer(x);
else sb.append(minHeap.poll()).append("\n");
}
System.out.println(sb);
}
private static class MinHeap {
int[] heap = new int[100001];
int size = 0;
void offer(int x) {
heap[++size] = x;
int idx = size;
while (idx != 1) {
int cur = idx/2;
if (heap[idx] > heap[cur]) break;
swap(idx, cur);
idx = cur;
}
}
int poll() {
if (size == 0) return 0;
int r = heap[1];
heap[1] = heap[size--];
int idx = 1;
while (idx * 2 <= size) {
int left = idx * 2;
int right = left + 1;
int min = left;
if (right <= size && heap[right] < heap[left]) min = right;
if (heap[min] >= heap[idx]) break;
swap(min, idx);
idx = min;
}
return r;
}
void swap(int x, int y) {
int tmp = heap[x];
heap[x] = heap[y];
heap[y] = tmp;
}
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->
Math.abs(a) == Math.abs(b) ? (a - b) : (Math.abs(a) - Math.abs(b)));
for (int i = 0; i < n; i++) {
int x = Integer.parseInt(br.readLine());
if (x != 0) {
pq.offer(x);
} else {
sb.append(pq.isEmpty() ? 0 : pq.poll()).append("\n");
}
}
System.out.println(sb);
}
}
두 번째 풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<>(n);
Map<Integer, Integer> countMap = new HashMap<>();
for (int i = 0; i < n; i++) {
int x = Integer.parseInt(br.readLine());
if (x != 0) {
int abs = Math.abs(x);
int count = countMap.getOrDefault(abs, 0);
if (x < 0) count++;
countMap.put(abs, count);
pq.offer(abs);
} else {
if (pq.isEmpty()) sb.append(0).append("\n");
else {
int num = pq.poll();
int count = countMap.get(num);
if (count != 0) {
sb.append(-num).append("\n");
countMap.put(num, count - 1);
} else {
sb.append(num).append("\n");
}
}
}
}
System.out.println(sb);
}
}
풀고 나서 비트 연산을 통한 풀이도 봤는데 아직 이런 방법으로는 풀이를 못 떠올리겠다...
시뮬레이션 문제들은 기능이나 중복된 코드들을 메서드로 분리하여
간결하고 가독성 있게 풀 수도 있지만 막상 풀고 나서 코드를 정리하려니 귀찮아서
풀 때부터 메서드로 분리하려고 노력해야겠다.
풀이
public class Main {
private static int n;
private static int m;
private static int r;
private static int c;
private static int[][] sticker;
private static int[][] notebook;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int result = 0;
notebook = new int[n][m];
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
sticker = new int[r][c];
int plus = 0;
for (int j = 0; j < r; j++) {
st = new StringTokenizer(br.readLine());
for (int l = 0; l < c; l++) {
int num = Integer.parseInt(st.nextToken());
sticker[j][l] = num;
if (num == 1) plus++;
}
}
if (stick()) result += plus;
}
System.out.println(result);
}
private static boolean stick() {
for (int rota = 0; rota < 4; rota++) {
if (rota % 2 == 0) {
for (int i = 0; i <= n - r; i++) {
for (int j = 0; j <= m - c; j++) {
if (rotation(rota, i, j)) return true;
}
}
} else {
for (int i = 0; i <= n - c; i++) {
for (int j = 0; j <= m - r; j++) {
if (rotation(rota, i, j)) return true;
}
}
}
}
return false;
}
private static boolean rotation(int rota, int st, int ed) {
int a = 0;
if (rota == 0) {
for (int i = 0; i < r; i++) {
int b = 0;
for (int j = 0; j < c; j++) {
if (sticker[i][j] == 1 && notebook[st + a][ed + b] == 1) return false;
b++;
}
a++;
}
paste(rota, st, ed);
} else if (rota == 1) {
for (int i = 0; i < c; i++) {
int b = 0;
for (int j = r - 1; j >= 0; j--) {
if (sticker[j][i] == 1 && notebook[st + a][ed + b] == 1) return false;
b++;
}
a++;
}
paste(rota, st, ed);
} else if (rota == 2) {
for (int i = r - 1; i >= 0; i--) {
int b = 0;
for (int j = c - 1; j >= 0; j--) {
if (sticker[i][j] == 1 && notebook[st + a][ed + b] == 1) return false;
b++;
}
a++;
}
paste(rota, st, ed);
} else {
for (int i = c - 1; i >= 0; i--) {
int b = 0;
for (int j = 0; j < r; j++) {
if (sticker[j][i] == 1 && notebook[st + a][ed + b] == 1) return false;
b++;
}
a++;
}
paste(rota, st, ed);
}
return true;
}
private static void paste(int rota, int st, int ed) {
if (rota == 0) {
for (int i = 0; i < r; i++) {
int b = 0;
for (int j = 0; j < c; j++) {
if (sticker[i][j] == 1) notebook[st][ed + b] = 1;
b++;
}
st++;
}
} else if (rota == 1) {
for (int i = 0; i < c; i++) {
int b = 0;
for (int j = r - 1; j >= 0; j--) {
if (sticker[j][i] == 1) notebook[st][ed + b] = 1;
b++;
}
st++;
}
} else if (rota == 2) {
for (int i = r - 1; i >= 0; i--) {
int b = 0;
for (int j = c - 1; j >= 0; j--) {
if (sticker[i][j] == 1) notebook[st][ed + b] = 1;
b++;
}
st++;
}
} else {
for (int i = c - 1; i >= 0; i--) {
int b = 0;
for (int j = 0; j < r; j++) {
if (sticker[j][i] == 1) notebook[st][ed + b] = 1;
b++;
}
st++;
}
}
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[] history = new int[k + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= k; i++) {
history[i] = Integer.parseInt(st.nextToken());
}
int tab = n;
int[] arr = new int[n];
boolean[] isUsed = new boolean[k + 1];
int count = 0;
for (int i = 1; i <= k; i++) {
int target = history[i];
int idx = 0;
int late = 0;
if (isUsed[target]) continue;
if (tab > 0) {
tab--;
for (int j = 0; j < n; j++) {
if (arr[j] == 0) {
arr[j] = target;
break;
}
}
isUsed[target] = true;
continue;
}
count++;
for (int j = 0; j < n; j++) {
int use = arr[j];
int x = 0;
for (int l = i + 1; l <= k; l++) {
if (history[l] == use) {
x = l;
break;
}
}
if (x == 0) {
idx = j;
break;
}
if (x > late) {
late = x;
idx = j;
}
}
tab--;
isUsed[arr[idx]] = false;
isUsed[target] = true;
arr[idx] = target;
}
System.out.println(count);
}
}
// 음수로 만들 수 있는 최적의 해
음수 * 0이하의 수
// 양수로 만들 수 있는 최적의 해
양수 * 양수
양수 + 1
양수는 0과 곱하거나 더하는 경우에는 어떤 이득도 볼 수 없기 때문에
0은 위와 같이 음수와 처리해주는 것이 좋다.
수열을 입력 받을 때 0이하의 수가 등장할 때마다
따로 변수에 카운팅을 해준 후에
수열을 오름차순으로 정렬하면
0번 인덱스 부터 카운팅한 만큼까지가 0이하의 수에 해당하고
이후의 인덱스들은 모두 양수라는 것을 알 수 있다.
-3
-2
-1
위와 같은 수열이 주어졌을 때를 생각해보면
-3과 -2를 곱하여 6을 만들고 -1을 빼서 5를 얻는 경우가 최적의 해이고
-2
-1
위와 같은 경우는 둘이 그대로 곱해 2를 얻는 경우가 최적의 해인데
여기서 알 수 있는 것이 0이하의 개수가 홀수면
마지막 인덱스를 제외한 값들은 서로 곱하고 마지막만 빼주면 되고
개수가 짝수면 모두 서로 곱해주면 된다.
양수의 경우는 반대로 개수가 홀수면
첫 인덱스 값을 더해주고 나머지 값들을 서로 곱해주고
짝수면 모두 서로 곱해주면 된다.
이제 정리한 내용들을 토대로
0번 부터 COUNT - 1번 인덱스 까지의 음수들을 처리하는 부분과
COUNT번 부터 N - 1번 까지의 양수들을 처리하는 부분을 계산해주면 된다.
풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int count = 0;
int[] seq = new int[n];
for (int i = 0; i < n; i++) {
int x = Integer.parseInt(br.readLine());
seq[i] = x;
if (x <= 0) count++;
}
Arrays.sort(seq);
long prev = -1001;
long sum = 0;
for (int i = 0; i < count; i++) {
int cur = seq[i];
if (i == count - 1 && count % 2 != 0) {
sum += cur;
continue;
}
if (prev < -1000) {
prev = cur;
continue;
}
sum += (prev * cur);
prev = -1001;
}
prev = -1001;
for (int i = count; i < n; i++) {
int cur = seq[i];
if (i == count && (n - count) % 2 != 0) {
sum += cur;
continue;
}
if (prev < -1000) {
prev = cur;
continue;
}
if (prev * cur == cur) sum += (prev + cur);
else sum += (prev * cur);
prev = -1001;
}
System.out.println(sum);
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
int[][] xy = new int[n][2];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
xy[i][0] = Integer.parseInt(st.nextToken());
xy[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(xy, (o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]);
int s = xy[0][0];
int e = xy[0][1];
int len = e - s;
for (int i = 1; i < n; i++) {
int x = xy[i][0];
int y = xy[i][1];
if (y <= e) continue;
if (x <= e) {
len += (y - e);
} else {
len += y - x;
}
e = y;
}
System.out.println(len);
}
}
