2025년 01월 21일

2025. 1. 21 알고리즘 오답노트

알고리즘

1. 달팽이는 올라가고 싶다 (백준 2869번)

링크
처음엔 루프문으로 해결하려 했지만, 테스트 케이스당 0.25초 (절대 루프문 못씀) 가 조건이라 루프문은 포기.
알고리즘 분류(힌트)를 슬쩍 봤다.. 수학이라고 한다.
그럼 한 줄로도 가능할 것 같은데? 하고 방정식을 세워봤다.
깔끔하게 해결 완료 ^ㅅ^ (30분 걸림)
달팽이는 올라가고 싶다 방정식 내 답안

const [A,B,V] = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
    .toString()
    .trim()
    .split(" ")
    .map(Number);

let day = 0;
let count = 0;

while (day < V) {
    day += A;

    if (day >= V) break;

    day -= B;

    if (day >= V) break;

    count += 1;
}

console.log(count + 1);

고친 답안(정답)

const [A,B,V] = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
    .toString()
    .trim()
    .split(" ")
    .map(Number);

console.log(Math.ceil(((V - B) / (A - B)) % V));

2. 수 정렬하기 3 (백준 10989번)

링크
그냥 정렬하면 되겠지? 라고 생각하는 순간 이렇게 쉬운 게 나올리 없었고, 메모리 제한이 8MB인데다 자바스크립트(node.js) 사용 불가라니..
그래서 오래 전에 배웠던 파이썬 문법을 되뇌어 가며 풀었는데, 진짜 골머리를 앓았다.
결국엔 답지 보고 계수 정렬을 쓰면 된다는 것을 알았고, 이를 사용하라는 힌트가 조건에 나와있었다.

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000) 이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

내 답안

length = int(input())
arr = [int(input()) for _ in range(length)]

for i in range(0, length):
  for j in range(i, length):
    if arr[i] > arr[j]:
        arr[i], arr[j] = arr[j], arr[i]

for i in range(0, length):
   print(arr[i])

고친 답안(정답)

import sys

length = int(sys.stdin.readline().rstrip())

dict = {}

for i in range(length):
  n = int(sys.stdin.readline().rstrip())

  if (n not in dict):
    dict[n] = 1
  else:
    dict[n] += 1

for i in range(max(dict.keys()) + 1):
  if i not in dict:
    continue
  else:
    for _ in range(dict[i]):
      print(i)