초니로그

문제 URL

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

문제 설명 요약

• 키가 작은 학생이 더 큰 학생보다 앞에 서도록 줄 세우기

문제 풀이

• 위상정렬 사용
• 키 비교 값을 방향을 가진 간선 정보로 사용
• indegree의 값을 통해 우선적으로 위치해야 하는 정점들을 파악해나감
  • 주어진 키 비교값을 통해 정점간의 선후 관계를 indegree 배열로 표현
    만약 1 2 라면 1 -> 2 이므로, 2의 indegree 값에 1이 추가됨
  • 맨 처음부터 indegree의 값이 0인 정점들을 모두 큐에 추가
    (indegree가 0이라는 것은 곧 반드시 해당 정점보다 앞에 위치해야 하는 정점이 없다는 것과 같은 의미)
  • 큐가 빌 때까지 돌면서, 큐에서 빼낸 정점에서 뻗어나가는 정점들의 indegree 값을 1 감소시킴
    (큐에서 빼낸 정점을 의미적으로 삭제하기 위함)
  • 감소시킨 indegree값이 0이라면 앞선 로직처럼 큐에 추가

Swift를 활용한 풀이

let nm = readLine()!.split(separator: " ").map{Int($0)!}
var ind = Array(repeating: 0, count: nm[0]+1) // 1-index
var adj:[Int:[Int]] = [:]

for n in 1...nm[0] { adj[n] = [] }

for _ in 0..<nm[1] {
    let ab = readLine()!.split(separator: " ").map{Int($0)!}
    ind[ab[1]] += 1
    adj[ab[0]]!.append(ab[1])
}

var q:[Int] = []
for i in 1...nm[0] {
    if(ind[i] == 0) { q.append(i) } // 처음부터 indegree가 0인 정점을 큐에 추가해둠
}

var answer = ""
while(!q.isEmpty) {
    // 큐에 추가된 정점을 하나씩 꺼내어, 해당 정점에서 뻗어나가는 정점들의 indegree를 1 감소시킴
    // 감소된 indegree값이 0이라면, 해당 정점의 앞에 위치해야 하는 정점들이 모두 사라진 것으로 간주되므로 큐에 추가
    let cur = q.removeFirst()
    answer += "\(cur) "
    for n in adj[cur]! {
        ind[n] -= 1
        if(ind[n] == 0) { q.append(n) }
    }
}

print(answer)

JAVA를 활용한 풀이

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] ind = new int[N+1];
        HashMap<Integer, ArrayList<Integer>> adj = new HashMap<>();

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            ind[b]++;

            ArrayList<Integer> list = adj.getOrDefault(a, new ArrayList<Integer>());
            list.add(b);
            adj.put(a, list);
        }

        Queue<Integer> q = new LinkedList<>();
        for(int i=1; i<=N; i++) {
            if(ind[i] == 0) q.offer(i);
        }

        while(!q.isEmpty()) {
            int cur = q.poll();
            sb.append(cur).append(" ");

            if(adj.get(cur) != null) {
                for(int n : adj.get(cur)) {
                    ind[n]--;
                    if(ind[n] == 0) q.offer(n);
                }
            }
        }

        System.out.println(sb);
    }
}

문제 URL

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

문제 설명 요약

• 최소힙을 활용하여 카드 묶음의 값 정렬
• 작은 값부터 꺼내고 더해가며 최소 비교 횟수 구하기

문제 풀이

• 최소힙 직접 구현 필요 (스위프트는 힙 자료구조 없음)
  • Heap :: push -> 추가되는 값을 힙 내 원소들과 비교하여 저장 
  • Heap :: pop -> 최소힙의 값(최상단 루트 값) 삭제 및 반환

Swift를 활용한 풀이

var heap = [0] // 1-based-index
let N = Int(readLine()!)!
for _ in 0..<N { push(Int(readLine()!)!) }

// 카드 묶음의 값을 두 개씩 꺼내어 합쳐나가는 과정 
// 합치는 것의 대상 두 묶음을 답에 누적 & 합쳐진 값은 새로운 카드 묶음으로 취급(push)
var answer = 0
while(heap.count > 2) {
    let a = pop()
    let b = pop()
    answer += a+b
    push(a+b)
}
print(answer)

// 힙에 원소 추가
// 1. 배열 맨 끝에 추가
// 2. 끝 인덱스 값을 시작으로 부모값과의 대소 비교 후, 부모값보다 작다면 스왑 수행
// 3. (2)번 작업을 idx가 1까지 줄어들기 전까지 진행함. 단, 그 이전에 부모값보다 큰 경우엔 탈출
func push(_ n:Int) {
    heap.append(n)
    if(heap.count == 2) { return }

    var idx = heap.count-1
    while(idx > 1) {
        let parent = idx/2
        if(heap[parent] <= heap[idx]) { break }
        heap.swapAt(parent, idx)
        idx = parent
    }
}

// 최소힙의 값 삭제(루트 삭제) 및 반환
// 1. 힙의 맨 끝의 값을 루트로 이동
// 2. 갱신된 루트값에 대하여 자식값 두 개와 비교 후, 더 작은 자식 값이 있는 경우 스왑 수행
// (2)번 작업을 자식 인덱스값이 배열 범위 내에 있는 경우에 한하여 진행. 단, 두 자식보다 부모의 값이 작은 경우엔 탈출
func pop() -> Int {
    if(heap.count == 1) { return 0 }

    let deleted = heap[1]
    heap[1] = heap[heap.count-1]
    heap.removeLast()

    var idx = 1
    while(idx*2 < heap.count) {
        let left = idx*2, right = idx*2+1
        var minIdx = left
        if(right < heap.count && heap[right] < heap[left]) { minIdx = right }

        if(heap[idx] < heap[minIdx]) { break }
        heap.swapAt(idx,minIdx)
        idx = minIdx
    }
    return deleted
}

문제 URL

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

문제 설명 요약

• 최소힙을 활용하여 주어지는 연산 처리
• 단, 최소힙의 우선순위는 "절댓값이 작은 것, 절댓값이 같다면 값이 작은 것"

문제 풀이

• 최소힙 직접 구현 필요 (스위프트는 힙 자료구조 없음)
  • Heap :: push -> 추가되는 값을 힙 내 원소들과 비교하여 저장 
  • Heap :: pop -> 최소힙의 값(최상단 루트 값) 삭제 및 반환

Swift를 활용한 풀이

var heap = [0] // 1-based-index
let N = Int(readLine()!)!
for _ in 0..<N {
    let x = Int(readLine()!)!
    if(x == 0) { print(pop()) }
    else { push(x) }
}

// 힙에 원소 추가
// 1. 배열 맨 끝에 추가
// 2. 끝 인덱스 값을 시작으로 부모값과의 대소 비교 후, 부모값보다 작다면 스왑 수행
// 3. (2)번 작업을 idx가 1까지 줄어들기 전까지 진행함. 단, 그 이전에 부모값보다 큰 경우엔 탈출
func push(_ n: Int) {
    heap.append(n)
    if(heap.count == 2) { return }

    var idx = heap.count-1
    while(idx > 1) {
        let parent = idx/2
        if(abs(heap[idx]) > abs(heap[parent])) { break }
        else if(abs(heap[idx]) == abs(heap[parent]) && heap[idx] > heap[parent]) { break }
        heap.swapAt(idx,parent)
        idx = parent
    }
}

// 최소힙의 값 삭제(루트 삭제) 및 반환
// 1. 힙의 맨 끝의 값을 루트로 이동
// 2. 갱신된 루트값에 대하여 자식값 두 개와 비교 후, 더 작은 자식 값이 있는 경우 스왑 수행
// (2)번 작업을 자식 인덱스값이 배열 범위 내에 있는 경우에 한하여 진행. 단, 두 자식보다 부모의 값이 작은 경우엔 탈출
func pop() -> Int {
    if(heap.count == 1) { return 0 }

    let deletedValue = heap[1]
    heap[1] = heap[heap.count-1]
    heap.removeLast()

    var idx = 1
    while(2*idx < heap.count) {
        let left = 2*idx, right = 2*idx+1
        var minIdx = left
        if(right < heap.count && abs(heap[right]) < abs(heap[left])) { minIdx = right }
        else if(right < heap.count && abs(heap[right]) == abs(heap[left]) && heap[right] < heap[left]) { minIdx = right }

        if(abs(heap[idx]) < abs(heap[minIdx])) { break }
        else if(abs(heap[idx]) == abs(heap[minIdx]) && heap[idx] < heap[minIdx]) { break }
        
        heap.swapAt(idx,minIdx)
        idx = minIdx
    }
    return deletedValue
}

문제 URL

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

문제 설명 요약

• 최소힙을 활용하여 주어지는 연산 처리

문제 풀이

• 최소힙 직접 구현 필요 (스위프트는 힙 자료구조 없음)
  • Heap :: push -> 추가되는 값을 힙 내 원소들과 비교하여 저장 (부모는 자식 두 개보다 값이 작아야 함)
  • Heap :: root -> 최소힙의 최상단 루트 값 조회
  • Heap :: pop -> 최소힙의 값 삭제 (최상단 루트 값의 삭제)

Swift를 활용한 풀이

var heap = [-1] // 1-based index

let N = Int(readLine()!)!
for _ in 0..<N {
    let x = Int(readLine()!)!
    if x == 0 {
        print(root())
        pop()
    } else {
        push(x)
    }
}

// 힙에 원소 추가
// 1. 배열 맨 끝에 추가
// 2. 끝 인덱스 값을 시작으로 부모값과의 대소 비교 후, 부모값보다 작다면 스왑 수행
// 3. (2)번 작업을 idx가 1까지 줄어들기 전까지 진행함. 단, 그 이전에 부모값보다 큰 경우엔 탈출
func push(_ n: Int) {
    heap.append(n)

    var idx = heap.count - 1
    while(idx > 1) { // 반복문 내에서 부모값을 조회하고자, /2를 수행하기 때문에 1보다 커야 함
        let parent = idx / 2
        if heap[parent] <= heap[idx] { break }
        heap.swapAt(parent, idx)
        idx = parent
    }
}

// 힙의 최상단 값 조회
func root() -> Int {
    return heap.count > 1 ? heap[1] : 0
}

// 최소힙의 값 삭제(루트 삭제)
// 1. 힙의 맨 끝의 값을 루트로 이동
// 2. 갱신된 루트값에 대하여 자식값 두 개와 비교 후, 더 작은 자식 값이 있는 경우 스왑 수행
// (2)번 작업을 자식 인덱스값이 배열 범위 내에 있는 경우에 한하여 진행. 단, 두 자식보다 부모의 값이 작은 경우엔 탈출
func pop() {
    if heap.count <= 1 { return } // 빈 힙 예외 처리

    heap[1] = heap[heap.count - 1] // 마지막 요소를 루트에 복사
    heap.removeLast() // 마지막 요소 제거(제거하지 않으면 불필요한 끝값이 지속적으로 쌓여 더미가 커짐)

    var idx = 1
    while(2*idx < heap.count) {
        let left = 2 * idx
        let right = left + 1
        var minIdx = left

        if(right < heap.count && heap[right] < heap[left]) { minIdx = right }

        if heap[idx] <= heap[minIdx] { break }
        heap.swapAt(idx, minIdx)
        idx = minIdx
    }
}

문제 URL

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

문제 설명 요약

• 1부터 N까지의 숫자를 오름차순으로 적어둠
• 적어둔 숫자 리스트에서 몇개 지워버림
• 주어진 숫자는 지워지고 남은 숫자들을 하나로 이은 숫자

/// 예시 (입력 : 234092 / 출력 : 20)
예상할 수 있는 원본 숫자 리스트 : 2 / 3 / 4 / 10 / 19 / 20
N의 최솟값 : 20

문제 풀이

• input : 입력 데이터를 쪼갠 배열 (각 원소를 '조각 숫자' 라고 부름)
• cur : 원본 숫자 배열 내 포함되는지 판별하는 대상 숫자
• 1씩 증가하는 cur 변수를 자릿수마다 쪼갠 배열을 탐색하며
  -> 각 자릿수 중 조각 숫자와 같은지 판별하고
  -> 같다면 인덱스 1 증가 후, 다음 반복으로 넘어가기 전 인덱스의 유효성 판단
• 가능한 가장 작은 숫자로 조각 숫자를 포함하는 값을 찾아나가는 방식

Swift를 활용한 풀이

let input = readLine()!.map{Int(String($0))!}
var cur = 0
var idx = 0

outer: while(true) {
    cur += 1
    let list = String(cur).map{Int(String($0))!}
    for s in list {
        if(input[idx] == s) { 
            idx += 1
            if(idx >= input.count) {
                print(cur)
                break outer
            }
        }
    }
}

Java를 활용한 풀이

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] input = br.readLine().toCharArray();
        int len = input.length;
        int cur = 0;
        int idx = 0;
        
        outer: while(true) {
            cur++;
            char[] cur_list = Integer.toString(cur).toCharArray();
            for(char c : cur_list) {
                if(c == input[idx]) {
                    idx++;
                    if(idx >= len) {
                        System.out.println(cur);
                        break outer;
                    }
                }
            }
        }
    }
}

문제 URL

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

문제 설명 요약

• n개의 네모 모양 벽돌 정보가 주어짐
• 주어진 정보는 '밑면의 넓이'와 '높이' 그리고 '무게'
• 구해야 하는 것은 주어진 벽돌들 중 높이가 최대가 되도록 쌓을 때, 쓰인 벽돌의 개수와 각 벽돌의 순서
  (단, 순서를 출력할 때에는 제일 위에 쌓인 벽돌의 순서부터 출력해야함)
• 벽돌을 쌓을 때의 규칙은 아래와 같음
  
  1. 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
  2. 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
  3. 벽돌들의 높이는 같을 수도 있다.
  4. 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
  5. 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다

문제 풀이

• 벽돌을 쌓을 수 있을지 없을지를 결정하는 요소가 '밑면의 넓이'와 '무게'이므로, 우선 둘 중에 하나를 기준으로 배열을 정렬해둠
• 정렬 이후 Dynamic Programming(동적 계획법)을 활용하여, 쌓을 수 있는지 없는지에 대한 판단을 요소별로 쪼개어 수행

Swift를 활용한 풀이

import Foundation

let n = Int(readLine()!)! // 벽돌의 개수
var origin:[[Int]] = [] // 벽돌들의 정보

// 벽돌 정보 입력 받기
for _ in 0..<n {
    origin.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}
// 벽돌의 밑면의 넓이를 기준으로 내림차순 정렬
var sorted_list = origin.sorted { $0[0] > $1[0] }

var dy:[Int] = [] // 높이합 최대 기록 배열
var hist:[Int:[Int]] = [:] // 각 항목 별 쌓을 수 있는 벽돌의 무게 정보 - [s:[w1, w2, ...]]

// 밑면이 가장 넓은 벽돌(맨 앞의 벽돌)에 대한 정보는 기본적으로 저장 (비교 대상이 없기 때문)
dy.append(sorted_list[0][1])
hist[sorted_list[0][0]] = [sorted_list[0][2]]

// 최대값에 관한 정보는 모두 밑면이 가장 넓은 벽돌(맨 앞의 벽돌)의 값으로 초기화
// (0과 빈 배열로 초기화해두면, 0번째 값을 고려하는 경우가 없어지기 때문)
var max_h_sum = dy[0] // 높이 합의 최대값
var max_h_list:[Int] = hist[sorted_list[0][0]]! // 높이 합이 최대인 경우의 높이값 요소 배열

// 2번째 벽돌 정보부터 살펴보면서, 이전 벽돌 중 자신이 위에 쌓일 수 있을지를 판단
for i in 1..<n {
    var max_h = 0
    var temp:[Int] = []
    for j in (0..<i).reversed() {
        // 이전 벽돌 중 자신보다 무게가 무거운 벽돌이면서, 높이의 합이 최대치인 경우의 정보를 임시 저장
        if (sorted_list[i][2] < sorted_list[j][2] && dy[j] > max_h) {
            max_h = dy[j]
            temp = hist[sorted_list[j][0]]!
        }
    }
    // 바로 위 for문에 의해 결정된 '높이의 합이 최대이면서, 무게가 자기자신보다 무거운 벽돌'의 정보를 기반으로 dy와 hist 초기화
    temp.append(sorted_list[i][2])
    hist[sorted_list[i][0]] = temp
    dy.append(max_h + sorted_list[i][1])

    // dy와 hist의 정보가 추가될 때마다, 각 높이의 합과 그것을 이루는 높이 요소값 배열을 갱신
    if (max_h_sum < dy[i]) {
        max_h_sum = dy[i]
        max_h_list = hist[sorted_list[i][0]]!
    }
}

// 결정된 최대 높이값의 요소 배열을 뒤집고 출력
// (무게를 기준으로 내림차순 된 배열에서 값을 찾았기때문)
max_h_list = max_h_list.reversed()
print(max_h_list.count)
for w in max_h_list {
    for i in 0..<origin.count {
        if(origin[i][2] == w) { print(i+1) }
    }
}