[Do it! 알고리즘 코딩테스트 - 자바 편] 04. 자료구조

04-1. 배열과 리스트

배열: 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조.

- 값을 인덱스를 통해 참조(값에 바로 접근 가능. 새로운 값 삽입/삭제 어렵.)

- 배열의 크기는 선언할 때 지정, 한 번 선언하면 크기를 늘리거나 줄일 수 X.

- 선언한 자료형의 값만 저장 가능.

리스트: 값과 포인터를 묶은 노드를 포인터로 연결한 자료구조

- 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 (값에 접근하는 속도 느림)

---

[11720번: 숫자의 합] / 브4

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

public class Main
{
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int n = Integer.parseInt(br.readLine());
	    String sNum = br.readLine();
	    int sum=0;
	    for(int i=0; i<sNum.length(); i++) {
	        sum += sNum.charAt(i)-'0';
	    }
	    System.out.println(sum);
	}
}

 

형변환 연습

Long.parseLong(s), Long.valueOf(s)

 

 

[1546번: 평균] / 브1

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

public class Main
{
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int n = Integer.parseInt(br.readLine());
	    String[] s = br.readLine().split(" ");
	    long sum=0, max=0;
	    for(int i=0; i<n; i++) {
	        int score = Integer.valueOf(s[i]);
			if(max < score)
				max = score;
	        sum += score;
	    }
	    System.out.println(sum*100.0/max/n);
	}
}

---

04-2. 구간 합

합 배열 S를 만들어서 0번 인덱스부터의 합을 저장해두기. (S[i] = S[i-1] + A[i])

뺄셈을 이용하면 임의의 연속된 구간 합을 효율적으로 계산 가능.

i~j 구간 합 = S[j] - S[i-1]

(S[5]-S[1] = A[3]~A[5] 구간의 합)

---

[11659번: 구간 합 구하기 4] / 실3

크기 +1로 하는 게 편리

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

public class Main
{
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String[] nm = br.readLine().split(" ");
	    int n = Integer.parseInt(nm[0]);
	    int m = Integer.parseInt(nm[1]);
	    String[] nums = br.readLine().split(" ");
	    
	    int[] sum = new int[n+1];
	    sum[0] = 0;
	    for(int i=1; i<=n; i++) {
	        sum[i] = sum[i-1]+Integer.parseInt(nums[i-1]);
	    }
	    for(int i=0; i<m; i++) {
	        String[] input = br.readLine().split(" ");
	        System.out.println(sum[Integer.parseInt(input[1])]-sum[Integer.parseInt(input[0])-1]);
	    }
	}
}

 

[11660번: 구간 합 구하기 5] / 실1

크기 +1로 하는 게 편리, x1와 y1에 -1 주의

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

public class Main
{
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String[] nm = br.readLine().split(" ");
	    int n = Integer.parseInt(nm[0]);
	    int m = Integer.parseInt(nm[1]);
	    
	    int[][] board = new int[n+1][n+1];
	    int[][] sum = new int[n+1][n+1];
	    for(int i=1; i<=n; i++) {
	        String[] nums = br.readLine().split(" ");
	        for(int j=1; j<=n; j++) {
	            board[i][j] = Integer.parseInt(nums[j-1]);
	            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + board[i][j];
	        }
	    }
	    for(int i=0; i<m; i++) {
	        String[] input = br.readLine().split(" ");
	        int x1 = Integer.parseInt(input[0]);
	        int y1 = Integer.parseInt(input[1]);
	        int x2 = Integer.parseInt(input[2]);
	        int y2 = Integer.parseInt(input[3]);
	        int ans = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
	        System.out.println(ans);
	    }
	}
}

 

 

[10986번: 나머지 합] / 골3

계속 틀려서 문제가 뭐지했는데, 마지막 계산 공식에서 괄호를 잘못 쳤고, ans에 넣기 전에 (long)으로 형변환을 시켜줬어야 했다.

또는 rem자체를 long으로 만들거나...!! <- rem에 들어가는 값은 long범위를 안넘어서 int로 했는데, 앞으로 수가 얼추 크다면 바로 long을 쓰는게 나을지도 모르겠다

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

public class Main
{
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String[] nm = br.readLine().split(" ");
	    int n = Integer.parseInt(nm[0]);
	    int m = Integer.parseInt(nm[1]);
	    
	    String[] nums = br.readLine().split(" ");
	    int[] rem = new int[m];
	    long ans=0;
	    int sum=0;
	    for(int i=0; i<n; i++) {
	        sum = (sum + Integer.parseInt(nums[i])) % m;
	        if(sum==0) ans++;
	        rem[sum]++;
	    }
	    
	    for(int i=0; i<m; i++) {
	        if(rem[i]>1){
	            ans += (long)rem[i]*(rem[i]-1)/2; // (조합) 2개 뽑는 경우의 수
	        }
	    }
	    System.out.println(ans);
	}
}

---

04-3. 투 포인터

투 포인터: 2개의 포인터로 알고리즘의 시간복잡도를 최적화하기. 매우 간단함. 시간복잡도 O(n).

한 줄의 배열에서 두 변수 사용해 인덱스 탐색한다. (i와 j 또는 start와 end 등)

두 변수가 있는 부분을 비교하거나, 사이 범위를 비교하거나.

while문을 i < j 및 end < n 등으로 조건을 걸어 이용한다.

if문에서 sum등의 값으로 경계 확인 -> 문제에 따라 i 증가/ j 감소 OR start 증가 / end 증가 등

---

[2018번: 수들의 합 5] / 실5 - 투포인터

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

public class Main
{
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int n = Integer.parseInt(br.readLine());
	    int count=1; // n을 바로 뽑는 경우
	    int start=1;
	    int end=1;
	    int sum=1;
	    
	    while(end!=n) {
	        if(sum<=n) {
	            if(sum==n) count++;
	            end++;
	            sum += end;
	        } else {
	            sum -= start;
	            start++;
	        }
	    }
	    System.out.println(count);
	}
}

 

 

(추가로 찾아서 푼 문제)

[1789번: 수들의 합] / 실5 - 그리디

그리디로 최대한 작은 수를 사용.

s=5일 때는 1+4. i=2에서 1+2 이어가는 상황을 생각.

sum에 i를 더한 후 남은 s-sum<=i 로 체크해서 break했다.

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

public class Main
{
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    long s = Long.parseLong(br.readLine());
	    long sum=0;
	    for(int i=1; i<=Integer.MAX_VALUE; i++) {
	        sum+=i;
	        if(s-sum<=i) {
	            System.out.println(i);
	            break;
	        }
	    }
	}
}

 

 

[1940번: 주몽] / 실4 - 투포인터

i, j 합이 딱 m이 되어야 갑옷을 만들 수 있다.

i=0, j=n-1에서 A[i]+A[j]와 m을 대소비교해 i, j 좁혀가기.

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

public class Main
{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int[] A = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);
        int count = 0;
        int i=0;
        int j=n-1;
        while(i<j) {
            if(A[i] + A[j] < m)
                i++;
            else if (A[i] + A[j] > m)
                j--;
            else {
                count++;
                i++;
                j--;
            }
        }
        System.out.println(count);
        br.close();
    }
}

 

 

[1253번: 좋다] / 골4

수의 범위를 잘 확인하지 못해 틀렸다. 자연수 범위라는 말 없다! 음수 및 0이 가능.

 

고려해야 하는 엣지 케이스 유형

1. 0 포함 케이스: [0,0,0], [0,m,m] (m = 0 + m)
2. 음수 포함 케이스: [-1,1,0], [-2,-1,-3] (정렬 시 순서 주의)
3. 중복 원소 케이스: [2,2,4], [3,3,6]
4. 자기 자신 사용 금지 케이스: [5,10] 은 불가해야 함 vs 하지만 [5, 5, 10]이면 성립해야 함
5. 최대/최소값 극단 케이스: [1,2,3,1000000000], [-1000000000,-1,-2,-3]
6. 소규모 입력: n=2, n=3

이중에서 2번 때문에 틀렸다.

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

public class Main
{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] A = new int[n];
        int count = 0;
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);
        
        for (int m=0; m<n; m++) {
            int i=0;
            int j=n-1;
            while (i<j) {
                if (A[i] + A[j] == A[m]) {
                    if (i==m) { 
                        i++;
                    } else if (j==m) { 
                        j--;
                    } else {
                        count++;
                        break;
                    }
                } else if (A[i] + A[j] < A[m]) {
                    i++;
                } else {
                    j--;
                }
            }
        }
        System.out.println(count);
        br.close();
    }
}

---

04-4. 슬라이딩 윈도우

슬라이딩 윈도우 알고리즘: 2개의 포인터로 범위를 지정한 다음, 범위를 유지한 채로 이동하며 문제를 해결.

---

[12891번: DNA 비밀번호] / 실2

https://www.acmicpc.net/problem/12891

charAt()으로 문자열의 문자에 순차 접근했다.

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

public class Main
{
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        String dna = br.readLine();
        
        int[] minCntList = new int[4];
        int[] currCntList = new int[4];
        st = new StringTokenizer(br.readLine());
        for(int k=0; k<4; k++){
            minCntList[k] = Integer.parseInt(st.nextToken());
        }
        
        int availableCnt=0;
        for(int i=0; i<s; i++){
            currCntList[baseCharToIndex(dna.charAt(i))]++;
            if(i>=p-1){
                if(i>=p)
                    currCntList[baseCharToIndex(dna.charAt(i-p))]--;
                boolean flag=true;
                for(int k=0; k<4; k++){
                    if(minCntList[k]>currCntList[k]) {
                        flag=false;
                        break;
                    }
                }
                if(flag){
                    availableCnt++;
                }
            }
        }
        System.out.println(availableCnt);
	}
	static int baseCharToIndex(char c){
	    if(c=='A') return 0;
	    else if(c=='C') return 1;
	    else if(c=='G') return 2;
	    else return 3;
	}
}

 

 

[11003번: 최솟값 찾기] / 플5

아래처럼 풀면 시간 초과... 데자뷰... 시간 복잡도부터 계산한 후에 풀어야 한다. n, l이 5백만이어서 O(n)으로 해결해야 한다.

현재 수보다 큰 값을 제거해 min 비교를 하지 않아도 되도록 해야 함.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nl = br.readLine().split(" ");
		int n = Integer.parseInt(nl[0]);
		int l = Integer.parseInt(nl[1]);
		int[] A = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for(int i=0; i<n; i++) {
		    A[i] = Integer.parseInt(st.nextToken());
		    int d = A[i];
		    for(int j=0; j<l; j++){
		        if(i-j<0) break;
		        d = Math.min(d, A[i-j]);
		    }
		    bw.write(d+" ");
		}
		bw.flush();
	}
}

deque으로 구현!!

양쪽을 사용, now 이하의 값만 저장되도록 remove해 정렬같은 효과를 내면서 & 인덱스 넘어가는 값은 삭제!

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

public class Main {
	static class Node{
	    int value;
	    int index;
	    Node(int value, int index){
	        this.value = value;
	        this.index = index;
	    }
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int l = Integer.parseInt(st.nextToken());
	    st = new StringTokenizer(br.readLine());
	    Deque<Node> dq = new LinkedList<>();
	    
		for(int i=0; i<n; i++) {
		    int now = Integer.parseInt(st.nextToken());
		    while(!dq.isEmpty() && dq.getLast().value > now) {
		        dq.removeLast();
		    }
		    dq.addLast(new Node(now, i));
		    if(dq.getFirst().index<= i-l) {
		        dq.removeFirst();
		    }
		    bw.write(dq.getFirst().value+" ");
		}
		bw.flush();
		bw.close();
	}
}

---

04-5. 스택과 큐

스택: 삽입과 삭제 연산이 LIFO(후입선출)로 이뤄지는 자료구조.

- 새 값이 스택에 들어가면 top이 새 값을 가리킨다. pop으로 스택에서 값을 빼낼 때 가장 마지막에 넣었던 값(top)이 나온다.

- DFS와 백트래킹 풀이에 효과적이다. LIFO의 개념이 재귀 함수 알고리즘 원리와 맞닿아 있다. (cf. 함수 스택 프레임)

 

스택 용어

- top: 삽입과 삭제가 일어나는 위치

연산

- push: top 위치에 새로운 데이터 삽입

- pop: top 위치에 현재 있는 데이터를 삭제하고 확인(반환값 활용 가능)

- peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산

 

큐: 삽입과 삭제 연산이 FIFO(선입선출)로 이뤄지는 자료구조.

- 먼저 들어온 데이터가 먼저 나가, 삽입과 삭제 방향이 다르다.

- 값의 추가는 큐의 rear에서, 삭제는 큐의 front에서 이루어진다.

- BFS에서 자주 사용한다.

 

큐 용어

- front: 큐에서 가장 앞 데이터를 가리키는 영역
- rear: 큐에서 가장 끝 데이터를 가리키는 영역

- add: rear 부분에 새로운 데이터를 삽입하는 연산

- poll: front 부분에 있는 데이터를 삭제하고 확인(반환값 활용 가능)

- peek: 큐의 front에 있는 데이터를 확인할 때 사용하는 연산

 

우선순위 큐: 값이 들어간 순서와 상관 없이, 우선순위가 높은 데이터가 먼저 나오는 자료구조.

- 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다.

- 힙을 이용해 구현한다.

---

[1874번: 스택 수열] / 실2

스택에 오름차순으로 숫자가 저장될 수 있을 때(1~n), 주어진 수열을 스택의 push/pop을 반복해서 만들 수 있는지.

 

if(num<=ai)일 때와, else 즉 num>ai일 때를 나누어서 봐야 한다.

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

public class Main
{
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int n = Integer.parseInt(br.readLine());
	    int[] A = new int[n];
	    for(int i=0; i<n; i++) {
	        A[i] = Integer.parseInt(br.readLine());
	    }
	    
	    Stack<Integer> stk = new Stack<>();
	    StringBuffer sb = new StringBuffer();
	    int num=1;
	    boolean result=true;
	    
	    for(int i=0; i<A.length; i++) {
	        int ai = A[i];
	        if(num<=ai) {
    	        while(num<=ai){
    	            stk.push(num);
    	            sb.append("+\n");
    	            num++;
    	        }
    	        stk.pop();
    	        sb.append("-\n");
	        } else {
	            int top = stk.pop();
	            if(top<=ai) {
    	            sb.append("-\n");
	            } else {
	                System.out.println("NO");
	                result=false;
	                break;
	            }
	        }
	    }
	    if(result) System.out.println(sb.toString());
	    br.close();
	}
}

 

c++로 풀었던 것

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    stack<int> S;
    int n;
    cin >> n;
    int cnt = 1;
    string ans;
    while (n--) {
        int t;
        cin >> t;
        while (cnt <= t) {
            S.push(cnt++);
            ans += "+\n";
        }
        if (S.top() != t) {
            cout << "NO\n"; 
            return 0;
        }
        S.pop();
        ans += "-\n";
    }
    cout << ans;
}

 

스택 삽입 - push(v), add(v)

스택 삭제 - pop(), remove(index)

스택 top에 있는 원소 반환: peek()

크기: size()

비어있는가? isEmpty()

search(v): 값이 top에서부터 몇번째에 존재하는지 찾음 (lastIndexOf() 메서드를 사용하여 스택의 마지막 위치인 꼭대기(Top)에서 데이터를 검색하며, 특정 값이 꼭대기(Top)에 존재하면 1을 반환하고 한 층씩 내려갈수록 반환 결과는 +1 증가합니다.
출처: https://developer-talk.tistory.com/714 [DevStory:티스토리])

특정 인덱스에 존재하는 값 반환: elementAt(idx)

 

 

[17298번: 오큰수] / 골4

크기 N 수열 A=A1~AN. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다.

Ai의 오큰수: i보다 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수. (그러한 수가 없는 경우에 오큰수는 -1)

 

[핵심 아이디어]

- 스택에 새로 들어오는 수가 peek한 수보다 크면 그 수는 오큰수가 된다.

- 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력.

 

BufferedWriter를 안 써서 처음에 시간초과가 났다. N번 출력할 때 BufferedWriter 쓰기!!!

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

public class Main
{
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int n = Integer.parseInt(br.readLine());
	    int[] A = new int[n];
	    int[] ans = new int[n];
	    Stack<Integer> stk = new Stack<>();
	    StringTokenizer sb = new StringTokenizer(br.readLine());
	    for(int i=0; i<n; i++) {
	        A[i] = Integer.parseInt(sb.nextToken());
	        ans[i] = -1;
	    }
	    stk.push(0);
	    for(int i=1; i<n; i++) {
	        while(!stk.isEmpty() && A[stk.peek()]<A[i]){
                ans[stk.pop()] = A[i];
	        }
	        stk.push(i);
	    }
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    for(int i=0; i<n; i++) {
	        bw.write(ans[i]+" ");
	    }
	    bw.write("\n");
	    bw.flush();
	}
}

 

 

[2164번: 카드2] / 실4

카드가 1장 남을 때까지 맨 위의 카드를 버리고, 맨 위의 카드를 가장 아래 카드 밑으로 이동시키기.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i=1; i<=n; i++) {
            q.offer(i);
        }
        while(q.size()>1) {
            q.poll();
            q.offer(q.poll());
        }
        System.out.println(q.peek());
    }
}

 

[11286번: 절댓값 힙 구현하기] / 실1

PriorityQueue에 [1순위] 절댓값을 우선 비교, 값이 같으면 [2순위] 부호(음수 우선) 비교하는 Comparator를 구현.

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

public class Main
{
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] cmd = new int[n];
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            (a, b) -> {
                int absA = Math.abs(a);
                int absB = Math.abs(b);
                if (absA == absB) return Integer.compare(a, b);
                else return Integer.compare(absA, absB);
            }
        );
        
        for(int i=0; i<n; i++){
            int x = Integer.parseInt(br.readLine());
            if(x==0){
                if(pq.isEmpty()) {
                    System.out.println(0);
                } else {
                    System.out.println(pq.poll());
                }
            } else {
                pq.offer(x);
            }
        }
	}
}