• 데이터를 감싼 노드(Node) 가 서로 연결되어 있는 구조
• 각 노드는 데이터와 다음 노드를 가리키는 주소(Next) 로 이루어져 있음

Linked List의 특징

• 데이터들이 노드로 구성되어 있음 → 바로 뒷 노드만 알고 있고 건너 건너에는 어떤 데이터가 있는지 모름

• 메모리의 유연함 → 크기 제한이 없고 늘리고 줄이고가 자유로움

• 데이터 삽입/삭제 용이함 → 물리적인 이동 없이 주소만 바꿔주면 됨 (O(1))

• 조회 속도가 느림 → 처음부터(Head) 하나하나 확인하며 가야 함 (O(N))

💡배열과 LinkedList 비교

LinkedList 선언 방법

import java.util.LinkedList;

//1. 선언
LinkedList<String> list = new LinkedList<>();

//2. 값 추가
list.add("Java");
list.add("Spring");
list.add(1, "Boot"); // 중간에 삽입 (인덱스 1번)

//3. 값 삭제
list.remove(1); // 인덱스로 삭제
list.remove("Java");

//4. 값 조회
System.out.println(list.get(0));

💡단순 연결 리스트(Singly Linked List)

단순 연결 리스트는 위에서 말한 연결 리스트와 동일한 특징을 가지고 있다

💡이중 연결 리스트(Doubly Linked List)

• 각 노드가 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 갖는 구조

이중 연결 리스트의 특징

• 양방향 탐색 → 앞(Next)으로도 갈 수 있고 뒤(Prev)로도 이동이 가능하여 단순 연결 리스트보다 탐색이 유연

• 효율적인 검색과 삭제 → 양쪽 방향에서 삽입과 삭제가 가능

• 메모리 사용이 많다 → 이전 노드의 주소를 추가로 저장해야 하기 때문에 단순 연결 리스트와 달리 메모리를 더 차지 함

💡원형 연결 리스트(Circular Linked List)

• 마지막 노드의 포인터가 NULL이 아닌 첫 번째 노드를 가리키는 형태를 갖는 구조 → 마지막 노드의 다음 노드는 첫 번째 노드 → 첫 번째 노드의 이전 노드는 마지막 노드

백준 2566 - 최댓값

1. 문제 분석

문제 이해

9 X 9 배열에 있는 81개의 자연수에서 최대값을 찾고, 그 값의 위치를 찾는 문제이다

풀이 방법

• 최댓값이 나타날 때 마다 그 행과 열 갱신

  for(int i = 0; i < 9; i++) {
    for(int j = 0; j < 9; j++) {
        if(max < arr[i][j]) {
            max = arr[i][j];
            row = i;
            col = j;    
        }
    }
  }

2. 코드 구현

import java.io.*;
import java.util.*;

public class No_2566 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int arr[][] = new int[9][9];

        //1. 배열 채워넣기
        for(int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 9; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int max = 0;
        int row = 0;
        int col = 0;

        //2. 최댓값 찾기
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(max < arr[i][j]) {
                    max = arr[i][j];
                    row = i;
                    col = j;

                }
            }
        }
        System.out.println(max);
        System.out.println((row + 1) + " " + (col + 1));
    }
}

백준 10811 - 바구니 뒤집기

1. 문제 분석

문제 이해

1 ~ N번까지의 번호를 가진 바구니가 있다 M번의 바구니의 순서를 역순으로 만들 것이다

M번의 역순을 다 한 후, 바구니 번호를 왼쪽 부터 출력하는 문제 이다.

바구니의 개수 N = 5 역순의 개수 M = 4

1 2 3 4 5의 바구니가 있을 때

• (1, 2) 수행하면 -> 2 1 3 4 5
• (3, 4) 수행하면 -> 2 1 4 3 5
• (1, 4) 수행하면 -> 3 4 1 2 5
• (2, 2) 수행하면 -> 3 4 1 2 5 이런식으로 풀어가는 것이다

풀이 방법

• 바구니 번호 배열 저장

  for(int i = 0; i < N; i++) {
    arr[i] = i + 1;
  }

• 투 포인터 알고리즘 사용으로 역순으로 표현

  while(front < end) {
    int temp = arr[end];
    arr[end] = arr[front];
    arr[front] = temp;
  
    front++;
    end--;
  }

💡 투 포인터는 양쪽 끝에서 시작해서 서로 마주 보는 방향으로 좁혀 오는 알고리즘

front는 오른쪽으로 이동 end는 왼쪽으로 이동하면서 역순으로 표현하는 것

2. 코드 구현

import java.io.*;
import java.util.*;

public class No_10811 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int arr[] = new int[N];

        //1. 배열 저장
        for(int i = 0; i < N; i++) {
            arr[i] = i + 1;
        }

        //2. 역순 부분 입력
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int front = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;


            //3. 역순으로 표현 - 투 포인터 사용
            while(front < end) {
                int temp = arr[end];
                arr[end] = arr[front];
                arr[front] = temp;

                front++;
                end--;
            }
        }

        //4. 마지막으로 저장된 배열 출력
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

• 데이터들이 순서대로 메모리에 연속으로 저장되는 것 (ex. 배열)
• 각 데이터들은 다음 데이터와 연결되어 있고 각 데이터는 인덱스를 통해 접근이 가능

💡 리스트 (ArrayList)

• 컬렉션 프레임워크의 List의 인터페이스를 사용하여 구현한 구현체

순차 리스트 종류에는 ArrayList, LinkedList, Vector 등이 있다

List<자료형> list = new ArrayList<>();

객체를 생성할 때, 데이터 타입은 제너릭 타입의 매개변수로 사용 객체 자료형에는 어떤 것이 들어갈까??

객체 자료형 종류

1. Integer - 정수 값을 저장하는 타입
2. String - 문자열 값을 저장하는 타입
3. Double - 실수 값을 저장하는 타입
4. Boolean - 논리 값(True/False)을 저장하는 타입
5. Object - 모든 객체 타입을 저장할 수 있는 타입

ArrayList의 특징

• 동적 배열(Array) → 일반 배열과는 달리 자동으로 크기를 조절 할 수 있음

• 조회(get) 속도가 매우 빠름 → 인덱스를 알면 O(1)의 속도로 한 번에 데이터를 찾아감

• 데이터 추가/삭제가 느림 (특히 중간에 삽입 / 삭제할 때) → 중간에 데이터가 삽입되거나 삭제되면, 그 뒤의 모든 데이터를 한 칸씩 밀거나 당기는 작업이 필요

ArrayList 선언 방법

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

List<String> fruits = new ArrayList<>();
fruits.add("사과");
fruits.add("바나나");
fruits.add("딸기");

String secondFruit = fruits.get(1);

System.out.println(fruits); // [사과, 바나나, 딸기]
System.out.println(secondFruit); // 바나나

배열과 ArrayList 비교

사실 배열이랑 ArrayList는 큰 차이는 없다 💡단지 배열 크기 늘리기, 데이터 복사하기 작업을 ArrayList가 대신해주는 것이다 코딩 테스트를 할 떄 크기가 정해져 있다면 배열을 사용하는 것이 조금 더 빠르다

• 덱(Deque)은 스택과 큐의 기능을 모두 가진 자료구조이며, 양쪽 끝에서 삽입과 삭제가 가능하다
• 선입선출과, 후입선출의 특성을 가진다

덱의 동작 과정

데이터 추가

• 새로운 데이터가 Front(앞) 또는 Rear(뒤) 양쪽 어디서든 들어갈 수 있음

rear & front

• 큐와 위치는 같지만, 입구와 출구의 역할이 고정되지 않음

데이터 꺼내기

• Front(앞) 또는 Rear(뒤) 양쪽 어디서든 데이터를 꺼낼 수 있음

• 데이터 추가 : offerFirst() / offerLast()
  • offerFirst() - 덱의 맨 앞에 데이터를 추가
  • offerLast() - 덱의 맨 뒤에 데이터를 추가

• 데이터 꺼내기 : pollFirst() / pollLast()
  • pollFirst() - 덱의 맨 앞에서 데이터를 제거하고 반환 / 덱이 비어 있으면 null 반환
  • pollLast() - 덱의 맨 뒤에서 데이터를 제거하고 반환 / 덱이 비어 있으면 null 반환

• 데이터 확인하기 : peekFirst() / peekLast() - 데이터를 삭제하지 않음
  • peekFirst() - 덱의 맨 앞에서 데이터를 반환 / 덱이 비어 있으면 null 반환
  • peekLast() - 덱의 맨 뒤에서 데이터를 반환 / 덱이 비어 있으면 null 반환

💡 덱은 큐의 상위 호환으로 알고 있으면 쉽게 이해할 수 있다

• 데이터를 추가할 때 add()
• 데이터를 삭제할 때 remove() 사용해도 되지만 선언하는 것에 따라 다르다

• ArrayDeque 나 LinkedList 로 만들었다면 용량 제한이 없어서 에러가 발생하지 않지만 크기가 고정된 덱있다면 에러가 발생하기 때문에 offer(), poll(), peek()를 사용하는 게 좋다

덱 예시

Deque<자료형> deque = new LinkedList<>();

// 덱의 데이터 추가
deque.offerFirst("Apple");
deque.offerFirst("Banana");
deque.offerLast("Orange");
deque.offerLast("Grape");

// 덱의 데이터 꺼내기 - 첫번째 데이터 제거(Banana 삭제)
deque.pollFirst();  

덱 사용 예시

• 회문 판별 - 앞, 뒤에서 읽었을 때 동일한 문자열을 검사할 때 사용

덱 장단점

• 장점
  • 양쪽 끝에서 삽입과 삭제가 가능

• 단점
  • 메모리 사용이 큼

• 선형 구조의 형태이며 먼저 들어온 데이터가 먼저 나가는 자료구조이며 선입선출(FIFO, First-In-First-Out)의 특성을 가진다

큐의 동작 과정

Enqueue : 데이터 추가

• 새로운 데이터가 큐의 입구로 들어가는 과정
• rear의 위치는 다음 데이터가 삽입될 위치로 이동

rear & front : 입구와 출구

• rear : 큐의 맨 뒤 / 데이터가 들어오는(추가되는) 곳
• front : 큐의 맨 앞 / 데이터가 나가는(삭제되는) 곳

Dequeue : 데이터 꺼내기

• 맨 앞에 있는 데이터만 큐의 출구로 나갈 수 있음
• front의 위치는 다음 데이터가 추출될 위치로 이동

• 데이터 추가 : add() vs offer()
  • add() - 큐가 꽉 차서 못 넣으면 IllegalStateException 에러 발생
  • offer() - 큐가 꽉 차면 false 반환 (실무나 코딩테스트에서는 에러가 안터지는 offer 자주 사용)

• 데이터 꺼내기 : remove() vs poll()
  • remove() - 큐가 비어있는데 꺼내라고 하면 NoSuchElementException 에러 발생
  • poll() - 큐의 맨 앞 데이터를 제거 하고 반환 / 큐가 비어있으면 null 반환

• 데이터 확인하기 : element() vs peek()
  • element() - 큐가 비어있으면 에러 발생
  • peek() - 큐가 비어있으면 null 반환 (데이터가 삭제되지 않음)

• 모든 데이터 제거 - clear()

큐 예시

Queue<자료형> queue = new LinkedList<>();

// 큐의 데이터 추가
queue.offer("Apple");
queue.offer("Orange");
queue.offer("Banana");

// 큐의 데이터 꺼내기 - 첫번째 데이터 제거(Apple 삭제)
queue.poll();

큐 사용 에시

• 먼저 온 순서대로 업무를 처리할 때
• BFS(너비 우선 탐색) - 인접한 노드를 우선으로 방문해야 하는 경우

큐 장단점

• 장점

  • 데이터의 순서가 중요한 작업에 적합

• 단점

  • 큐의 크기가 고정되어 있으면 데이터가 가득 차면 더 이상 삽입이 불가능

백준 21918 - 전구

1. 문제 분석

문제 이해

전구의 상태를 주어진 명령어를 다 수행한 결과 전구는 어떤 상태인지 알아내는 문제이다.

전구의 상태는 0(꺼진거), 1(켜진거) 2가지가 있다. 명령어의 종류는 4가지가 있다.

• 1번 명령어
  • [i, x] - i 번째 전구의 상태를 x로 변경

• 2번 명령어
  • [l, r] - l번째부터 r번째까지의 전구의 상태를 변경(0 -> 1, 1 -> 0)

• 3번 명령어
  • [l, r] - l번째부터 r번째까지의 전구를 끔

• 4번 명령어
  • [l, r] - l번째부터 r번째까지의 전구를 킴

풀이방법

• 전구의 상태를 저장하는 배열

  int[] state = new int[N];
  
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            state[i] = Integer.parseInt(st.nextToken());
        }

• 명령어 수행

  if(a == 1) { // 1번 명령어
    state[b - 1] = c;
  }
  

if(a == 2) { // 2번 명령어 for(int j = b; j <= c; j++) { if(state[j - 1] == 0) { state[j - 1] = 1; } else { state[j - 1] = 0; } } }

if(a == 3) { // 3번 명령어 for(int j = b; j <= c; j++) { state[j - 1] = 0; } }

if(a == 4) { // 4번 명령어 for(int j = b; j <= c; j++) { state[j - 1] = 1; } }

* 바뀐 전구의 상태를 출력
```java
for(int i = 0; i < state.length; i++) {
            System.out.print(state[i] + " ");
        }

2. 코드 구현

import java.io.*;
import java.util.*;

public class No_21918 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] state = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            state[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            if(a == 1) {
                state[b - 1] = c;
            }

            if(a == 2) {
                for(int j = b; j <= c; j++) {
                    if(state[j - 1] == 0) {
                        state[j - 1] = 1;
                    } else {
                        state[j - 1] = 0;
                    }
                }
            }

            if(a == 3) {
                for(int j = b; j <= c; j++) {
                    state[j - 1] = 0;
                }
            }

            if(a == 4) {
                for(int j = b; j <= c; j++) {
                    state[j - 1] = 1;
                }
            }
        }

        for(int i = 0; i < state.length; i++) {
            System.out.print(state[i] + " ");
        }
    }
}

백준 14467 - 소가 길을 건너간 이유1

1. 문제 분석

문제 이해

소들이 길을 건너간 횟수를 구하는 문제이다 소의 번호와 위치(0 또는 1)가 주어진다 같은 소가 위치가 바뀔 때 마다 카운트를 1씩 증가해야함

입력

첫 줄에 관찰 횟수 N이 주어짐 N은 100 이하의 양의 정수 다음 N줄부터는 한 줄에 하나씩 관찰 결과(소의 번호와 위치 0, 1로 이루어짐)

풀이 방법

• 데이터 저장용 배열

  //1. 소 번호, 위치 2차원 배열에 저장
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            records[i][0] = Integer.parseInt(st.nextToken());
            records[i][1] = Integer.parseInt(st.nextToken());
        }

• 소의 위치 기록용 배열

  //2. 소의 현재 위치 배열
        int[] cowPos = new int[11];
        Arrays.fill(cowPos, -1); //아직 확인 되지 않은 소는 -1로 초기화

• 저장된 데이터 순회하면서 확인

  for(int i = 0 ; i < N; i++) {
            int cowNum = records[i][0];
            int location = records[i][1];
  
            //처음 보는 소라면 위치 저장
            if(cowPos[cowNum] == -1) {
                cowPos[cowNum] = location;
            } 
  
            // 전에 봤던 소인데 위치가 다르다면? 위치 갱신
            else if(cowPos[cowNum] != location) {
                count++;
                cowPos[cowNum] = location;
            }
        }

2. 코드 구현

package Bronze;

import java.io.*;
import java.util.*;

public class No_14467 { //소가 길을 건너간 이유1

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[][] records = new int[N][2];

        //1. 소 번호, 위치 2차원 배열에 저장
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            records[i][0] = Integer.parseInt(st.nextToken());
            records[i][1] = Integer.parseInt(st.nextToken());
        }

        //2. 소의 현재 위치 배열
        int[] cowPos = new int[11];
        Arrays.fill(cowPos, -1); //아직 확인 되지 않은 소는 -1로 초기화

        int count = 0;

        for(int i = 0 ; i < N; i++) {
            int cowNum = records[i][0];
            int location = records[i][1];

            //처음 보는 소라면 위치 저장
            if(cowPos[cowNum] == -1) {
                cowPos[cowNum] = location;
            } 

            // 전에 봤던 소인데 위치가 다르다면? 위치 갱신
            else if(cowPos[cowNum] != location) {
                count++;
                cowPos[cowNum] = location;
            }
        }
        System.out.println(count);
    }
}

문제를 풀고 나서 보니까 꼭 2차원 배열을 안써도 되는 것을 알았다 입력 받자마자 바로 소의 위치 배열과 비교해서 처리하면 메모리를 더 아깔 수 있을 것 같다

백준 1316 - 그룹 단어 체커

1. 문제 분석

문제 이해

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우를 말한다 예를 들면 aabbbcccc는 a,b,c가 모두 연속해서 나타나기 떄문에 그룹 단어이지만, aabba는 a가 떨어져서 나타나기 때문에 그룹 단어가 아니다

단어 N개를 입력 받아서 그룹 단어의 개수를 출력하자

입력

첫째 줄에 단어의 개수 N, N은 100보다 작거나 같은 자연수 둘째 줄에 N개 만큼의 단어가 들어옴, 단어는 소문자로만 되어있고 중복되지 않는다, 길이는 최대 100

풀이 방법

이 문제를 풀기 위해선 한번 나온 문자가 연속되지 않고 다른 문자가 나온 뒤에 또 나오면 그룹단어가 아니다 라는 개념이 있으면 된다

자 위에 했지만 다시 한 번 예시를 들어보자 aaabbcc -> 그룹 단어 (같은 문자끼리 뭉쳐 있다) ccaazzddc -> 그룹 단어가 아님 (c는 맨 압에 나왔는데, 중간에 a,z,d가 나오고 다시 나왔다)

코드에 확인 해야할 것은

1. 이전 문자와 다음 문자가 다른가?
2. 만약 다르다면 다음 문자가 이전에 나온 적이 있는가?

두 조건이 참이라면 해당 단어는 그룹 단어가 아니라서 개수에서 제외

2. 코드 구현

import java.io.*;

public class No_1316 { //그룹 단어 체커

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int count = 0;

        for(int i = 0; i < N; i++) {
            String str = br.readLine();
            boolean arr[] = new boolean[26];
            boolean check = true;

            arr[str.charAt(0) - 'a'] = true;  //첫 글자 왔었다

            for(int j = 0; j < str.length() - 1; j++) {
                int pre = str.charAt(j);
                int next = str.charAt(j + 1);

                //전 과 후가 다를 때
                if(pre != next) {
                    if(arr[next - 'a'] == true) { //뒷 글자가 이미 나왔었던 경우
                        check = false;
                        break;
                    }
                    arr[next - 'a'] = true; // 처음 나온 글자면 왔다고 표시
                } 
            }
            if(check == true) count++;
        }
        System.out.println(count);
    }
}

문제 분석

토마토처럼 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나 낱말을 회문이라고 한다 단어를 입력 받아 회문이면 1, 아니면 0 출력

입력

• 첫 줄에는 테스트 케이스 수 T
• 단어의 길이는 3이상 10이하

출력

• 단어를 입력 받아 회문이면 1, 아니면 0 출력

코드 구현

import java.io.*;
import java.util.*;

public class No_1989 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++) {
            String str = br.readLine();
            int answer = 0;

            int len = str.length();

            for(int j = 0; j < len / 2; j++) {
                char front = str.charAt(j);
                char end = str.charAt(len - 1 - j);

                if(front == end) {
                    answer = 1;
                    break;
                }
            }
            System.out.println("#" + (i+1) + " " + answer);
        }
    }
}

💡문제 풀이

• 방법 1

  • 회문이면 앞에서 읽을 때와 뒤에서 읽을 때가 같아야함
  • 맨 앞과 맨 뒤 글자가 같은지 하나씩 확인하면서 중앙으로 오는 방법

• 방법 2

  • 문자열을 통째로 뒤집어서 원본 문자열과 뒤집은 문자열 비교하는 방법

문제 분석

• 패턴에서 반복되는 부분을 마디라고 부른다
• 문자열을 입력 받아 마디의 길이를 출력하자

입력

• 첫 줄에는 테스트 케이스의 개수 T
• 문자열의 길이는 30, 마디의 최대 길이는 10

출력

• 마디의 길이를 출력

코드 구현

import java.io.*;

public class No_2007 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++) {
            String str = br.readLine();
            int answer = 0;

            for(int j = 1; j <= 10; j++) {
                String pattern1 = str.substring(0, j);
                String pattern2 = str.substring(j, j + j);

                if(pattern1.equals(pattern2)) {
                    answer = j;
                    break;
                }
            }
            System.out.println("#" + (i+1) + " " + answer);
        }
    }
}

💡문제 풀이

• 브루트 포스(완전 탐색) 방식으로 모든 경우를 다 확인하는 방식으로 풀었다

1. 마디의 최대 길이는 10이므로 1부터 10까지 차례대로 가정
2. 가정한 길이 j만큼 문자열 자르기
   • 첫 번째 마디 : str.substring(0, j)
   • 두 번째 마디 : str.substring(j, j + j)
3. 첫 번째 마디와 두 번째 마디가 같은지 equals를 사용하여 확인
4. 만약 같고 제일 먼저 발견된 길이가 최소 길이니까 반복문 종료후 빠져나오기

• 문자열에는 공백으로 구분된 숫자들이 저장되어 있음
• 문자열에 나타나는 숫자 중 최소값과 최대값을 찾아 "최소값 최대값" 형태로 구하자

제한

• s에는 둘 이상의 정수가 공백으로 구분되어 있음

코드 구현

class Solution {
    public String solution(String s) {
        String[] str = s.split(" ");

        int min = Integer.parseInt(str[0]);
        int max = Integer.parseInt(str[0]);

        for(int i = 0; i < str.length; i++) {
            int num = Integer.parseInt(str[i]);
            if(num < min) {
                min = num;
            }
            if(num > max) {
                max = num;
            }
        }
        return min + " " + max;
    }
}

💡접근 방법

• split(" ") - 공백을 기준으로 나눠서 배열로 저장
• 최대값과 최솟값을 배열의 초기값으로 설정해주기
• 배열의 모든 요소를 하나씩 num에 저장
  • 현재 num이 임시 최솟값보다 작으면 min 갱신
  • 현재 num이 임시 최대값보다 크면 max 갱신 후 반환

프로그래머스 - 최대값과 최솟값

• 두 정수 a, b가 주어졌을 때 a와 b 사이에 속한 모든 정수의 합을 구하라
• 예시) a = 3, b = 5 이면 3 + 4 + 5 = 12 출력

제한

• a와 b가 같은 경우는 둘 중 아무 수나 리턴
• a와 b는 -10,000,000 이상 10,000,000 이하 인 정수
• a와 b의 대소관계는 정해져 있지 않다

코드 구현

class Solution {
    public long solution(int a, int b) {
        long answer = 0;

        int start = Math.min(a, b);
        int end = Math.max(a, b);

        for(int i = start; i <= end; i++) {
            answer += i;
        }
        return answer;
    }
}

프로그래머스 - 두 정수 사이의 합

1. 문제 분석

문제 이해

스택의 원리를 정확하게 알고 있는지 확인하는 문제 스택의 pop, push과 후입선출 특성을 이해하고 있다면 쉽게 풀 수 있을 것이다 단, 스택에 push하는 순서는 오름차순을 지키도록 함

에제 입력으로 문제 이해를 해보자

8
4
3
6
8
7
5
2
1

순서대로 입력 했다고 하자

수열 4 찾아야함 STACK - 1 STACK - 1 2 STACK - 1 2 3 STACK - 1 2 3 4 / PUSH(4) 까지 수열 3 찾아야함 STACK - 1 2 3 / POP(3) 수열 6 찾아야함 STACK - 1 2 5 6 / PUSH(6) 까지 한 후 POP(6) 수열 8 찾아야함 STACK - 1 2 5 7 8 / PUSH(8) 까지 한 후 POP(8) 수열 7 찾아야함 STACK - 1 2 5 7 / PUSH(7) 까지 한 후 POP(7) 수열 5 찾아야함 STACK - 1 2 5 / POP(5) 수열 2 찾아야함 STACK - 1 2 / POP(2) 수열 1 찾아야함 STACK - 1 / POP(1)

이러한 방식으로 문제를 풀어야 한다

• 어떻게 스택 연산을 수행할까 (오름차순으로 넣고 뺄까)

  • 현재 수열 값 >= 자연수

    • PUSH(4) 까지 해야하니 자연수가 1부터 4까지 PUSH() 하고 마지막에 한 번 POP()

  • 현재 수열 값 < 자연수

    • POP(4) 를 하면면 자연수는 5가 되고 수열 값은 3이 된다 따라서 POP(3)
    • 만약 해당 조건을 만족하지 않는 다면 스택이 정상적으로 작동하지 않기 때문에 "NO" 출력

입력

• 첫째 줄 - n (1 이상 10만 이하)
• 둘째 줄 - 수열을 이루는 1이상 n이하의 정수
• 중복 되는 정수는 나오지 않는다

출력

• push -> "+" / pop -> "-"
• 불가능한 경우 "NO"

시간 복잡도

• Stack 연산(pop(), push())은 상수 시간 복잡도가 소요된다 -> O(1)
• 최대 한 번씩 스택에 값을 pop, push 하니까 N개의 수를 처리하는데 O(N)의 시간이 걸림

코드 구현

import java.io.*;
import java.util.*;

public class No_1874 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        int arr[] = new int[T];

        // 1. 수열 배열 만들기
        for(int i = 0; i < T; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Stack<Integer> stack = new Stack<>();

        int num = 1;
        boolean ps = true;

        // 2. 수열을 하나씩 확인
        for(int i = 0; i < arr.length; i++) {
            int su = arr[i];

            // 3. 수열이 num 보다 크면 num을 수열 숫자까지 push
            if (su >= num) {  
                while(su >= num) {
                    stack.push(num++);
                    sb.append("+\n");
                }
                stack.pop();
                sb.append("-\n");
            } else {  // 4. 수열이 num 보다 작을 때
                int top = stack.pop(); 

                // 5. 스택에서 꺼낸 top와 수열 값이 다른 경우
                if(top != su) {
                    System.out.println("NO");
                    ps = false;
                    break;
                } else {
                    sb.append("-\n");
                }
            }
        }

        // 6. for문이 중단되지 않고 스택 연산이 모두 이뤄진 경우
        if(ps) {
            System.out.println(sb.toString());
        }
    }
}

문제 분석

숫자 N은 아래와 같다 이떄 a,b,c,d,e 구하는 문제 이다

• N의 크기는 2 이상 10,000,000이하

입력

• 첫 줄에는 테스트 케이스의 개수 T
• 각 테스트 케이스의 첫 번째 줄에 N

출력

• 출력의 각 줄은 #t로 시작하고, 공백을 한 칸 둔 다음 정답을 출력

코드 구현

import java.util.*;
import java.io.*;

public class No_1945 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());

            int a = 0;
            int b = 0;
            int c = 0;
            int d = 0;
            int e = 0;

            while (N % 2 == 0) {
                a++;
                N /= 2;
            }

            while (N % 3 == 0) {
                b++;
                N /= 3;
            }

            while (N % 5 == 0) {
                c++;
                N /= 5;
            }

            while (N % 7 == 0) {
                d++;
                N /= 7;
            }

            while (N % 11 == 0) {
                e++;
                N /= 11;
            }
            System.out.print("#" + (i + 1) + " " + a + " " + b + " " + c + " " + d + " " + e);
        }
    }
}

💡문제 풀이

우선 문제를 보면 a,b,c,d,e를 구해야하니까 N들의 수는 2,3,5,7,11로 나눠떨어지는 수이다 따라서 N이 해당 숫자로 더 이상 나눠지지 않을 때까지 계속 나누는 것이다

문제 분석

프로그래밍 언어에는 += 연산자가 있다 x += y = x = x + y 이런식으로 x의 값이 바뀐다 문제에서는 x에 저장된 값은 A, y에 저장된 값은 B라고 한다 x += y, y += x의 연산을 원하는 만큼 수행해서 x 와 y 둘 중 하나 이상의 저장된 값이 N이 초과가 되게 하려고 할 때, 최소 몇 번 수행해야 하는지 계산하는 프로그램을 만드는 것이 목적

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다 각 줄에는 세 개의 정수가 주어짐 테스트 케이스 개수는 60만개 이상으로 상당히 많다

출력

문제와 같이 x 와 y 둘 중 하나 이상의 저장된 값이 N초과가 되게 하려고 할 때, 최소 몇 번 수행해야 하는지 계산하는 프로그램을 만드는 것이 목적

코드 구현

import java.util.*;
import java.io.*;

public class No_21425 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());

            int count = 0;

            while (A <= N && B <= N) {
                if(A < B) {
                    A += B;
                } else {
                    B += A;
                }
                count++;
            }
            System.out.println(count);
        }
    }
}

💡 문제 풀이

A 또는 B 둘 중 하나라도 N을 초과하게 만들면 되기 때문에 값을 빨리 키우는 게 좋다 항상 더 작은 값을 더 큰 값에 더해주는 로직을 만들면 된다 예시를 들어보자 만약 A=2, B=5, N=10 일 때

• if(A < B)
  • A += B 실행 -> A = A + B
    • 2 + 5 = 7 (N을 초과하지 않음) 1회
    • 7 + 5 = 12 (N을 초과) 2회 // 총 2회

• B += A 실행 -> B = B + A
  • 5 + 2 = 7 (N을 초과하지 않음) 1회
  • 7 + 2 = 9 (N을 초과하지 않음) 2회
  • 9 + 2 = 11 (N을 초과) 3회 // 총 3회

따라서 더 작은 값을 큰 값에 더해주면 된다!

💡이것을 탐욕 알고리즘(Greedy Algorithm) 이라고 부른다 매 순간 가장 좋아 보이는 선택을 하는 것 기억해두자

문제 분석

문자열 binomial은 a op b 형태의 이항식이다 a 와b는 음이 아닌 정수이고 op는 +, -, * 중 하나이다

풀기 위해서 문자열을 공백을 기준으로 나누고 switch문으로 연산자의 기준에 따라 나누는 것으로 했다

제한

a 와b 는 0 이상 40,000이하의 음이 아닌 정수 0을 제외하고 a 와b는 0으로 시작하지 않는다 ex) 02393

코드 구현

class Solution {
    public int solution(String binomial) {
        int answer = 0;
        String[] arr = binomial.split(" ");

        int a = Integer.parseInt(arr[0]);
        int b = Integer.parseInt(arr[2]);

        String op = arr[1];

        switch(op) {
            case "+":
                answer = a + b;
                break;

            case "-":
                answer = a - b;
                break;

            case "*":
                answer = a * b;
                break;
        }

        return answer;
    }
}

문제 분석

모든 배열의 원소가 알파벳으로 이루어져 있을 때

• 배열의 홀수 인덱스의 문자열은 대문자로 변환
• 배열의 짝수 인덱스의 문자열은 소문자로 변환

제한

• strArr의 원소의 길이는 1이상 20이하
• strArr의 원소는 알파벳으로 이루어져 있음

코드 구현

class Solution {
    public String[] solution(String[] strArr) {
        String[] answer = new String[strArr.length];

        for(int i = 0; i < strArr.length; i++) {
            if(i % 2 == 0) {
                answer[i] = strArr[i].toLowerCase();
            } else {
                answer[i] = strArr[i].toUpperCase();
            }
        }
        return answer;
    }
}

💡문제 핵심 풀이

• toLowerCase() -> 소문자로 변환
• toUpperCase() -> 대문자로 변환

문제 분석

단어가 공백 한 개 이상으로 구분되어 있는 문자열이 있음 문자열에서 나온 단어를 앞에서부터 순서대로 담기

제한

1. 문자열은 영소문자와 공백으로만 이루어짐
2. 문자열의 길이는 1 이상 1000 이하
3. 문자열의 맨 앞과 맨 뒤에도 공백이 있을 수 있음
4. 문자열안에 단어 하나 이상 존재

코드 구현

class Solution {
    public String[] solution(String my_string) {
        String[] answer = my_string.trim().split("\\s+");

        return answer;
    }
}

💡 풀이 설명

trim() 사용해서 문자열의 앞, 뒤 공백 없애기 split() 안에 \\s+ 사용

\s -> 모든 공백 문자

• 스페이스(" ")
• 탭(\t)
• 줄바꿈(\n)
• 이 외의 모든 공백
• + -> 앞의 패턴이 1번이상 반복됨을 의미

\s는 \n 처럼 이스케이프 문자가 아니라 정규 표현식이라서 \ 하나 더 추가해야 함

해당 문제는 친절하게 어떤거 쓰고 어떻게 쓰이는 지 알려주고 있다

우선 코드에서 사용한 스택 함수를 보여드리겠습니다

💡isEmpty() 는 boolean 값을 반환하므로 코드에선 1과 0으로 변경해줘야 함

백준 10828 - 스택

1. 문제 분석

문제 이해

정수를 저장하는 스택을 구현 후 명령을 처리하는 프로그램 만들어보자 명령1. push X → X를 스택에 넣기 명령2. pop → 스택에서 가장 위에 있는 정수를 빼고, 그 수 출력 만약 스택에 정수가 없으면 -1 출력 명령3. size → 스택에 들어있는 정수의 개수 출력 명령4. empty → 스택이 비어있으면 1, 아니면 0 출력 명령5. top → 스택에 가장 위에 있는 정수 출력, 만약 스택에 정수가 없으면 -1

입력

• 첫째 줄에 주어지는 명령의 개수 N → (1 <= N <= 10,000)
• 둘째 줄부터 명령이 하나씩 주어짐 → (1 <= 명령 <= 100,000)

단, 문제에 나와있지 않은 명령이 주어지는 경우는 없음

출력

명령 한 줄당 결과도 하나씩 출력

2. 시간 복잡도

• N개의 명령어 만큼 반복해야하니까 → O(N)
• 나머지 스택 연산들은 → O(1)

💡for문이 한 번 돌때마다 스택 연산이 한 번씩 일어나기 때문에 총 시간 복잡도는 O(N)

3. 코드 구현

import java.io.*;
import java.util.*;

public class No_10828 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String s = st.nextToken();

            switch(s) {
            case "push" :
                stack.push(Integer.parseInt(st.nextToken()));
                break;

            case "pop" :
                if(stack.isEmpty()) {
                    sb.append("-1\n");
                } else {
                    sb.append(stack.pop()).append("\n");
                }
                break;

            case "size" :
                sb.append(stack.size()).append("\n");
                break;

            case "empty" :
                if(stack.isEmpty()) {
                    sb.append("1\n");
                } else {
                    sb.append("0\n");
                }
                break;

            case "top" :
                if(stack.isEmpty()) {
                    sb.append("-1\n");
                } else {
                    sb.append(stack.peek()).append("\n");
                }
                break;
            }
        }
        System.out.println(sb);
    }
}