<stdio.han>

[문제 링크]

https://school.programmers.co.kr/learn/courses/30/lessons/87377

[난이도]

- Level 2

[알고리즘]

- 구현

- 배열

[코드]

import java.util.*;

class Solution {
    public String[] solution(int[][] line) {
        long maxX = Long.MIN_VALUE;
        long maxY = Long.MIN_VALUE;
        long minX = Long.MAX_VALUE;
        long minY = Long.MAX_VALUE;

        List<long[]> list = new ArrayList<>();

        for (int i = 0; i < line.length - 1; i++) {
            for (int j = i + 1; j < line.length; j++) {
                long A = line[i][0];
                long B = line[i][1];
                long E = line[i][2];
                long C = line[j][0];
                long D = line[j][1];
                long F = line[j][2];

                long denominator = A * D - B * C;

                if (denominator == 0) continue;  // 평행 또는 동일 직선

                long numeratorX = B * F - E * D;
                long numeratorY = E * C - A * F;

                // 정수 교차점인지 확인
                if (numeratorX % denominator != 0 || numeratorY % denominator != 0) continue;

                long x = numeratorX / denominator;
                long y = numeratorY / denominator;

                maxX = Math.max(maxX, x);
                maxY = Math.max(maxY, y);
                minX = Math.min(minX, x);
                minY = Math.min(minY, y);

                list.add(new long[]{x, y});
            }
        }

        int width = (int)(maxX - minX + 1);
        int height = (int)(maxY - minY + 1);

        char[][] graph = new char[height][width];
        for (char[] row : graph) {
            Arrays.fill(row, '.');
        }

        for (long[] point : list) {
            int x = (int)(point[0] - minX);
            int y = (int)(maxY - point[1]);  // y축 뒤집기

            graph[y][x] = '*';
        }

        String[] answer = new String[height];
        for (int i = 0; i < height; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < width; j++) {
                sb.append(graph[i][j]);
            }
            answer[i] = sb.toString();
        }

        return answer;
    }
}

[풀이]

단순 구현 문제이다. 중요한점은 int가 아닌 long타입으로 변환해서 풀어야한다는것이다. 그 이유는 int*int가 int의 범위를 벗어나는 경우가 있어 테스트케이스29번을 통과하지 못하기 때문이다.

[문제 링크]

https://school.programmers.co.kr/learn/courses/30/lessons/388351

[난이도]

- Level 1

[알고리즘]

- 구현

[코드]

class Solution {
    public int solution(int[] schedules, int[][] timelogs, int startday) {
        int answer = 0;
        boolean flag = false;
        for(int i=0;i<schedules.length;i++){
            int time = function(schedules[i]);
            flag = false;
            for(int j=0;j<7;j++){
               if(j == 7-startday || j == 6-startday){
                   continue;
               }
                if(6-startday == -1){
                    if(j==6){
                        continue;
                    }
                }

                
                if(timelogs[i][j]>time){
                    flag = true;
                    break;
                }
            }
            if(!flag){
                answer++;
            }
        }
        return answer;
    }
    static int function(int time){
        int min = time%100;
        int hour = time/100;
        int newMin = min+10;
        if(newMin>=60){
            newMin -=60;
            hour++;
        }
        int newTime = hour*100 + newMin;
        return newTime;
    }
}

[풀이]

단순 구현 문제이다. 토요일과 일요일이 위치할 배열을 고르는 법은 6 - startday, 7-startday이다. 중요한점은 startday가 7일때를 고려해야한다. 이때 토요일은 배열의 마지막에 위치하기 때문에 한 번 더 if문으로 해결했다.

10분이 지난시간이 60분을 넘길때를 고려해주어야 한다. 

[문제 링크]

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

[난이도]

- Silver 2

[알고리즘]

- LinkedHashSet

[코드]

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 🔹 HashSet 대신 LinkedHashSet 사용 (입력 순서 유지 가능)
        Set<String> keywords = new LinkedHashSet<>();
        for (int i = 0; i < N; i++) {
            keywords.add(br.readLine());
        }

        for (int i = 0; i < M; i++) {
            String[] words = br.readLine().split(",");
            for (String word : words) {
                keywords.remove(word); // ✅ 평균 O(1)로 최적화됨
            }
            bw.write(keywords.size() + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

[풀이]

처음엔 List로 풀었지만 List.remove() 는 for문으로 전체탐색을 한번진행하며 삭제하는 메서드이므로 최악의 경우 O(N*M)가 걸린다. LinkedHashSet은 O(1)이 걸린다.

그렇다면 언제 LinkedHashSet을 쓰면 좋을까?

1. 중복을 허용하지 않아야 할때 -> List는 중복 허용, LinkedHashSet은 중복을 제거함.

2. 입력된 순서를 유지해야 할 때 -> HashSet은 순서를 보장하지 않지만, LinkedHashSet은 순서를 유지.

3. 탐색보다는 삭제 연산이 많을 때 -> ArrayList는 삭제 시 O(N)인데, LinkedHashSet은 O(1)에 가깝다.

하지만 LinkedHashSet을 쓰면 안되는 경우도 있다.

1. 빠른 인덱스 접근이 필요할 때

• ArrayList.get(index)는 O(1)로 빠르지만 LinkedHashSet은 인덱스로 직접 접근할 수 없다.

2. 메모리를 아껴야 할 때

3. 데이터가 중복될 가능성이 없거나, 순서가 중요하지 않을 때

결론 : 언제 LinkedHashSet을 써야 할까?

• 중복을 방지해야 하고, 순서를 유지해야하며, 삭제 연산이 많을 때 -> LinkedHashSet
• 탐색이나 삽입 속도가 중요하고, 중복을 허용해도 된다면 -> ArrayList
• 인덱스로 직접 접근해야 한다면 -> ArrayList

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

[틀린 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        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 X = Integer.parseInt(st.nextToken());
        int[] visitors = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            visitors[i] = Integer.parseInt(st.nextToken());
        }


        int max = 0;
        int answer = 0;
        for (int i = 0; i <= N - X; i++) {
            int tmp = 0;
            for (int j = i; j < i + X; j++) { // X기간동안의 방문자 수의 합
                tmp += visitors[j];
            }
            if (tmp > max) { // X기간동안 최고 방문자수가 갱신될 경우
                answer = 0;
                max = Math.max(tmp, max);
            }
            if (tmp == max) { // 최고방문자수가 max 와 같은 기간 카운팅
                answer++;
            }
        }
        System.out.println(max);
        System.out.println(answer);
    }
}

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        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 X = Integer.parseInt(st.nextToken());
        int[] visitors = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            visitors[i] = Integer.parseInt(st.nextToken());
        }

        int sum = 0;
        for (int i = 0; i < X; i++) {
            sum += visitors[i];
        }


        int max = sum;
        int answer = 1;
        for (int i = 0; i < N - X; i++) { // 슬라이딩 윈도우

            //한칸 씩 이동
            sum += visitors[i+X];
            sum -= visitors[i];

            if (sum == max) { // 최다 방문자수가 유지될 경우 answer++
                answer++;
            }

            if (sum > max) { // 최다 방문자수가 갱신되었을 경우
                answer = 1;
                max = sum;
            }

        }
        if (max == 0) { // 최대 방문자 수가 0이라면 SAD 출력
            System.out.println("SAD");
        } else {
            System.out.println(max);
            System.out.println(answer);
        }
    }
}

[설명]

이 문제는 슬라이딩 윈도우 기법을 활용해야 한다. 처음에 이 문제를 풀었을때는 이중 for문으로 문제를 풀었었다. 그러자 시간초과 떴다. 그래서 2중for문을 해결하기 위해 for문을 하나로 두고 다시 풀었다.

먼저 입력을 받고 입력받은것중에 슬라이딩 윈도우로직을 사용할 구간만큼 미리 합을 구해놓는다.

그리고 for문을 이용해 한칸씩 이동해 나아가며 합을 계산한다. 

계산한 합이 알고있는 max값보다 클 경우 max값을 갱신하고 answer를 1로 초기화시킨다.

max값과 새로 이동해 계산한 합의 값이 같을 경우 answer를 1 증가시킨다.