소문난 칠공주

골드3

문제 이해

• 5x5의 그리드로 주어지는 25개 글자에 대해
• 7개로 구성된 조합을 만드는데
  • 1. 7개의 글자는 연결되어 있어야 한다
  • 2. S가 일곱 글자 중 4개 이상이어야 한다
• 제약 조건을 만족시키는 모든 조합의 수를 출력한다

입력의 크기가 무조건 25로 고정되어 있기 때문에 시간복잡도 면에서 널널하다고 할 수 있다.

해결방안 고안

1. 좌표 (y, x)와 글자 (S or Y)를 담을 Node 클래스를 만든다

입력을 그대로 받는 것이 아닌, 좌표 값과 글자를 필드로 갖는 노드 클래스의 집합으로 받는다. 조합을 생성하는 메서드에서 .get(int idx) 메서드를 활용할 일이 잦을 것 같아 ArrayList<Node>로 구현했다.

static class Node {
	int y, x;
    char val;
	Node(int y, int x, char val) {
		this.y = y;
		this.x = x;
		this.val = val;
    }

	@Override
	public String toString() {
		return "(" + y + ","+x+")=> "+val+"\t";
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + y;
		result = prime * result + x;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) return true;
		if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
		Node other = (Node) obj;
		if (y != other.y) return false;
		if (x != other.x) return false;
		return true;
	}
}

equals와 hashCode는 다음 섹션에서 7개의 노드가 연결되었는지의 조건을 만족시키는지 확인하는 작업을 위해 구현해뒀다.

이 조건은 글자의 값과 무관하게 좌표 기준으로 연결되어 있으면 만족되기 때문에 equals와 hashCode 메서드 또한 글자에 대한 의존성을 제거했다.

2. 노드 7개로 구성된 조합을 만든다

 private static void makeCombinations(ArrayList<Node> students, int depth, int start, boolean[] visited, Node[] result) {
	if (depth == 7) {
		if (satisfiesCondition(result)) count++;
        return;
    }
    for (int i = start; i < students.size(); i++) {
        if (!visited[i]) {
			result[depth] = students.get(i);
			visited[i] = true;
			makeCombinations(students, depth+1, i+1, visited, result);
			visited[i] = false;
		}
	}
}

3. S가 4개 이상인지 확인한다

private static boolean satisfiesCondition(Node[] result) {
	int sCount = 0;
	for (int i = 0; i < 7; i++) {
		if (result[i].val == 'S') sCount++;
	}
	if (sCount < 4) return false;
    return isConnected(result);
}

우선 조합의 글자 중 4개 이상이 S인지 확인한 다음, 조합이 연결되어 있는지 여부를 확인하는 메서드를 호출한다

4. 조합의 노드가 연결되어 있는지 확인한다

private static boolean isConnected(Node[] result) {
	int[] dy = {-1, 1, 0, 0};
    int[] dx = {0, 0, -1, 1};

    Set<Node> nodes = new HashSet<>(List.of(result));
    ArrayDeque<Node> queue = new ArrayDeque<>();
    Set<Node> visited = new HashSet<>();
    
    queue.addLast(result[0]);
    visited.add(result[0]);

    while (!stack.isEmpty()) {
        Node curr = queue.pollFirst();
        int y = curr.y;
        int x = curr.x;

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            Node n = new Node(ny, nx, '0');
			if (nodes.contains(n) && !visited.contains(n)) {
				queue.addLast(n);
				visited.add(n);
			}
		}
	}
	return visited.size() == nodes.size();
}

조합이 연결되어 있는지 여부는 BFS로 확인했다.

ArrayDeque<Node> queue는 BFS를 위한 큐로 사용했고, Set<Node> visited는 방문된 노드를 기록하기 위해 사용했다.

int[] dy와 int[] dx에 대한 루프로 사방탐색을 진행하고, 조합의 노드와 일치 (좌표 값에 대해)한다면 방문 노드 목록에 추가한다.

BFS가 끝나고 나서는 조합의 모든 노드가 방문되었는지, 각 자료구조의 크기를 비교하여 리턴한다

5. 만족시킬 경우 조합의 수를 업데이트한다

3번과 4번의 조건이 모두 만족된 조합에 대해서는 static int count 변수를 증가시킨다.

풀이 코드

소문난 칠공주 백준#1941 풀이 코드

삽질

연결되어 있는지 여부를 확인하는 코드에서 조금 헷갈려서 시간을 낭비했던게 조금 아쉬움으로 남는다. 하지만 대체로 푸는 재미가 있는 문제였다.

---

암호 만들기 #1759

골드5

문제 이해

• C 개의 알파벳이 주어졌을 때
• 다음 조건들을 만족 시키는 조합을 모두 구해라
  • L개의 문자로 구성된다
  • 최소 1개의 모음 (a, e, i, o, u)를 포함한다
  • 최수 2개의 자음을 포함한다
  • 알파벳 오름차순으로 정렬되어 있다

알파벳 오름차순으로 정렬되어 있다는 것은 순서가 다른 순열을 고려할 필요가 없다는 의미로 조합이라 결정했다. 또한, L과 C의 최댓값이 15로 작기 때문에 조합을 해보기 딱 좋은 크기라 판단했다.

해결방안 고안

1. 알파벳을 정렬한다.

Arrays.sort(characters);
makeCombinations(characters, new char[L], 0, 0,L, new boolean[C]);

알파벳을 정렬해야지 오름차순 정렬된 암호만 생성한다는 조건을 만족시킬 수 있다.

2. C개에 대하여 L개 고르는 조합을 생성한다

private static void makeCombinations(char[] characters, char[] result, int depth, int start, int L, boolean[] visited) {
	if (depth==L) {
		if (satisfiesCondition(result)) sb.append(arrToString(result)).append("\n");
        return;
    }
	for (int i = start; i < characters.length; i++) {
		if (!visited[i]) {
			visited[i] = true;
			result[depth] = characters[i];
			makeCombinations(characters, result, depth + 1, i+1, L, visited);
			visited[i] = false;
		}
	}
}

조합 메서드의 인자로 int start를 포함해서 매번 고르는 알파벳 다음 순서부터 알파벳을 고를 수 있다. 이렇게 자연스레 오름차순 조건을 만족시킬 수 있다.

2. (조건 1) 최소 1개의 모음을 포함하는지 확인한다, (조건 2) 최소 2개의 자음을 포함하는지 확인한다

private static boolean satisfiesCondition(char[] result) {
	int vowels = 0, consonants = 0;
	for (char c : result) {
		switch (c) {
			case 'a':
			case 'e':
			case 'i':
			case 'o': 
			case 'u':
				vowels++;
				break;
			default:
				consonants++;
		}
	}
	return vowels >= 1 && consonants >= 2;
}

풀이 코드

암호 만들기 백준#1759

삽질

사실 어려운 문제는 아니였는데 조건을 제대로 안 읽어서 실수했다

---

트럭 백준#13335

실버1

문제 이해

• 길이가 w이고, 최대 하중이 L인 다리를 n개의 트럭이 건너고자 한다.
• 다리 위의 트럭들의 무게 총합은 항상 최대 하중 이하여야 한다
• 움직이는 각 트럭은 1초에 1만큼 전진한다
• 트럭은 순서대로 건너야 한다

해결방안 고안

1. 큐 사용

순서를 변경할 수 없으니까 인덱스가 중요하지 않다. 트럭들은 그저 앞 순서부터 가능하면 다리 건너기를 시작하면 된다

이 힌트로 큐를 생각해낼 수 있다. 트럭을 모두 큐에 담아두고, 다리를 건너는 트럭들은 큐에서 제거하면 된다. 트럭을 담은 큐가 비었으면 트럭들이 모두 건넜음을 의미한다.

2. 다리를 건넜는지 확인하기

그럼 트럭이 건넜는지는 어떻게 확인할지 고민하다가, key 기준으로 오름차순 정렬되는 TreeMap에 담기로 결정했다.

다리에 입장한 시간을 key로, 트럭 무게를 value로 갖는 pair를 사용해서 입장하고 지난 시간이 다리의 길이보다 같거나 긴지 확인하면 된다. true면 TreeMap에서 해당 entry를 제거하고, 다리 위 무게에서도 해당 트럭의 무게를 빼서 업데이트한다

3. 다음 트럭 입장 가능한지 확인하기

현재 무게 총합에 다음 트럭의 무게를 더해도 최대 하중을 넘어가지 않으면 트럭이 입장할 수 있다.

입장은 트럭 큐에서 해당 트럭을 pollFirst하고, 시간을 관리하는 TreeMap에 입장을 (time, weight)으로 기록하면 된다

풀이 코드

트럭 백준#13335 코드

배운 점

최대한 자료구조를 활용하는 접근을 우선시해야겠다고 다시금 생각했다. 확실히 자료구조를 사용하는 것이 오류도 잘 발생하지 않는다.

그리고 하나의 루프 안에 처리 순서를 더 신중하게 고민해야겠다. 이 문제에서는 다리를 다 건넌 트럭이 나감과 동시에 새로운 트럭이 들어올 수 있었다. 로직을 구현할 때 루프 내에서 새로운 트럭이 들어올 수 있는지 여부부터 확인하고 나서 트럭이 다리를 건넜는지 확인하는 실수를 저질렀다.

---

추억의 2048게임 SWEA#6109

D4

문제 이해

• NxN 그리드에 0 또는 2^k 값의 숫자들이 주어진다
• right, left, up, down을 입력 받으면 그리드의 셀들이 그 방향으로 밀린다
  • 어떤 타일이 밀리는 방향에 다른 타일이 있고, 두 타일에 적힌 숫자 같다면 두 타일은 합쳐져 두 숫자의 합이 적힌 하나의 타일이 된다
  • 벽에서 가까운 숫자들부터 합쳐진다
  • 이미 합쳐진 셀은 또 합쳐질 수 없다
  • 원래 0이였거나, 셀들이 밀어지면서 빈 셀들은 이동 방향 반대쪽 끝에 0 타일로 존재한다

해결방안 고안

1. 그리드를 rotate해서 무조건 한쪽 방향으로 밀리도록 구현했다

나는 왼쪽으로 밀리는 상황만 구현하고자 했다. 그래서 나머지 (오른쪽, 윗쪽, 아랫쪽) 밀리는 상황은 rotate90 함수로 해결했다

이동 방향이 up이면 rotate90을 3번해서 왼쪽으로 미는 상황을 구현한 다음 rotate90을 1번 해서 방향을 원상복구 시켰다.

2. 왼쪽으로 밀리는 상황을 구현한다

2-1. 0을 제거한다

이 문제를 풀 수 있었던 가장 결정적인 요인은 0 을 제거한 것이다. 처음에는 투포인터를 풀려고 했는데, 그리드에서 값이 변경 되면서 포인터 2개까지 관리하려고 하니 머릿속에서 복잡해졌다.

그래서 NxN 그리드를 N개의 ArrayDeque (row)로 생각하고 풀었다. 이 row에는 0 이 아닌 숫자만 포함시켰다.

0 을 제외시킨 이유는 다음과 같다

1. 같은 숫자인지 확인해서 셀을 합치는 로직에서 현재 숫자의 다음 숫자가 0이면, 현재 숫자와 다다음 숫자를 비교한다. 즉, 0이 아닌 숫자를 만날 때까지 비교하니 0이 필요하지 않다

2. 숫자가 합쳐지지 않더라도 우선 0의 오른쪽으로 모두 밀린다.

그래서 0 셀들은 결국 연산이 모두 끝난 마지막에 빈 셀들의 값을 채워주기 용으로 추가해주면 된다

2-2. ArrayDeque의 요소들을 순차적으로 방문해 합쳐질 수 있는지 확인한다

우선 ArrayDeque의 숫자는 모두 0이 아니기 때문에 자신의 다음 숫자와 같지 않으면 그냥 결과 ArrayDeque에 그대로 들어간다.

나는 왼쪽으로 밀리는 상황을 구현했기 때문에 row의 앞부터 순회하면서 합쳐질 수 있는지 확인한다. 합쳐질 수 없다면 ArrayDeque의 끝에 추가하고, 합쳐질 수 있다면 두 숫자의 합을 ArrayDeque에 추가하면 된다.

2-3. 연산 과정 이후 빈 셀 처리하기

합쳐질 수 있는지 여부를 모두 확인해서 결과 ArrayDeque을 완성했다면 그리드 해당 row에 값을 하나씩 넣어주면 된다.

2-1에서 0 을 제외시켰기 때문에 이 ArrayDeque이 그리드의 컬럼 수보다 작을 수 있지만, 어차피 0으로 초기화되어 있기 때문에 상관 쓸 필요 없다.

풀이 코드

추억의 2048게임 SWEA

배운 점

이 문제도 자료구조를 잘 활용하는 것이 얼마나 중요한지 깨달은 풀이였다.

투포인터를 써서 배열을 그대로 사용한 풀이도 있으나, 나는 내장된 자료구조를 사용한 풀이가 로직이나 컴파일/런타임 오류를 최소화한다고 생각한다.

---

단어 맞추기 #9081

실버1

문제 이해

• 주어진 단어의 알파벳으로 만들 수 있는 단어들을 사전 순으로 정렬했을 때, 주어진 단어의 다음 순서를 구한다
• 만약 주어진 단어가 마지막 순서면 그대로 출력한다

해결방안 고안

Next Permutation 정석 문제다. 총 3단계를 거쳐 수행한다.

1. Next Permutation은 배열의 마지막부터 앞쪽으로 순회하며 사전순에 부합하는 첫 글자를 찾는다. 이를 pivot이라 부른다.

사전순 정렬을 가정하면 123456789의 직후 순서는 123456798이다. 가장 마지막 요소들부터 스왑하는 것을 확인할 수 있다.

2. 유효한 pivot을 찾았다면 다시 뒷쪽부터 순회하며 이 pivot과 스왑할, pivot의 값보다 큰 가장 오른쪽의 요소를 찾아야 한다.

123456798의 다음 순서는 123456879다. 123456798의 pivot은 가장 오른쪽의, arr[i]와 arr[i+1]가 사전순으로 정렬되어 있는 7이다. successor는 pivot보다 큰 값 중 가장 오른쪽에 있는 8이다. 이 둘을 스왑하면 123456897이다.

3. 마지막으로, pivot 인덱스 다음값부터 reverse를 수행한다

2에서 123456897 까지 구했는데, 이 때 pivot은 7, successor는 8이였다. pivot 다음 값인 9부터 reverse하면 123456879을 얻을 수 있다.

풀이 코드

단어 맞추기 백준#9081

배운 점

처음에 뭣도 모르고 조합으로 풀었다가 시간 초과가 났었다. Next Permutation을 공부하고 나니까 얼마나 비효율적인 풀이 방법으로 접근하고 있었던지 깨달았다.

---