배열

[SWEA] 2819 - 격자판의 숫자 이어 붙이기

배열의 모든 원소에 대해 사방탐색을 6번 진행하는 것이다. dfs를 통해 구현하면 되는데, 한 번 방문한 원소도 다시 방문할 수 있으니 방문여부를 검사할 필요는 없다. 결과값의 중복을 제거하기 위해 hashSet을 사용하였다. 7개의 결과값을 담을 ans배열을 static으로 선언하여 depth가 1 증가할 때마다 ans[depth]에 수를 담았다. 모든 원소에 대해 dfs를 수행하고, ans배열의 0번 index에 초기값을 담아 진행한다. for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) { ans[0] = arr[i][j]; dfs(arr, i, j, 1); } dfs는 사방탐색으로 한다. 먼저 깊이가 7이 되면 결과값을 return한다. 그 다음 사..

[자료구조] 이진 트리의 구현, 순회 (자바/Java)

이진 트리를 각각 배열과 링크드 리스트로 구현하고 트리의 노드들을 전위순회, 중위순회, 후위순회하는 코드를 구현하였다. 1. 배열 1-1. 트리 구현 배열로 이진 트리를 구현할 때는 배열의 index를 통해 부모와 자식 노드를 확인할 수 있다. 루트 노드의 index를 1로 하고, 같은 층위의 노드들을 순서대로 배열에 삽입하면 부모 노드의 인덱스가 i일 때 자식 노드의 인덱스는 i*2, i*2+1이 된다. 전체 정점의 개수를 입력받고 그 다음 줄에 각 간선의 parent와 child 값을 입력받는다. 13 1 2 1 3 2 4 3 5 3 6 4 7 5 8 5 9 6 10 6 11 7 12 11 13 위 케이스에서 1 2는 부모가 1, 자식 노드가 2임을 의미한다. 이때 루트노드는 부모 노드가 없으니 첫 ..

[SWEA] 1873 - 상호의 배틀 필드 (자바/Java)

shoot을 할 때 각 방향을 정의하기 위해 HashMap을 활용하였다. 각 방향을 key로 하고, 방향에 따라 달라지는 dr과 dc를 길이 2의 배열에 담아 value로 지정하였다. HashMap dir = new HashMap(); // 각 방향의 dr dc dir.put('', new Integer[] { 0, 1 }); dir.put('^', new Integer[] { -1, 0 }); dir.put('v', new Integer[] { 1, 0 }); 그리고 입력받은 문자열을 char 하나씩 문자열 배열로 만들었다. StringTokenizer st = new StringTokenizer(br.readLine()); int H = Integer.parseInt(st.nextToken()); /..

[백준] 17276 배열 돌리기 (자바/Java)

문제 크기가 n x n인 2차원 정수 배열 X가 있다. (n은 홀수) X를 45° 의 배수만큼 시계방향 혹은 반시계방향으로 돌리려고 한다. X를 시계 방향으로 45° 돌리면 아래와 같은 연산이 동시에 X에 적용되어야 한다: X의 주 대각선을 ((1,1), (2,2), …, (n, n)) 가운데 열 ((n+1)/2 번째 열)로 옮긴다. X의 가운데 열을 X의 부 대각선으로 ((n, 1), (n-1, 2), …, (1, n)) 옮긴다. X의 부 대각선을 X의 가운데 행 ((n+1)/2번째 행)으로 옮긴다. X의 가운데 행을 X의 주 대각선으로 옮긴다. 위 네 가지 경우 모두 원소의 기존 순서는 유지 되어야 한다. X의 다른 원소의 위치는 변하지 않는다. 반시계 방향으로 45° 돌리는 경우도 위와 비슷하게 정..

[SWEA] 1954 - 달팽이 숫자 (자바/Java)

2차원 배열의 순회를 활용한 문제이다. while 문을 활용해서 해당 방향의 index를 채우고, array의 끝을 만나거나 이미 방문된 노드를 만났을 때는 방향을 바꾸어 주었다. 각 방향을 1~4로 두고 switch문으로 케이스를 정하였다. case 1: 오른쪽으로 이동: row는 그대로, col을 증가 case 2: 아래로 이동: col은 그대로, row를 증가 case 3: 왼쪽으로 이동: row는 그대로, col을 감소 case 4: 위로 이동: col은 그대로, row를 증가 그리고 1에서 더 나아갈 방향이 없으면 2로, 2에서 3으로 재귀적으로 snail함수를 수행하도록 하였다 그리고 함수를 실행하였을 때 이미 그 칸이 칠해져있다면, 모든 칸이 칠해진 경우이므로 return으로 종료조건을 주었..

[백준] 2567 - 색종이 2 (자바/Java)

문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 둘레의 길이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 네 장의 검은색 색종이를 과 같은 모양으로 붙였다면 검은색 영역의 둘레는 96 이 된다. 입력 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 ..

[SWEA] 1208 - Flattern (자바/Java) 배열, 우선순위 큐(힙)

처음에는 ArrayList를 매번 정렬하는 방법으로 풀었는데, 우선순위 큐를 이용하면 더 쉽게 풀릴 것 같아서 두 가지 방법을 모두 써봤다. ArrayList int N = sc.nextInt(); // 덤프 횟수 ArrayList box = new ArrayList(); for (int i = 0; i 0 && dis > 1) { box.set(0, box.get(0) + 1); box.set(size - 1, box.get(size - 1) - 1); Collections.sort(box); di..

[백준] 2564 - 경비원 (자바/Java)

문제 동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 경비차를 몰고 그 곳으로 달려가야 한다. 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다. 예를 들어 가로의 길이가 10, 세로의 길이가 5인 블록의 경계에 무인 경비를 의뢰한 3개의 상점이 있다고 하자. 과 같이 이들은 1, 2, 3으로 표시되어 있고, 동근이는 X로 표시한 위치에 있다. 1번 상점에서 호출이 들어 왔을 때 동근이가 블록을 시계방향으로 돌아 이동하면 이동 거리가 12가 된다. 반면 반시계방향으로 돌아 이동하면 이동 거리는 18이 된다. 따라서 동근이가 1번 상점으로 가는 최단 거리는 12가..

[SWEA] 4789 - 성공적인 공연 기획 (자바 / Java)

입력되는 string의 각 index는 0부터 시작해서 최소 index명 이상이 박수치고 있을 때 자신도 박수를 친다는 것을 뜻한다. 즉 string이 "110011" 일 때, 세 번째 0은 index가 2이고, 2명 이상 박수치고 있을 때 자신이 박수를 친다는 것이다. 이에 따라 문자열을 char 배열로 바꾼 후, 앞자리부터 박수를 치고 있는 사람의 수를 누적합하여 count 배열을 생성하였다. char[] people = sc.next().toCharArray(); int[] count = new int[people.length]; for (int i = 0; i < count.length; i++) { if (i == 0) count[i] = people[i] - '0'; else { count[i..

[SWEA] 1220 - Magnetic (자바/Java)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14hwZqABsCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이차원 배열의 같은 열에서, 1이 위에서, 2가 아래에서 만나는 경우의 수를 세면 된다. 이때 1이나 2가 중복되어도 교착 상태는 하나로 판단한다. 이를 체크하기 위해 같은 열에서 작은 값(위에 위치한 값)이 1인 경우 prev에 1을 저장하고, prev가 1이면서 2를 만날 때 교착 상태이므로 cnt를 하나씩 더해준다. 그리고 prev를 초기화해야 한다. 또한 한 열의 검사가 다 끝나면 prev를..