JH 개발 블로그

https://www.acmicpc.net/problem/1911

음... 그냥 단순하게 정렬한 후 널빤지의 개수를 구하면 된다.

주의해야 할 건 널빤지의 길이는 정해져 있기 때문에 물웅덩이가 아닌 위치도 널빤지로 덮을 수 있다는 점.

만약 물웅덩이의 위치가 [1,5] [10,15] 이고, 널빤지의 길이가 20이라면 널빤지의 모든 물웅덩이를 커버 가능하다.

이부분만 생각해서 풀면 되는 간단한(?) 문제였다. 딱히 정렬말고 알고리즘을 쓸 필요도 없음...

물웅덩이는 최대 만개이다.

웅덩이의 위치값은 최소 0에서 최대 10억이다.

시간복잡도를 고려하면 범위를 for문으로 돌리면 안된다는 걸 알 수 있다.

import java.io.*;
import java.util.*;

public class Main {

    public static int answer = 0;
    public static int N,L;

    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());
        L = Integer.parseInt(st.nextToken());
		
        // 물웅덩이 위치 저장
        int[] waters = new int[2*N];

        for (int i=0; i<2*N; i+=2) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            waters[i] = start;
            waters[i+1] = end;
        }
		
        // 정렬해도 상관 없다. 입력에서 물웅덩이 위치가 겹치는 범위는 없으므로
        Arrays.sort(waters);
		
        // 널빤지의 가장 마지막 위치를 기억한다.
        int lastIdx = 0;

        for (int i=0; i<2*N; i+=2) {

            int start = waters[i];
            
            이미 물웅덩이에 널빤지가 존재한다면,
            시작점을 널빤지의 가장 마지막 위치 + 1로 잡는다.
            if (lastIdx >= start) {
                start = lastIdx + 1;
            }
            int end = waters[i+1];
            int length = end - start;
            
            // 이미 널빤지가 대져있을 수도 있기 때문에, 이런 경우는 continue
            if (length <= 0) continue;

		
       		// 널빤지 개수
            int cnt = length/L;

			// 널빤지 대고 남는 부분
            int res = length%L;

			// 남는 부분이 있으면, 널빤지개수를 1 증가시키고 마지막 널빤지위치를 구한다.
            if (res != 0) {
                cnt++;
                lastIdx = waters[i+1]-1 + (L - res);
            }

			// 답에 카운트 더하기
            answer += cnt;
        }

        System.out.println(answer);
    }
}

https://www.acmicpc.net/source/80479844

문제를 읽어보면, 서로 바라 볼 수 있는 사람의 쌍의 수를 구해야 한다.

조건은 두 사람 사이에, 둘중 아무나보다 키가 큰 사람이 존재하면 안된다는 것이다. ( 키가 동일하면 상관없다 )
처음엔 막연하게 이중포문을 생각했지만 N이 최대 50만 이기 때문에.. 절대 안된다 ! 

어렵다.. 머리 좋아지고 싶다..! 결국 보게 된 풀이..

스택을 사용한다. 

문제풀이 아이디어를 정리하면 다음과 같다.

1. 스택 만드는데 내림차순 스택임 (이유는 아래에)

2. 내림차순 스택을 만드는 과정에서 분기처리 잘하자

여기서 중요한점은 스택 내에  '앞으로 쌍이 될 가능성이 없는 사람' 은 제거한다.

예를들어 스택에 [3 2 1] 이 쌓여있다고 하자. 네번째에 키가 4인 사람이 들어왔다.

[3 2 1 4]가 된다. 네번째 사람은 첫번째~세번째 사람과 모두 쌍이 될 수 있다. 
근데 반대로 첫번째 ~ 세번째 사람은 네번째사람에게 가로막혀 앞으로 나올 사람들과 쌍이 절대 될 수 없다.

따라서 스택에서 제거한다.

다시 예를들어 [5 5 5]가 쌓여있다고하자. 네번째에도 키가 5인 사람이 들어왔다.

그럼 네번째 사람은 첫번째~세번째 사람과 모두 쌍이 될 수 있다. 근데 이걸 스택으로 어떻게 구현할것인가 ?

스택에 5 5 5 5 이렇게 쌓아두면 for문으로 5가 안나올때 까지 돌릴건가 ? 그건 시간초과다.

따라서 스택에 연속된 동일값은 하나만 저장해야한다. 그럴려면 연속된 동일값 개수를 카운트해야한다. 따라서 스택안의 타입은 인트배열로,  인트배열은 [키, 연속된 동일값 개수] 로 이루어진다.

import java.io.*;
import java.util.Stack;

public class Main {

    static int N;
    static Stack<int[]> stack = new Stack<>();
    static long answer;

    public static void main(String[] args) throws IOException {
        // N이 50만이기 때문에 웬만해선 O(N)이나 O(logN) 으로 해결해야함 . 
        // stack

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {

            // h => 키
            int h = Integer.parseInt(br.readLine());
            // cnt => 연속된 동일값 개수
            int cnt = 1;

            // 자신의 키와 스택에 쌓인 사람들의 키를 비교한다.
            // 만약 자신의 키가 스택에 있는 사람의 키보다 크다면 스택에서 사람을 지운다. (자신의 키가 더 크면 기존 스택에 있던 것들은 무용지물. 앞으로 나올 값들과 쌍이 될 수 없기 때문에 )
            // 스택은 내림차순으로 유지된다.
            while (!stack.isEmpty() && h > stack.peek()[0]) {
                int[] pop = stack.pop();
                answer += pop[1];
            }

            // 자신의 키와 스택에 있는 사람의 키가 같을 때.
            // 스택의 값을 없애고, 스택의 cnt만큼 현재 cnt에 추가한다.
            if (!stack.isEmpty() && h == stack.peek()[0]) {
                int[] pop = stack.pop();

                // 기존 스택 값을 없애기 때문에 answer에 더해준다.
                answer += pop[1];
                cnt += pop[1];
            }

            // 스택안에 사람이 있을 때. 쌍이 되므로 1을 더해줌
            if (!stack.isEmpty()) {
                answer++;
            }

            stack.push(new int[]{h, cnt});
        }

        bw.write(answer + "\n");
        bw.flush();
    }
}

https://www.acmicpc.net/problem/1644

문제를 읽어보면, "소수의 연속합"으로 특정 자연수를 나타내야 한다.

예시에 나와있듯이 20은 7+13으로 나타낼 수 있지만 "연속된 소수" 들이 아니기 때문에 (7과 13 사이에는 11이 있다)

잘못된 경우이다.

그럼 문제를 어떻게 풀어야 할지 생각해보면

1. 소수 리스트를 구한다. 특정 값이 소수인가? 가 아닌 범위내의 모든 소수들의 값을 구하는 것이기 때문에

에라토스테네스의 체를 사용한다.  시간복잡도는  O(n * log(log n))

2. 소수 리스트를 구했으면, "연속된 소수" 로 나타내야 하기 때문에 투포인터로 풀이가 가능할 것 같다.

에라토스테네스의 체와 투포인터로 풀이한 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    static boolean[] prime;
    static ArrayList<Integer> primeList;

    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        prime = new boolean[N+1];
        primeList = new ArrayList<>();

        // 에라토스테네스의 체
        for (int i = 2; i*i <= N; i++) {
            if (!prime[i]) {
                for (int j = i*i; j <= N; j += i) {
                    prime[j] = true;
                }
            }
        }

        for (int i = 2; i <= N; i++) {
            if (!prime[i]) {
                primeList.add(i);
            }
        }

        // 투포인터
        int start = 0, end = 0, sum = 0, cnt = 0;
        while (true) {
            if (sum >= N) sum -= primeList.get(start++);
            else if (end == primeList.size()) break;
            else sum += primeList.get(end++);

            if (sum == N) cnt++;
        }

        System.out.println(cnt);

    }
}

import heapq
import sys

N, K = map(int, sys.stdin.readline().split())
jewelryList = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
bagList = [int(sys.stdin.readline()) for _ in range(K)]
jewelryList.sort()
bagList.sort()

result = 0
temp = []

for bagWeight in bagList:
    while jewelryList and bagWeight >= jewelryList[0][0]:
        heapq.heappush(temp, -heapq.heappop(jewelryList)[1])  # Max heap

    if temp:
        result += heapq.heappop(temp)
    elif not jewelryList:
        break

print(-result)

힙은

1. 데이터가 지속적으로 정렬이 되어야 할 때
2. 데이터의 삽입 / 삭제가 빈번히 일어날 때
풀이시간을 많이 줄여줍니다.

만약 temp가 비어있는데, 보석리스트까지 비어있다면 종료합니다.
(가방의 개수가 많이 남아있어도 넣을 보석이 없으면 의미가 없습니다.)

import sys
import heapq
input = sys.stdin.readline
n = int(input())
li = [list(map(int,input().split())) for _ in range(n)]
li.sort(key=lambda x:x[1])
temp = []

for p,d in li:
    heapq.heappush(temp,p)
    if len(temp) > d:
        heapq.heappop(temp)
print(sum(temp))

n = int(input())
coin = [list(input()) for _ in range(n)]
ans = n * n + 1

for bit in range(1 << n):
    tmp = [coin[i][:] for i in range(n)]
    for i in range(n):
        if bit & (1 << i):
            for j in range(n):
                if tmp[i][j] == 'H':
                    tmp[i][j] = 'T'
                else:
                    tmp[i][j] = 'H'

    tot = 0
    for i in range(n):
        cnt = 0
        for j in range(n):
            if tmp[j][i] == 'T':
                cnt += 1
        tot += min(cnt, n-cnt)
    ans = min(ans, tot)

print(ans)

각 동전마다 뒤집는다/ 안뒤집는다 2가지 경우의 수가 있습니다.

만약 n개의 동전이 있다면 총 경우의 수는 2^n개가 됩니다.

tmp 각 열에서 T의 개수가 H보다 많다면, 열을 뒤집었다 칩니다.(n-cnt)