백준 문제풀이 1181번 단어 정렬

2021/11/25 #algorithm #boj #silver #sorting

[백준 문제풀이] 1181번 단어 정렬

1181번 단어 정렬 (Silver 5)

문제

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

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

  1. 길이가 짧은 것부터
  2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

풀이

Set 객체로 만들어서 반복을 지우고, sort를 두 번 사용해서 풀 수 있었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = input.shift();

let strArr = new Set(input);
strArr = [...strArr];
strArr.sort();

strArr.sort((a, b) => a.length - b.length);

console.log(strArr.join("\n"));

구현할 때 왜 단어순 정렬부터 했을까? (2022.05.04)

문제를 보고 바로 생각해볼 수 있는 것은, 단어 순으로 정렬한 뒤, 길이순으로 정렬하는 것이다.

하지만 조금만 더 생각해보면, 그렇게 정렬하게될 경우 단어순으로 정렬하게되며 길이순 정렬이 모두 꼬인다는 것을 생각해볼 수 있다.

Read more

백준 문제풀이 10814번 나이순 정렬

2021/11/25 #algorithm #boj #silver #sorting

[백준 문제풀이] 10814번 나이순 정렬

10814번 나이순 정렬 (Silver 5)

문제

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

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

풀이

가입순으로 이미 정렬되어있기 때문에, 나이 순으로만 정렬할 수 있도록 sort() 메서드를 사용했다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = input.shift();
input = input.map((el) => el.split(" "));

input.sort((a, b) => parseInt(a[0]) - parseInt(b[0]));

input = input.map((el) => el.join(" "));

console.log(input.join("\n"));
Read more

백준 문제풀이 좌표 정렬하기 1, 2

2021/11/24 #algorithm #boj #silver #sorting

[백준 문제풀이] 좌표 정렬하기 1, 2

11650번, 11651번 좌표 정렬하기 (Silver 5)

두 문제가 작은 차이만 있고, 풀이는 같아서 하나의 게시글에서 다루려고 한다.

11650번 문제

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

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

11651번 문제

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

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력 (동일)

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력 (동일)

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

풀이

sort()로 쉽게 풀 수 있었다.

11650번 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = parseInt(input.shift());
input = input.map((el) => el.split(" "));

input.sort((a, b) => {
  if (parseInt(a[0]) === parseInt(b[0])) {
    return parseInt(a[1]) - parseInt(b[1]);
  } else {
    return parseInt(a[0]) - parseInt(b[0]);
  }
});

input = input.map((el) => el.join(" "));

console.log(input.join("\n"));

11651번 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = parseInt(input.shift());
input = input.map((el) => el.split(" "));

input.sort((a, b) => {
  if (parseInt(a[1]) === parseInt(b[1])) {
    return parseInt(a[0]) - parseInt(b[0]);
  } else {
    return parseInt(a[1]) - parseInt(b[1]);
  }
});

input = input.map((el) => el.join(" "));

console.log(input.join("\n"));
Read more

백준 문제풀이 10989번 수 정렬하기 3

2021/11/23 #algorithm #boj #silver #sorting

[백준 문제풀이] 10989번 수 정렬하기 3

10989번 수 정렬하기 3 (Silver 5)

문제

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

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

시간 제한 5초, 메모리 제한 8MB

접근

힌트가 카운팅 정렬이었어서, 카운팅 정렬에 대해 찾아보았다.

계수 정렬 (Counting sort)

Counting Sort는 O(n)의 시간 복잡도를 가지는 정렬 알고리즘이다. 일반적으로는 평균 시간 복잡도가 O(nlogn)인 Quick Sort 알고리즘이 더 빠르지만 수의 등장 횟수를 누적합으로 바꿔주는 Counting Sort의 경우 수의 범위 특정하게 정해진 경우 range를 구해서 빠르게 정렬할 수 있다. 하지만 대부분의 상황에서 엄청난 메모리 낭비가 될 수 있다.

일단 설명만 보고 스스로 구현을 먼저 해보고, 막히면 찾아보기로 했다.

풀이

범위에 맞는 countArr를 만들어서 풀려고 했는데, 바로 메모리 초과가 나왔다.

찾아보니, node.js는 메모리 초과가 나와서, 추후 제한 완화 예정이라고 해서 파이썬으로 찾아서 문제를 풀었다. 설명되어있는 counting sort를 사용해보고 싶었는데, 생각과는 달리 더 빠른 방법이 있었다.

python으로 풀때도 input으로 받으면 메모리 초과가 나온다고 해서, sys.stdin.readline()을 사용해서 풀었다. 나중에 node.js 메모리 제한이 풀리면 다시 풀어보고 싶다.

파이썬에서는 반복문에 변수가 사용되지 않을 경우, _를 사용한다는 것도 인상깊었다.

그리고 FE 개발자도 파이썬으로 코딩 테스트를 준비하는 이유도 느껴볼 수 있었다…☆

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
import sys

N = int(sys.stdin.readline())
num_list = [0] * 10001

for _ in range(N) :
    num = int(sys.stdin.readline())
    num_list[num] += 1

for i in range(10001) :
    countNum = num_list[i]
    for _ in range(countNum) :
        print(i)
Read more

백준 문제풀이 2751번 수 정렬하기 2

2021/11/23 #algorithm #boj #silver #sorting

[백준 문제풀이] 2751번 수 정렬하기 2

2751번 수 정렬하기 2 (Silver 5)

문제

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

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

첫번째 풀이

sort 메서드를 사용해 간단하게 풀 수 있었다. 새롭게 알게된 사실은 sort 메서드의 시간 복잡도가 O(n log(n)) 이라는 것이었다.

첫번째 풀이 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
const fs = require("fs");
const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((el) => parseInt(el));

const N = input.shift();

input.sort((a, b) => a - b);

console.log(input.join("\n"));

사족

지금 생각해보면 sort 메서드를 쓰라고 했던 건 아닌 것 같다. 22년 3월 게시글 중에 다른 정렬 알고리즘들을 구현해두었다.

Read more