230622 - 자료구조 공부(ArrayList, LinkedList) + 알고리즘 시험

오늘 느낀점/배운점

기능을 쓰긴 하지만 왜 쓰는지 몰랐던 나의 지난 날들..(물론 지금도) 그래서 컴퓨터 공학쪽도 공부해야 함을 느꼈다.

먼저 자료구조가 무엇인지에 대해 알아보고, java 프로그래밍에서 제공하는 컬렉션에 대해서도 알게 되었다.

Collection의 종류에는 List, Set, Queue, Map이 있는데 그중에서 List의 ArrayList와 LinkedList가 무엇인지 그리고 그 차이점이 무엇인지에 대하여 알게되었다. 아래 사진은 공부하며 적은 내용들이다. (인증용임)

 

간단하게 Array와 ArrayList의 차이점은 각각 정적배열, 동적배열 이라는 것!

+배열은 primitive type(int, byte, char 등)과 object 모두를 담을 수 있지만, arrayList는 object element만 담을 수 있다.

 

 

ArrayList와 LinkedList

ArrayList는 데이터들이 순서대로 쭉 늘어선 배열의 형식을 취하고 있어서

삽입 시에 사이즈를 늘려주는 연산, 삭제 시 빈 인덱스를 채워주는 연산이 필요하기 때문에 이러한 일이 빈번하게 일어나는 프로세스의 경우 치명적이다.

 

LinkedList는 데이터가 자료의 주소 값으로 서로 연결되어 있는 구조라서

ArrayList 처럼 뒤로 밀거나 채우는 작업 없이 주소만 서로 연결시켜 주면 되기 때문에 추가/삭제가 ArrayList보다 빠르고 용이하다.

 

하지만, ArrayList에서는 무작위 접근이 가능하지만, LinkedList에서는 순차접근만 가능한 단방향성을 가지고 있기 때문에 인덱스를 이용하여 자료를 검색하는 애플리케이션에는 적합하지 않다. 그리고 데이터도 이것 저곳에 저장되어 있어서 노드들을 접근하는데 보다 긴 지연 시간이 소모된다. 

 

ArrayList와 비교한 LinkedList의 장/단점

시험문제!!!

헤헤헤헤헤 기분이 좋다. 그동안 풀었던 문제들을 짬뽕하여 만든 것으로 초큼.. 어려웠다.

 

하. 자연수 뒤집어 더하기 (1점)

자연수 n의 각 자리 숫자를 뒤집은 순서로 더해 출력하는 수식을 리턴해주세요. 예를들어 n이 12345이면 "5+4+3+2+1=15" 라는 문자열을 리턴합니다.

 

풀이

public class Main {
       public String solution(int n) {
              String answer = "";
              String num = Integer.toString(n);

먼저 int형으로 들어온 숫자를 String의 형태로 바꿔 num이라는 변수에 넣어준다.

              String[] digits = num.split("");

다음 num에 저장된 문자열을 하나씩 쪼개서 String 배열인 digits 에 담아준다.

              int[] h = new int[digits.length]; 
              int sum = 0;

              for (int i = digits.length-1; i >= 0 ; i--) {
                    h[(digits.length-1)-i] = Integer.parseInt(digits[i]);

                    sum += h[(digits.length-1)-i];
               }

int 배열인 h라는 변수에 digits의 맨 뒤의 인덱스에 위치한 요소들부터 차례대로 넣어준다.

그리고 int sum에는 h의 요소들을 모두 더한 값을 넣는다.

              for (int i = 0; i < h.length; i++) {
                   answer += h[i];

                   if (i != h.length - 1) { 
                       answer += "+";
                   }
               }

다음 h의 0번째 요소부터 넣어주는데 조건이 하나 있다. 만약 i가 h.length-1과 같지 않으면 if문 안을 수행해 준다.

(index가 0부터 시작해서 h의 마지막 요소의 index번호는 h.length-1 이 된다.)

0번째 요소~h.length-2요소 까지는 if문을 만족하므로 숫자 뒤에 "+"가 붙게된다. 

h의 마지막 요소가 answer에 들어갔을때는 if문을 만족하지 않으므로 for문을 빠져나간다.

              answer += "=" + sum;
              return answer;
}

그럼 answr에 마지막으로 "=" + sum 을 넣어주고 return한다.

public static void main(String[] args) {
        Main method = new Main();
        System.out.println(method.solution(718253));
        }
}

718253을 넣으면 ' 3+5+2+8+1+7 = 26 ' 이라는 문자열을 리턴한다.

 

 

 

 

중. Making Triangle (2점)

첫째 줄에 정수 n이 주어진다. (0≤n≤100)

n줄 만큼 ‘*’로 이루어진 삼각형을 출력한다.

최상단의 별은 1개이며, 모든 줄의 별의 갯수는 홀수이다.

(그리고 예시를 보면 별은 가운데에 위치함.)

 

풀이

먼저 문제를 어떻게 풀어야할지 감이 잡히지 않아서 직접 별을 그려보았다. ㅋㅋㅋㅋ

일단 int star는 별의 줄의 갯수를 말하고,

*의 수가 star번째 줄까지 일정한 규칙을 가지며 커가는 걸 알 수 있다. -> (2n-1)

 n은 1 ~ star번째까지의 수가 차례로 들어간다.   

 

다음은 별이 가운데에 위치하게 출력을 해야하는데

가운데의 위치는 맨 아래 star번째의 별의 개수 (= 가장 많은 별을 가진) 에서 비교할 현재 줄의 별의 개수를 뺀다음

2로 나누어 주면 *앞의 공백의 길이를 얻어낼 수 있다.

import java.util.ArrayList;
import java.util.List;

public class Main {
        public void solution(int star) {

        List<Integer> newArr = new ArrayList<>();
        for (int i = 0; i < star; i++) {
               newArr.add(2 * (i + 1) - 1);
        }

먼저 별의 개수를 담은 배열을 만들어준다.

1. star는 무조건 홀수이고, 어떤 수가 들어올지 모르기 때문에 ArrayList로 동적배열 newArr를 만들어 주었다. 

2. for문으로 안의 조건을 만족할때 (2*(i+1)-1)을 계산해서 newArr에 넣어주었다.

   index가 0으로 시작하기 때문에 i도 0부터 시작해서  (2*(i+1)-1) 이러한 식이 나왔다.

        int maxNumOfStars = newArr.get(newArr.size() - 1); 

이제 공백의 길이를 구할 것이다. maxNumOfStars 에 newArr의 마지막 인덱스 요소를 가져와 넣어준다.

마지막 인덱스의 요소는 당연히 별의 개수가 가장 많을테니!

        for (int i = 0; i < newArr.size(); i++) {
              int numOfStars = newArr.get(i); 
              int numOfSpaces = (maxNumOfStars - numOfStars) / 2; 

다음 for문으로 첫번째 줄부터 돈다. numOfStars 안에 현재 줄의 별의 개수를 

numOfSpaces 안에는 (가장 많은 별의 개수 - 현재 줄의 별의 개수) / 2 를 하여 공백의 길이를 넣어준다.

             String spaces = " ".repeat(numOfSpaces);
             String stars = "*".repeat(numOfStars);
             System.out.println(spaces + stars);
       }
}

다음 numOfSpaces 만큼 먼저 " " 공백을 입력하고, 다음 numOfStars 만큼 현재 줄의 별의 개수를 입력하여 출력한다.

println 을 통해 자동으로 줄바꿈이 되어 star번째까지 별이 그려진다.

public static void main(String[] args) {
       Main method = new Main();
       int star = 9;
       method.solution(star);
       }
}

star에 9를 입력했을때 예상과 같이 잘 출력됨을 볼 수 있다.

 

 

 

 

상. 양옆앞뒤 큰 수 찾기 (3점)

5x5 2차원 배열이 주어질 때 어떤 원소가 상하좌우에 있는 원소보다 클 때 해당 위치에 * 을 표시하는 프로그램을 작성하세요. 경계선에 있는 수는 상하좌우 중 존재하는 원소만을 비교합니다.

조건 1: 결과는 하나의 문자열이며, 2차원 배열의 각 배열의 요소들에 해당하는 문자는 길이 1의 공백으로 구분된다.

조건2: 결과에서 배열간의 구분은 줄바꿈(개행문자)으로 한다.

조건3: 비교할 원소가 존재하지 않는 경우 0으로 간주한다

입출력예시

 

풀이

 

처음에 이문제를 보고 쓰고 있지도 않던 안경을 벗어 큰 눈으로 화면을 쳐다봤다. 뭔말이야 이게?

일단 저 입력 부분을 봤을때는 상하좌우 비교하는게 가능한가? 싶었다. 그래서 또 직접 그려보았다.

{7,4,6,5,9}
{6,1,3,4,5}
{4,8,5,6,9}
{1,3,0,6,4}
{6,4,8,1,7}   //arr의 입력값으로 이 숫자들이 들어온다고 해서 이걸 썼다.

여기서 3열 2행의 8과 같이 상하좌우의 숫자들과 비교해서 가장크면 *을 표시해주는데, (index기준으로 [2][1])

문제는 1행 1열 의 7과 같은 요소는 상,좌의 숫자들이 없다. 조건에서는 비교할 원소가 존재하지 않는 경우 0으로 간주하라고 하였다.

public class Main {
       public void solution(int[][] arr1) {
               int[][] answer = new int[5][5];

크기가 5*5인 answer라는 배열을 만든다 여기에 *로 바꾼 숫자들을 집어 넣을거다.

               for (int i = 0; i < 5; i++) {
                     for (int j = 0; j < 5; j++) {
                            int check = arr1[i][j];

2중 for문으로 모든 요소들을 야무지게 돌며 요소 하나하나씩 차근~차근 check에 넣어주어 상하좌우의 숫자와 비교해준다.

                            int top = (i > 0) ? arr1[i - 1][j] : 0; 
                            int bottom = (i < 4) ? arr1[i + 1][j] : 0; 
                            int left = (j > 0) ? arr1[i][j - 1] : 0; 
                            int right = (j < 4) ? arr1[i][j + 1] : 0; 

1. top 을 구할 때 check의 i가 0이면 위에 비교할 요소가 없다. 따라서 i가 0보다 클때는 check의 바로 위에 위치하고 j(행)의 위치는 같은 요소의 숫자를 저장한다. 

2. bottom도 같은 원리로 i가 4보다 작았을 때를 만족하면 check의 바로 아래에 위치하고 j의 위치는 같은 요소의 숫자를 저장한다.

3. 이렇게 상하좌우에 위치한 요소들을 구하여 각각 top, bottom, left, right 변수 안에 값을 저장. 

                            if (check > top && check > bottom && check > left && check > right) {
                                 answer[i][j] = 1;
                             }

                      }
               }

4. 이 상하좌우의 값보다 check의 값이 큰 경우를 '모두' 만족하면 answer[i][j] 에 임의의 숫자 1을 입력한다. 그럼 answer에는 상하좌우의 값들 보다 큰 숫자들만 '1'로 저장된 상태가 된다. (나머지는 디폴트값.)

 

이제 요구한 대로 출력해준다.

               for (int i = 0; i < 5; i++) {
                     for (int j = 0; j < 5; j++) {
                            if (answer[i][j] == 1) {
                                System.out.print("* ");
                            } else {
                                System.out.print(arr1[i][j] + " ");
                            }
                     }

answer의 [i][j]가 1일 때 "* "을,

아닐 때는 arr1[i][j]의 원래 요소들을 문자열로 출력한다. arr1[i][j] + " " 이런 식으로 쓰면 자동으로 형변환 된다.

                     System.out.println();

다음 println(); 으로 i가 증가할때마다 (열이 바뀔때마다) 줄바꿈한다.

                }
         }

public static void main(String[] args) {
      Main method = new Main();
      int[][] arr1 = {{7,4,6,5,9}, {6,1,3,4,5}, {4,8,5,6,9}, {1,3,0,6,4}, {6,4,8,1,7}};

      method.solution(arr1);
      }
}

위의 값이 들어왔을때

이렇게 잘 출력됨을 확인