IT Docs

문제 링크 : https://www.acmicpc.net/problem/16926

처음 시도에는 배열의 외각을 돌리는 거 말고는 해결하지 못하였다.

그래서 배열 돌리기의 기초가 되는 백준 달팽이 문제를 풀면서 기초를 다지고 다시 풀었다.

문제를 해결하는 원리를 이해하여 풀었고 어느 정도 힌트를 기억하고 있어서 문제를 푸는데 수월하였다.

이 문제가 어렵게 느껴진다면 달팽이 문제를 풀고 다시 도전하기 바란다.

• nkt-docs.tistory.com/17

배열 돌리기 1의 소스를 아래와 같이 공유한다.

public class 배열돌리기1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] str = br.readLine().split(" ");
		
		int n = Integer.parseInt(str[0]);
		int m = Integer.parseInt(str[1]);
		int t = Integer.parseInt(str[2]);
		
		int[][] map = new int[n][m];
		
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int min = Math.min(n, m);
		int[] dx = {0, 1, 0, -1};
		int[] dy = {1, 0, -1, 0};

		for(int z = 0; z < t; z++) {
			for(int i = 0; i < min/2; i++) {
				int x = i;
				int y = i;
				int temp = map[x][y];
				int idx = 0;
				
				while(idx < 4) {
					int xx = x + dx[idx], yy = y + dy[idx];
					
					if(xx < i || yy < i || xx > n-i-1 || yy > m-i-1) {
						idx++;
					}else {
						map[x][y] = map[xx][yy];
						x = xx;
						y = yy;
					}
				}
				map[x+1][y] = temp;
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				sb.append(map[i][j]).append(" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}
}

문제 링크 : https://www.acmicpc.net/problem/1913

달팽이 문제는 백준 배열 돌리기 1, 배열 돌리기 문제를 먼저 접하게 되어 풀게 된 문제이다.
배열 돌리기 문제가 너무 어려웠다..
배열 돌리기 유형의 문제를 처음 본 사람이 과연 누군가의 도움 없이 문제를 풀 수 있을까라는 의문을 가지게 되었고 누군가는 단박에 문제를 풀었을 거라는 생각에 나 자신에게 화가 나고 무기력해졌다.
그래도 어쩌겠나 모르면 부딪혀서 경험하고 배우는 수밖에 없다.
그래서 배열 돌리기의 기초 문제인 달팽이 문제를 풀게 되었다.

내가 느낀 감정을 표출하지 않는다면 성장할 수 없다는 생각에 서론이 길었다.

처음 문제를 접했을 때 index가 정사각형의 각 꼭짓점이 되는 부분에 도달했을 때 조건문을 주어 방향을 전환하였다.
하지만 조건문은 특정 영역인 각 꼭짓점인 부분만 동작하도록 되어있어 정사각형의 외각만 숫자를 카운팅 하게 되었다.
그 뒤로는 안쪽의 배열을 어떻게 채워나가야 할지 고민하다 포기하고 사방 탐색을 변형해서 구현하면 된다는 힌트를 얻어 문제 다시 풀었다.

사방 탐색은 나의 위치에서 상, 우, 하, 좌를 탐색하는 구현 방법이어서 이걸 변형해서 인덱스의 끝부분이나 0을 만난다면 방향을 전환하고 달팽이 모양을 만들기 위해 이미 값이 채워져 있다면(map[x][y] != 0) 방향을 전환하도록 구현하였다.

아래와 같이 소스를 공유한다.

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int t = sc.nextInt();
		
		int[][] map = new int[n][n];
		
		int[] dx = {1, 0, -1, 0};
		int[] dy = {0, 1, 0, -1};
		
		int cnt = n*n;

		for(int i = 0; i <= n/2; i++) {
			int x = i;
			int y = i;
			int idx = 0;
			
            // 사방 탐색이 시작위치보다 한 칸더 앞서 있기 때문에 시작 위치의 값 삽입
			map[i][i] = cnt--;
			
			while(idx < 4) {
				
				int xx = x + dx[idx], yy = y + dy[idx];

				// 정사각형의 외각에 도달했다면 방향 전환
				if(xx >= n || yy >= n || xx < 0 || yy < 0) {
					idx++;
                // 이미 값이 채워져 있다면 방향 전환
				}else if(map[xx][yy] != 0) {
					idx++;
				}else {
					map[xx][yy] = cnt--;
					x = xx;
					y = yy;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		int x = 0, y = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				int val = map[i][j];
				if(map[i][j] == t) {
					x = i;
					y = j;
				}
                // IDE에서 디버깅시 한눈에 보기 위한 formatting
				// sb.append(String.valueOf(val).length() == 1 ? "0" + val:val).append(" ");
                sb.append(val).append(" ");
			}
			sb.append("\n");
		}
		
		sb.append(x+1).append(" ").append(y+1);
		
		System.out.println(sb.toString());
	}

문제 링크 : https://www.acmicpc.net/problem/7569

백준 7576 토마토 문제를 풀고 난 후에 시도한 문제라서 쉬울 거라 생각하고 문제를 접근했다.

7576 토마토는 2차원 문제라면 7569 토마토는 3차원 문제였다.

알고 있는 유형의 문제라서 그런지 너무 쉽게 생각하여 입력 방식에 대해 잘못 구현했다.

첫 시도는 틀렸습니다를 받았다. 문제를 다시 정독한 후 입력 방식을 바꾸고 문제를 해결했다.

구현에 대해서는 어렵지 않았지만 문제를 파악하는데 실수가 있었다.

알고 있는 유형의 문제라도 빠른 해결을 위해 꼼꼼히 읽어보자!!

아래와 같이 구현 소스를 공유합니다.

public class 토마토 {
	public static class Node {
		int x, y, h, s;
		Node(int x, int y, int h, int s) {
			this.x = x;
			this.y = y;
			this.h = h;
			this.s = s;
		}
	}
	public static int X, Y, H, cnt;
	public static int[][][] arr;
	public static boolean[][][] visit;
	public static Queue<Node> que = new LinkedList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] str = br.readLine().split(" ");
		
		Y = Integer.parseInt(str[0]);
		X = Integer.parseInt(str[1]);
		H = Integer.parseInt(str[2]);
		
		arr = new int[X][Y][H];
		visit = new boolean[X][Y][H];
		
		boolean isSuccessed = true;
		
		for (int f = 0; f < H; f++) {
			for (int i = 0; i < X; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < Y; j++) {
					int v = Integer.parseInt(st.nextToken());
					if(v == 0) isSuccessed = false;
					if(v == 1) {
						que.add(new Node(i, j, f, 0));
						visit[i][j][f] = true;
					}
					arr[i][j][f] = v;
				}
			}
		}
		
		if(isSuccessed) {
			System.out.println("0");
		}else {
			bfs();
			
			boolean isCompleted = true;
			
			for (int f = 0; f < H; f++) {
				for (int i = 0; i < X; i++) {
					for (int j = 0; j < Y; j++) {
						int v = arr[i][j][f];
						if(v == 0) isCompleted = false;
					}
				}
			}
			
			if(isCompleted) {
				System.out.println(cnt-1);
			}else {
				System.out.println("-1");
			}
			
		}
	}
	
	public static void bfs() {
		int[] dx = {0, -1, 0, 1, 0, 0};
		int[] dy = {-1, 0, 1, 0, 0, 0};
		int[] dh = {0, 0, 0, 0, -1, 1};
		
		while(!que.isEmpty()) {
			int size = que.size();
			cnt++;
			for (int i = 0; i < size; i++) {				
				Node node = que.poll();
				
				for (int j = 0; j < 6; j++) {
					int xx = node.x + dx[j], yy = node.y + dy[j], hh = node.h + dh[j];
					if(xx < X && yy < Y && hh < H && xx >= 0 && yy >= 0 && hh >= 0) {
						if(!visit[xx][yy][hh] && arr[xx][yy][hh] == 0) {
							visit[xx][yy][hh] = true;
							arr[xx][yy][hh] = node.s + 1;
							que.add(new Node(xx, yy, hh, node.s + 1));
						}
					}
				}
			}
		}
 	}
 }

문제 링크 : https://www.acmicpc.net/problem/5052

처음 전화번호 목록 문제를 접했을 때 이중 포문을 이용하여 시간 초과가 발생했다.

어떤 방법이 있을까 하고 고민할 때 스터디원이 Trie 자료구조를 사용하면 풀 수 있다고 힌트를 주었다.

하지만 Trie 자료구조를 모르고 있었기에 학습하여 문제를 해결하였고 Trie 자료구조를 이용하지 않더라도 풀 수 있는 방법이 있길래 Trie 자료구조를 사용하지 않는 방법으로 문제를 풀어보았다.

아래와 같이 소스를 공유한다.

Trie 자료구조를 이용한 구현

public class 전화번호목록 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for (int e = 0; e < T; e++) {
			int ca = Integer.parseInt(br.readLine());
			List<String> list = new ArrayList<>();
			Trie t = new Trie();
			
			for (int i = 0; i < ca; i++) {
				String word = br.readLine();
				list.add(word);
				t.insert(word);
			}
			
			boolean is = false;
			
			for(String k : list) {
				if(t.contains(k)) {
					is = true;
					break;
				}
			}
			
			sb.append((is == true) ? "NO":"YES").append("\n");
		}
		
        bw.write(sb.toString());
        bw.flush();
        bw.close();
	}
}

public class Trie {
	private TrieNode rootNode;
	
	public Trie() {
		this.rootNode = new TrieNode();
	}
	
	public void insert(String word) {
		TrieNode root = this.rootNode;
		
		for (int i = 0; i < word.length(); i++) {
			root = root.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
		}
		root.setIsLastChar(true);
	}
	
	public boolean contains(String word) {
		TrieNode temp = this.rootNode;
		
		for (int i = 0; i < word.length(); i++) {
			char ch = word.charAt(i);
			TrieNode node = temp.getChildNodes().get(ch);
			
			if(node == null) return false;
			
			temp = node;
		}
		
		if(temp.isLastChar()) {
			if(temp.getChildNodes().isEmpty()) {
				return false;
			}
		}
		
		return true;
	}
	
	public void delete(String word) {
		delete(this.rootNode, word, 0);
	}
	
	public void delete(TrieNode node, String word, int idx) {
		char ch = word.charAt(idx);
		
		if(!node.getChildNodes().containsKey(ch)) throw new Error(word + " : 존재하지 않습니다.");
		
		TrieNode child = node.getChildNodes().get(ch);
		idx++;
		
		if(idx == word.length()) {
			if(!child.isLastChar()) throw new Error(word + " : 존재하지 않습니다.");
			
			child.setIsLastChar(false);
			
			if(child.getChildNodes().isEmpty()) node.getChildNodes().remove(ch);
		}else {
			delete(child, word, idx);
			
			if(!child.isLastChar() && child.getChildNodes().isEmpty()) node.getChildNodes().remove(ch);
		}
	}
	
	public boolean isRootEmpty() {
		return this.rootNode.getChildNodes().isEmpty();
	}
}

public class TrieNode {
	private Map<Character, TrieNode> childNodes = new HashMap<>();
	private boolean isLastChar;
	
	Map<Character, TrieNode> getChildNodes() {
		return this.childNodes;
	}
	
	boolean isLastChar() {
		return this.isLastChar;
	}
	
	void setIsLastChar(boolean is) {
		this.isLastChar = is;
	}
}

Trie 자료구조는 트리 형식으로 문자열을 찾는 자료구조이다.

Trie 자료구조를 이용하지 않은 구현

public class 전화번호목록 {
	public static Comparator<String> compare = new Comparator<>() {

		@Override
		public int compare(String o1, String o2) {
			return o1.compareTo(o2);
		}
		
	};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for (int e = 0; e < T; e++) {
			int c = Integer.parseInt(br.readLine());
			
			List<String> list = new ArrayList<>();
			
			for (int i = 0; i < c; i++) {
				list.add(br.readLine());
			}
			
			Collections.sort(list, compare);
			boolean is = false;
			for (int i = 1; i < c; i++) {
				if(list.get(i).startsWith(list.get(i-1))) {
					is = true;
					break;
				}
			}
			
			System.out.println((is == true) ? "NO":"YES");
		}
	}
}

주어지는 문자들을 정렬하고 startsWith 함수를 이용하여 비교한다.

문제를 푸는 방식이 다양하여 한 가지 문제를 풀더라도 여러 방법으로 풀어 다양한 접근 방식을 습득하려고 노력중이다.

참고 자료

• Trie 자료 구조 : the-dev.tistory.com/3

• blue-boy.tistory.com/189