공부 기록

자리수가 가장 높은 알파벳에 순서대로 높은 값을 부여하면 되는 문제이다.

그렇지만 캐리 등이 있을 수 있다는 점을 염두해서 문제를 풀도록 해야한다.

이를 위해 예시 GCF + ACDEB의 경우

(100G+10C+1F)+(10000A+1000C+100D+10E+1B)로 변환하여

10000A+1010C+100D+100G+10E+1F+1B로 계산하고, 계수가 높은 순으로 높은 숫자를 부여해서 계산하도록 하면 된다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int alphabets[] = new int[26];

		for (int i = 0; i < n; i++) {
			String str = in.next();
			char ch[] = str.toCharArray();
			int index = 1;

			for (int j = ch.length - 1; j >= 0; j--) {
				alphabets[ch[j] - 'A'] += index;
				index *= 10;
			}
		}

		PriorityQueue<Alphabet> queue = new PriorityQueue<Alphabet>();
		for (int i = 0; i < alphabets.length; i++) {
			queue.add(new Alphabet(i, alphabets[i]));
		}

		int index = 9;
		int sum = 0;
		while (!queue.isEmpty()) {
			Alphabet alphabet = queue.poll();
			sum += alphabet.value * index;
			index--;
		}

		System.out.println(sum);
	}
}

class Alphabet implements Comparable {
	int index;
	int value;

	public Alphabet(int index, int value) {
		this.index = index;
		this.value = value;
	}

	@Override
	public int compareTo(Object o) {
		Alphabet alphabet = (Alphabet) o;
		return -Integer.compare(this.value, alphabet.value);
	}
}

문제 조건

• cpu에 태스크가 들어올건데 태스크의 순서는 맘대로 실행할 수 있다.
• 각 태스크는 한 시간 단위로 수행되고, 태스크를 실행하거나 idle 상태에 있을 수 있다.
• 두 개의 동일한 태스크를 실행하기 위한 사이에는 최소 n개의 태스크/idle이 있어야 한다.

흠... 일단은 그냥 가장 자주 나오는 글자를 배치하고 그 사이에 n개의 빈 칸을 둔 뒤에 다른 애들을 적절히 배치하면 될 것 같다고 생각했다.

class Solution {
	public int leastInterval(char[] tasks, int n) {
		int[] frequency = new int[26];
		for (int task : tasks) {
			frequency[task - 'A']++;
		}

		Arrays.sort(frequency);

		int maxFrequency = frequency[25];
		int betweenTime = (maxFrequency - 1) * n;

		int index = frequency.length - 2;
		while (index >= 0 && betweenTime > 0) {
			betweenTime -= Math.min(maxFrequency - 1, frequency[index]);
			index--;
		}
		betweenTime = Math.max(0, betweenTime);

		return betweenTime + tasks.length;
	}
}

문제 조건

• num 배열 원소는 음이 아닌 정수
• 배열의 마지막 요소까지 점프해서 무조건 도달 가능 => 0이 아닌 이상 1칸씩 가면 되니까
• 배열의 각 요소는 해당 위치에서 최대 점프 길이를 나타낸다.

class Solution {
	public int jump(int[] nums) {
		int n = nums.length;
		if (n < 2) {
			return 0;
		}

		int maxPosition = nums[0];
		int maxLength = nums[0];

		int jumps = 1;
		for (int i = 1; i < n; ++i) {
			if (maxLength < i) {
				jumps++;
				maxLength = maxPosition;
			}
			maxPosition = Math.max(maxPosition, nums[i] + i);
		}

		return jumps;
	}
}

문자열을 적절히 쪼갠 후 하나로 합칠 때, 사전상으로 가장 앞에 오는 단어를 구하는 문제이다.

한 문자내의 쪼갠 문자 순서는 바뀌면 안된다

먼저 아이디어는 각 단어를 가리키는 포인터가 각각 존재하며,

맨 앞부분만 서로 비교했을 때 가장 작은 값을 stringbuilder에 하나씩 붙인다.

처음에는 단순히 사전순, 길이순으로 정렬해서 풀었는데, 이 경우는 ABCCC, BACCC인 경우 ABABCCCCCC 예외케이스가 나온다.

이는 BAA, BA 테스트 케이스를 해결하기 위해 문자열의 길이를 함께 봤기 때문에 생긴 예외케이스이다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		List<String> string = new ArrayList<String>();
		int index[] = new int[n];
		int length[] = new int[n];

		PriorityQueue<Alphabet> queue = new PriorityQueue<Alphabet>();
		for (int i = 0; i < n; i++) {
			string.add(in.next());
		}
		string.sort(Comparator.comparing(String::length).reversed().thenComparing(String::compareTo));

		for (int i = 0; i < n; i++) {
			queue.add(new Alphabet(i, string.get(i).charAt(index[i])));
			length[i] = string.get(i).length();
		}

		StringBuilder sb = new StringBuilder("");
		while (!queue.isEmpty()) {
			Alphabet alphabet = queue.poll();

			sb.append(alphabet.ch);

			int nextIndex = alphabet.index;
			if (index[nextIndex] < length[nextIndex] - 1) {
				index[nextIndex]++;
				queue.add(new Alphabet(nextIndex, string.get(nextIndex).charAt(index[nextIndex])));
			}
		}
		System.out.println(sb.toString());
	}
}

class Alphabet implements Comparable<Alphabet> {
	int index;
	char ch;
	int length;

	public Alphabet(int index, char ch) {
		this.index = index;
		this.ch = ch;
	}

	@Override
	public int compareTo(Alphabet o) {
		if (ch == o.ch) {
			return Integer.compare(index, o.index);
		}
		return Character.compare(ch, o.ch);
	}

	@Override
	public String toString() {
		return "(" + index + ", " + ch + ")";
	}
}

그렇다면 문자열을 큐에 넣을때마다 정렬해야 한다는 소리인데

문자열 자체를 맨 앞 부분을 하나씩 제거해야하기 때문에,

연산을 할 때마다 새로운 객체를 반환하는 불변객체 String보다는 StringBuffer을 사용했다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		PriorityQueue<StringBuffer> queue = new PriorityQueue<StringBuffer>(new BufferComparator());

		for (int i = 0; i < n; i++) {
			queue.add(new StringBuffer(in.next()));
		}

		while (!queue.isEmpty()) {
			//System.out.println(queue);

			StringBuffer alphabet = queue.poll();

			System.out.print(alphabet.charAt(0));
			alphabet.deleteCharAt(0);

			if (alphabet.length() > 0) {
				queue.add(alphabet);
			}
			alphabet = null;
		}
		System.out.println();
	}
}

class BufferComparator implements Comparator<StringBuffer> {

	public int compare(StringBuffer s1, StringBuffer s2) {
		int min = Math.min(s1.length(), s2.length());
		for (int i = 0; i < min; i++) {
			if (s1.charAt(i) > s2.charAt(i)) {
				return 1;
			} else if (s1.charAt(i) < s2.charAt(i)) {
				return -1;
			}
		}
		return Integer.compare(s2.length(), s1.length());
	}
}

BufferComparator을 직접 구현해서 정렬해주도록 했다.

결과는 53%에서 시간초과..

결론적으로는 로직 자체는 같으나, 커스텀 Comparator을 사용하지 않고 기본 Comparable로 정렬하여 사용하는 방법이라면 통과가 된다.

문제 조건에서 공백은 없이 알파벳 대문자로만 구성되어 있다고 했기 때문에,

문자 마지막에 'a'를 붙여주면 (ASCII - \0: 0, a: 097, A: 065)

모든 대문자는 'a'보다 작기 때문에 커스텀 Comparator를 사용하지 않고 기본 Comparable을 사용하면서 같은 동작을 하도록 만들 수 있다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		PriorityQueue<StringBuffer> queue = new PriorityQueue<StringBuffer>();
		for (int i = 0; i < n; i++) {
			queue.add(new StringBuffer(in.next() + "a"));
		}

		while (!queue.isEmpty()) {
			StringBuffer alphabet = queue.poll();

			System.out.print(alphabet.charAt(0));
			alphabet.deleteCharAt(0);

			if (alphabet.length() > 1) {
				queue.add(alphabet);
			}
			alphabet = null;
		}
		System.out.println();
	}
}

이 문제에서 주의해야 하는 대표 테스트케이스는 아래와 같다

4 
CCCA 
CCCB 
CCCD 
CCCE

2
ABCCC
BACCC

2
BAA
BA

PriorityQueue의 정렬 방법

PriorityQueue 내부의 정렬은 아래와 같은 함수를 이용하여 정렬된다.

정렬 자체에 영향을 주는 가장 큰 요소는 정렬 알고리즘인데, 이는 머지 소트로 동일하다.

    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x, queue, comparator);
        else
            siftUpComparable(k, x, queue);
    }
    
    private static <T> void siftUpComparable(int k, T x, Object[] es) {
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = es[parent];
            if (key.compareTo((T) e) >= 0)
                break;
            es[k] = e;
            k = parent;
        }
        es[k] = key;
    }

    private static <T> void siftUpUsingComparator(
        int k, T x, Object[] es, Comparator<? super T> cmp) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = es[parent];
            if (cmp.compare(x, (T) e) >= 0)
                break;
            es[k] = e;
            k = parent;
        }
        es[k] = x;
    }

왠지는 모르겠지만.. 아래는 기본 Comparable과 custom Comparator이다.

어디서 차이가 발생했는지 시간날 때 compareTo 함수를 좀 더 까봐야겠다...

    int compareTo(AbstractStringBuilder another) { // StringBuffer::compareTo
        if (this == another) {
            return 0;
        }

        byte val1[] = value;
        byte val2[] = another.value;
        int count1 = this.count;
        int count2 = another.count;

        if (coder == another.coder) {
            return isLatin1() ? StringLatin1.compareTo(val1, val2, count1, count2)
                              : StringUTF16.compareTo(val1, val2, count1, count2);
        }
        return isLatin1() ? StringLatin1.compareToUTF16(val1, val2, count1, count2)
                          : StringUTF16.compareToLatin1(val1, val2, count1, count2);
    }
    
    class BufferComparator implements Comparator<StringBuffer> { // Custom BufferComparator

        public int compare(StringBuffer s1, StringBuffer s2) {
            int min = Math.min(s1.length(), s2.length());
            for (int i = 0; i < min; i++) {
                if (s1.charAt(i) > s2.charAt(i)) {
                    return 1;
                } else if (s1.charAt(i) < s2.charAt(i)) {
                    return -1;
                }
            }
            return Integer.compare(s2.length(), s1.length());
        }
    } 

문제 조건

레스토랑의 구조는 완전히 동그란 모양이고, 외벽의 총 둘레는 n(미터)이며, 외벽의 몇몇 지점은 취약한 지점들이 있다.

따라서 내부 공사 도중에 주기적으로 점검을 한다. 점검 시간을 1시간으로 제한된다.

친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하려고 한다.

편의상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타낸다.

친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동한다.

예제는 아래와 같고, 어디서든 출발하면서 특정 시간동안 많은 취약점을 찾도록 하면 되는 것 같다.

n = 12
weak = [1, 5, 6, 10]
dist = [1, 2, 3, 4]
=> answer = 2

일단 1 <= n <= 200, weak의 길이는 1 이상 15 이하, dist의 길이는 1 이상 8 이하이다.

수의 범위가 굉장히 작아서 완전탐색을 해도 될 것 같다고 생각했다.

문제 풀이 과정은 아래와 같다.

1. 일단 모든 경우의 수(순열)을 뽑는다.

2. 순열이 외벽 점검을 만족하는지 확인하고 인원수를 업데이트 해 준다.

• weak = [1, 5, 6, 10]이라면 [1, 5, 6, 10], [5, 6, 10, 13], [6, 10, 13, 17], [10, 13, 17, 18]의 외벽점검을 시작한다.
• 적은 수의 순열부터 구한 다음에 min 값이 업데이트 되면 그 뒤는 계산하지 않도록 한다.

import java.util.*;
class Solution {
	public static int min = Integer.MAX_VALUE;

	public int solution(int n, int[] weak, int[] dist) {
		boolean[] isVisited = new boolean[dist.length];
		int[] output = new int[dist.length];

		for (int i = 1; i <= n; i++) {
			permutation(dist, output, isVisited, 0, n, i, weak);
			if (min != Integer.MAX_VALUE) {
				break;
			}
		}

		if (min == Integer.MAX_VALUE) {
			min = -1;
		}
		return min;
	}

	public static void permutation(int[] dist, int[] output, boolean[] visited, int depth, int n, int r, int[] weak) {
		int length = dist.length;

		if (min < r) {
			return;
		}

		if (depth == r) {
			if (isPossible(output, n, r, weak)) {
				min = Math.min(min, r);
			}
			return;
		}

		for (int i = 0; i < length; i++) {
			if (visited[i] != true) {
				visited[i] = true;
				output[depth] = dist[i];
				permutation(dist, output, visited, depth + 1, n, r, weak);
				visited[i] = false;
			}
		}
	}

	public static boolean isPossible(int[] output, int n, int r, int[] weak) {
		if (min <= r) {
			return true;
		}

		int length = weak.length;
		for (int start = 0; start < length; start++) {
			int userIndex = 0;
			int before = weak[start];
			boolean possibleUnit = true;

			for (int i = start; i < start + length; i++) {

				int now = weak[i % length];
				if (i >= length) {
					now += n;
				}
				if (now - before > output[userIndex]) {
					userIndex++;
					before = now;
				}

				if (userIndex >= r) {
					possibleUnit = false;
					break;
				}
			}
			if (possibleUnit) {
				return true;
			}
		}
		return false;
	}
}

커플 (2N-2, 2N-1)가 인접해서 앉고 싶은데, 그렇지 못하다면 최소로 swap하여 인접하게 앉을 수 있도록 하는 문제이다.

커플은 (2N-2, 2N-1)으로 (0,1), (2,3), (4,5), ...이므로 x의 파트너는 x가 짝수인 경우 x+1, 홀수인 경우 x-1이다.

먼저 array를 0부터 2자리씩 보기 시작하면서 해당 파트너와 인접하면 넘어가고,

인접하지 않으면 짝은 옆으로 데려와서 앉힌다.

즉, 소파에 첫번째 앉아있는 사람은 고정시키고 두번째 사람만 옮김으로써 커플을 완성하도록 한다. 

시간복잡도는 O(N^2)이고 코드는 아래와 같다.

class Solution {
	public int minSwapsCouples(int[] row) {
		int ans = 0;

		for (int i = 0; i < row.length; i += 2) {
			int x = row[i];

			if (row[i + 1] == findPartner(x)) {
				continue;
			}

			ans++;

			for (int j = i + 1; j < row.length; ++j) {
				if (row[j] == findPartner(x)) {
					row[j] = row[i + 1];
					row[i + 1] = findPartner(x);
					break;
				}
			}
		}
		return ans;
	}

	public int findPartner(int x) {
		if (x % 2 == 0) {
			return x + 1;
		}
		return x - 1;
	}
}