1. 배열의 숫자들 중복 제거해서 나타내기
- 단, 새로운 배열이나 set사용은 금지
- 중복 제거된 원수의 개수를 나타내는 변수 idx를 선언한다.
- nums배열에 새롭게 값을 넣을 때는 nums[idx++]을 꼭 후치로 넣어준다.
<hide/>
<hide/>
import java.util.*;
public class Practice1 {
public static void solution(int[] nums) {
int idx = 0; // 중복 제거한 데이터 개수
for(int num : nums) {
// 인덱스가 첫번째이거나 이전 숫자보다 커지는 경우
if (idx == 0 || num > nums[idx - 1]) {
nums[idx++] = num;
}
}
System.out.print("[" + idx + "]");
for(int i= 0; i < idx ; ++i){
System.out.print(nums[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
// Test code
solution(new int[] {1, 1, 2});
solution(new int[] {0, 0, 1, 1, 1, 2, 2, 3, 3, 4});
}
}Note) 실행 결과
2. 주어진 nums 배열에서 두 번 나타나는 모든 정수의 배열을 반환하는 프로그램을 작성하세요.
- nums 배열은 [1, n] 범위의 정수로 이루어져 있다.
- 각 정수는 한 번 또는 두 번 나타날 수 있다.
- 반환을 위한 메모리 공간 외에 추가 적인 배열 사용은 하지 않는다.
- 배열의 각 원소에 대해,
새로운 index라는 변수를 만들어서 대응하는 값의 원소의 부호를 바꿔준다.
원소를 보다가 음수가 나오면 전에 한 번 나온적이 있으므로 list에 add해준다.
<hide/>
import java.util.*;
public class Practice2 {
public static ArrayList<Integer> solution(int[] nums) {
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < nums.length; ++i){
int index = Math.abs(nums[i]) - 1; //절댓값으로 얻는다.
if(nums[index] < 0){ // 음수인 경우는 두번째 방문이므로
list.add(Math.abs(index + 1));
}
nums[index] = -nums[index];
}
return list;
}
public static void main(String[] args) {
// Test code
int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
System.out.println(solution(nums));
nums = new int[]{1, 1, 2};
System.out.println(solution(nums));
nums = new int[]{1, 3, 1, 3, 5, 5};
System.out.println(solution(nums));
}
}Note) 실행 결과
<hide/>
입력 출력
4, 3, 2, 7, 8, 2, 3, 1 2, 3
1, 1, 2 1
1, 3, 1, 3, 5, 5 1, 3, 5
?????????
3. 정렬된 정수형 배열 arr 이 주어졌을 때, 다음을 구하는 프로그램을 작성하세요.
- arr 과 함께 k 와 x 가 주어진다.
- k 는 개수, x 는 기준 값이다.
- x 와 절대 값 차이 기준으로 가까운 수를 k 개수 만큼 정렬된 순서로 출력하세요.
- 절대 값 차이가 같을 때는 숫자가 작은 것이 먼저 출력되도록 한다.
<hide/>
import java.util.*;
public class Practice3 {
public static void solution(int[] arr, int k, int x) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
// Integer: 차이값, ArrayList<Integer>: 해당하는 값들을 리스트로 이어준다.
for(int i = 0; i < arr.length; ++i){
int diff = Math.abs(x - arr[i]); // 절댓값
ArrayList<Integer> cur = map.get(diff);
if(cur == null){ // 차이값이 아직 없다면
map.put(diff, new ArrayList<>(Arrays.asList(arr[i])));
}else{
int idx = cur.size();
for(int j = 0; j < cur.size(); ++j){
if(cur.get(j) > arr[i]){
idx = j;
break;
}
}
cur.add(idx, arr[i]);
}
}
ArrayList<Integer> result = new ArrayList<>();
int cnt = 0;
while(map.size() > 0){
int minDiff = map.keySet().stream().min((a,b) -> a - b).get();
// 가장 작은 차이값,
ArrayList<Integer> cur = map.get(minDiff);
map.remove(minDiff);
while(cur.size() > 0){
result.add(cur.get(0));
cur.remove(0);
++cnt;
if(cnt == k){
break;
}
}
if(cnt == k){
break;
}
}
Collections.sort(result);
System.out.println(result);
}
public static void main(String[] args) {
// Test code
int[] arr = {1, 2, 3, 4, 5};
solution(arr, 4, 3);
arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
solution(arr, 5, 5);
arr = new int[]{2, 4};
solution(arr, 1, 3);
arr = new int[]{2, 4};
solution(arr, 3, 3);
}
}Note) 입출력 예시
<hide/>
입력 k x 출력
1, 2, 3, 4, 5 4 3 1, 2, 3, 4
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 5 5 3, 4, 5, 6, 7
2, 4 1 3 2
2, 4 3 3 2, 4
4. MxN 행렬 정보가 2차원 정수형 배열 matrix 에 주어지면, 나선형 모양으로 출력하는 프로그램을 작성하세요.
- rowEnd => rowStart 인 경우에는 if(rowEnd >= rowStart)문이 필요하다.
- colEnd => colStart: if(colEnd >= colStart)문이 필요하다.
<hide/>
import java.util.ArrayList;
public class Practice4 {
public static ArrayList<Integer> solution(int[][] matrix) {
if(matrix == null || matrix.length == 0){
return null;
}
ArrayList<Integer> result = new ArrayList<>();
int rowStart = 0;
int rowEnd = matrix.length - 1;
int colStart = 0;
int colEnd = matrix[0].length - 1;
while(rowStart <= rowEnd && colStart <= colEnd){
for(int i = colStart; i <= colEnd ; ++i){
result.add(matrix[rowStart][i]);
}
++rowStart;
for(int i = rowStart; i <= rowEnd; ++i){
result.add(matrix[i][colEnd]);
}
--colEnd;
if(rowStart <= rowEnd){
for(int i = colEnd; i >= colStart; --i ) {
result.add(matrix[rowEnd][i]);
}
}
--rowEnd;
if(colStart <= colEnd){
for(int i = rowEnd; i >= rowStart; --i){
result.add(matrix[i][colStart]);
}
}
++colStart;
}
return result;
}
public static void main(String[] args) {
// Test code
int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
System.out.println((solution(matrix)));
matrix = new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10 ,11 ,12}};
System.out.println((solution(matrix)));
}
}Note) 입출력 예시
<hide/>
입력 출력
{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}} 1, 2, 3, 6, 9, 8, 7, 4, 5
{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10 ,11 ,12}} 1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7
5. 벽 사이사이의 빈 공간에 담을 수 있는 물의 총량
- n개의 정수형 데이터가 height 배열에 주어졌다. height 배열의 각각의 원소는 아래 그림과 같이 각 벽에 대한 높이를 의미한다.
- 이와 같이 높이 값들이 주어졌을 때, 벽 사이사이의 빈 공간에 담을 수 있는 물의 총량을 출력하세요.
<hide/>
public class Practice5 {
public static int solution(int[] height) {
if(null == height || 0 == height.length ){
return 0;
}
int left = 0;
int right = height.length - 1;
int leftMax = 0;
int rightMax = 0;
int result = 0;
while(left < right){
if(height[left] < height[right]){ // 벽이 높아진 경우
if(height[left] >= leftMax){
leftMax = height[left];
}else{
result += leftMax - height[left];
}
++left;
}else{
if(height[right] >= rightMax){
rightMax = height[right];
}else{
result += rightMax - height[right];
}
--right;
}
}
return result;
}
public static void main(String[] args) {
// Test code
int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println(solution(height));
height = new int[]{4, 2, 0, 3, 2, 5};
System.out.println(solution(height));
}
}Note) 입출력 예시
<hide/>
입력 출력
0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 6
4, 2, 0, 3, 2, 5 9
'자료구조와 알고리듬 With Java > [zerobase] Algorithm' 카테고리의 다른 글
| Chapter 02. 선형 자료구조 (0) | 2022.05.30 |
|---|---|
| Chapter 01. 기초 수학 [zerobase] (0) | 2022.05.22 |
| [Java 핵심 복습] (0) | 2022.05.13 |
| Part 01. 연습문제 풀이 2 [zerobase] (0) | 2022.05.11 |
| Part.01연습문제 풀이 [zerobase] (0) | 2022.05.11 |