1914 하노이 탑
📌문제 링크
https://www.acmicpc.net/problem/1914
💡 문제 풀이
하노이 탑에 n개의 블록이 있고 탑을 1번에서 3번으로 옮겨야 할 때,
1. 맨 아래에 있는 가장 큰 블록을 제외한 나머지 블록들을 2번으로 옮긴다.
2. 맨 아래 블록을 3번으로 옮긴다.
3. 2번에 있는 나머지 블록을 3번으로 옮긴다.
이런 방식으로 진행되므로 재귀함수로 구현했다.
함수의 인자를 from(출발하는 곳), between(중간 경유지), to(목적지), cnt(블록의 수)로 구성했다.
이제 이동 횟수를 구해보자.
n-1개를 옮기고, 나머지 한 개를 옮기고, 다시 n-1개를 옮기니 일반항은 다음과 같다.
hanoi(N) = hanoi(N-1)*2 + 1 (hanoi(1) = 1)
여기서 일반항을 도출한다면 다음과 같다.
출처 : https://mgyo.tistory.com/185
여기서 주의할점!! 입력의 최댓값 N=100이 들어올 때 2^100이 int형 범위를 넘어간다...
이거때문에 틀렸다ㅠㅠ 파이썬 쓸 때는 이런 거 신경 안썼었는데..
큰 수를 나타내야 할 때는 BigInteger를 써야한다고 한다
📋코드
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void hanoi(int from, int between, int to, int cnt) {
if (cnt == 1) {
System.out.println(from + " " + to);
} else {
hanoi(from, to, between, cnt-1);
hanoi(from, between, to, 1);
hanoi(between, from, to, cnt-1);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
BigInteger res = new BigInteger("2");
System.out.println(res.pow(n).subtract(new BigInteger("1")));
if (n <= 20) hanoi(1, 2, 3, n);
}
}
⏱ 시간 복잡도
N이 20 이하일 때 이동 횟수만큼 hanoi 함수를 호출한다. (2^n + 1)
따라서 시간 복잡도도 O(2^n)이다.
N이 20보다 클 때는 횟수 연산만 하면 되므로 O(1)이다.
10814 나이순 정렬
📌문제 링크
https://www.acmicpc.net/problem/10814
💡 문제 풀이
처음 문제를 봤을 때, String과 Int형을 같이 써야하니까 HashMap을 써아하나? 라는 생각을 했다. 하지만 가입 순서도 고려해야 돼서 index가 필요하니 배열로 구현해야겠다고 생각했다.
- String 2차원 배열로 나이, 이름을 모두 String으로 입력받는다.
- 나이를 기준으로 정렬하는 comparator를 구현한다. (lambda식을 사용했다.)
이 때, 나이가 같을 경우 이동하지 않기 때문에 자동적으로 가입 순서로(index 순서로) 정렬된다.- 출력한다.
나이를 String으로 받았는데, 어차피 문자열끼리도 대소비교가 되니까 처음엔 아래와 같이 구현했다.
Arrays.sort(members, (m1, m2) -> { return m1[0].compareTo(m2[0]); });그런데 틀렸다고 나와서 왜 그런가 찾아봤더니, 문자열로 비교할 경우 사전순으로 정렬되어 "10"이 "9"보다 앞서게 된다고 한다....
그래서 parseInt로 정수형으로 형변환하여 비교했다.
Arrays.sort(members, (m1, m2) -> { return Integer.parseInt(m1[0]) - Integer.parseInt(m2[0]); });📋코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[][] members = new String[n][2];
String[] tmp;
for (int i = 0; i < n; i++) {
tmp = br.readLine().split(" ");
members[i][0] = tmp[0];
members[i][1] = tmp[1];
}
Arrays.sort(members, (m1, m2) -> { return Integer.parseInt(m1[0]) - Integer.parseInt(m2[0]); });
for (String[] mem: members) {
System.out.printf("%s %s\n", mem[0], mem[1]);
}
}
}
⏱ 시간 복잡도
입출력에 O(N), 정렬 (Arrays.sort)에는 quick정렬이 사용되어 평균 O(NlogN)이 걸린다.
따라서 전체 시간복잡도는 평균 O(NlogN)이다.
