2️⃣ [Class: 2]

[subeenjeonHere]

• [x] #3
• [x] #26
• [x] #4
• [x] #5
• [x] #6
• [x] #15
• [x] #21
• [ ] #32
• [ ] #30
• [x] #31
• [ ] #34
• [ ] #35
• [ ] 수 찾기
• [ ] 좌표 정렬하기
• [ ] 체스판 다시 칠하기
• [x] #43
• [x] #44

[subeenjeonHere]

나이순정렬 #5

시간초과

원인

버블 정렬로 코드 작성, 시간 복잡도 O(n^2)

• 각 회원을 모든 회원들과 비교한다. 이중 for loop를 통해 구현되며 이로 인해 O(n^2)의 시간 복잡도가 발생한다.
• 또한, swap 연산을 사용하여 회원의 위치를 바꾼다. 이는 각 회원을 다른 모든 회원과 비교할 때마다 발생하므로 O(n^2)의 시간 복잡도를 가진다.

그럼, 문제에선 최대 100,000명까지 회원이 있을 수 있으므로, n^2의 연산이 수행된다. 따라서 회원 수가 100,000인 경우, 최대 10,000,000,000번의 연산이 수행된다.

---

Solved

        arrayList.sort(new Comparator<ArrayList<String>>() {
            @Override
            public int compare(ArrayList<String> o1, ArrayList<String> o2) {
                int a1 = Integer.parseInt(o1.get(0));
                int a2 = Integer.parseInt(o2.get(0));
                return Integer.compare(a1, a2);
            }
        });
        arrayList.sort(new Comparator<ArrayList<String>>() {
            @Override
            public int compare(ArrayList<String> o1, ArrayList<String> o2) {
                int age1 = Integer.parseInt(o1.get(0));
                int age2 = Integer.parseInt(o2.get(0));
                int idx1 = Integer.parseInt(o1.get(2));
                int idx2 = Integer.parseInt(o2.get(2));
                if (age1 == age2 && idx1 > idx2) {
                    return Integer.compare(idx1, idx2);
                }
                return 0;

            }
        });

Arrays.sort() 메소드 분할정복으로 동작하므로 시간 복잡도 O(n log n)

[subeenjeonHere]

4 랜선 자르기

시간 소요한 것

이분탐색 알고리즘 자체는 쉬웠는데, 엣지 케이스에 시간을 너무 많이 소요했다.

Idiot

1. 시간 초과

• 이분 탐색 코드인데, 아마 몫을 다시 구하는 부분에서 코드 병목현상 발생: 시간 복잡도 O(n)

  • 아니었다. 랜선 길이가 2^31-1 인데, 이걸 더하면 int의 최댓값을 초과함. 그래서 long으로 선언해줘야 했다.
  • 그래서 Overflow 발생했다. → 연산 과정에서 범위초과하는 경우 계산량 급격히 늘어나거나 무한루프 → 시간 초과

  //중간값 찾기
  mid = min + (max - min) / 2;

2. UpperBound

*return* Math.min(mid, min - 1);으로 하니까 정답 

이진 탐색에서 UpperBound는 목표 값보다 큰 가장 작은 값이다.

이진 탐색 후, 최종 mid 값이 자를 수 있는 실제의 최대 랜선 길이가 아닐수도 있다. 정확히 N개의 랜선을 자를 수 있는 최대의 길이를 찾아야 한다.

Mid 값이 N개 이상의 랜선을 자르는 경우에도, 더 큰 Mid 값도 정확히 N개의 랜선을 자를 수 있기에

//반복문 범위
while (min <= max) {
//생략
} else if (count >= n) {
                min = mid + 1;
            }

범위를 최대한 좁혀나가면서, Mid 값을 찾아 나간다. 이 때 mid와 min-1 중, 최솟값을 반환해야 한다.

While 문이 종료되는 경우는 min이 max를 초과하는 경우다. 이 경우, 그 직전의 mid 값이 가능한 최대의 값 = 즉, N개 이상의 랜선을 자를 수 있었던 마지막 값이었다.

3. 최댓값 부터 접근 해야한다.

• 왜 최대값부터 접근해야 하는건가? K개의 랜선 중, 최대값으로 이진탐색을 한다면 어차피 최소 길이의 랜선으론 0개의 랜선밖에 못 만드는데, 최솟값을 Right으로 설정하는 게 더 탐색을 적게할 수 있지 않는가?
  • 최대 길이를 찾는 것이므로 Max로 설정해서, 가장 긴 랜선을 만들어 봐야 한다.
  • 반면 최소 길이를 Max로 설정한다면, 탐색 과정에서 랜선 길이를 늘려야 하는데, 정답 범위를 넓혀가는 방향으로 탐색을 진행하게 됨.

[subeenjeonHere]

소수구하기 #15

답은 정상적으로 나오는데, StringBuilder 출력초과

시간 소요한 부분

1. 답은 출력되나, 채점 시 출력초과로 틀림. 이유는 3일 때 StringBuilder를 별도로 추가해줬기 때문임. 원래 메인 메소드에서 소수 판별했다면, isPrime 메소드로 소수 판별하여 메인 메소드에서 StringBuilder 에 추가 → 모든 숫자 일관되게 출력되도록 수정
2. 근데 88%에서 틀림. 이유는 2를 소수가 아니라고 false를 리턴하는 실수했다. 수정

[subeenjeonHere]

21 숫자카드2

HashMap으로 풀었다.

1. For Loop으로 배열 순회하기엔 시간초과 날 것 같아서 키-밸류 활용할 수 있는 HashMap 떠올림

시간 소요한 부분

1. 수 범위를 고려했을 때 int가 아니라 long 형으로 데이터 타입 지정해야했다.

2. val 값 갱신 할 때, 2 2 1 2 3 이렇게 값이 온다면? 처음에 if (val=1) else (val+=1) 이렇게 설정했었는데, 2 사이에 1이 왔을 때 val이 1로 갱신되어 그 다음 2 키값이 1이 되어버린다.

        for (int i = 1; i <= n; i++) {
            long key = sc.nextLong();
            //중복 된 값 갱신하더라도 중간에 val 1로 초기화되면 다시 1로 갱신됨
            if (!map.containsKey(key)) {
                val = 1;
                map.put(key, val);
            } else {
                long newVal = map.get(key);
                newVal += 1;
                map.put(key, newVal);
            }
        }

[subeenjeonHere]

31 괄호

시간 소요한 것

1. 로직

1. 처음에 ( 괄호는 +1, ) 괄호는 -1로 스택에 전체 push 이후, pop 하며 전체 합계가 0이 되면 YES를 출력하도록 했다.
2. 생각할 때도 분명히 인지하고 있었는데, 일단 코드 짰고 당연히 틀렸음. 0이 온다고 한들 괄호가 닫히는 순서가 올바르지 않으면 NO를 출력해야 한다.

3. 일단 +- 연산으로 할거면 최종 합이 0이 되어야 함은 맞다. (=괄호 한 쌍)
4. 그리고 스택이 비어있을 때 )가 온다면 무조건 NO이다.
   1. 열어놓은 ( 괄호가 없기 때문
5. ( 다음에 )가 온다면, (= peek + push) 합계가 0 이라면, 해당 원소를 push하지 않고 스택에서 pop을 수행한다.
6. 끝까지 진행하고, 스택 사이즈가 0이라면 YES, 0이 아니라면 NO를 출력한다.
   1. NO라는 것은 괄호 한 쌍이 이뤄지지 않았다는 것이기 때문이다.

[subeenjeonHere]

43 이항계수 1

이항계수 조합 점화식

dp[i][j] = dp[i-1][j] + d[i-1][j-1]

[subeenjeonHere]

44 부녀회장이 될테야

DP 점화식

• 조건: "a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합"

for (int p = 1; p < dp.length; p++) {
    for (int q = 1; q < dp[0].length; q++) {
        dp[p][q] = dp[p][q - 1] + dp[p - 1][q];
    }
}

• 점화식
  • dp[p][q]: p층 q호에 살고 있는 사람의 수
  • dp[p][q - 1]: p층 (q-1)호에 살고 있는 사람의 수
  • dp[p - 1][q]: (p-1)층 q호에 살고 있는 사람의 수

바텀-업 방식 DP

0층 1호에는 1명, 0층 i호에는 i명이 살고 있다는 초기 조건을 먼저 DP 테이블에 채우고 시작해야 한다.

---

누적합으로도 풀었었는데

• TC마다 누적합 배열을 초기화해주어야 한다. -> 각 테스트 케이스에서 누적합이 독립적으로 수행되어야 함