[JS] Algorithm - 자주 쓰이는 구문 정리(22.02.06)
2022-01-31
Algorithm / Javascript

[JS] Algorithm - 자주 쓰이는 구문 정리(22.02.06)

이채현

배열 중복값 개수 구하기

reduce()

reduce() 함수는, 배열의 값을 순회하면서 배열의 값을 특정 형태로 누적하는데 사용합니다.

1
2
3
4
5
6
7
8
9
10
const inputNum = [1, 1, 2, 3, 4, 2, 1];

const result1 = inputNum.reduce((obj, t) => (obj[t] = obj[t] ? obj[t] + 1 : 1, obj), {});

const result2 = inputNum.reduce((obj, t) => {
    obj[t] = (obj[t] || 0) + 1;
    return obj;
}, {});

// { '1': 3, '2': 2, '3': 1, '4': 1 }

forEach()

1
2
3
const cnt = {}
inputNum.forEach((x) => (cnt[x] ? (cnt[x] += 1) : (cnt[x] = 1)));
// { '1': 3, '2': 2, '3': 1, '4': 1 }

forEach의 callback함수를 풀어쓰면 아래와 같다.

1
2
3
4
5
if(cnt[x]) {
	cnt[x] = cnt[x] + 1;
} else {
cnt[x] = 1;
}

즉, 처음에 배열의 첫 번째 값인 ‘1’이 들어오면, cnt[x] (cnt.1)은 undefined이다.

cnt[x]가 undefinded이므로 cnt에 key ‘1’를 추가하고 value 1을 세팅해준다.

이후 다시 ‘1’이 들어오면 cnt[1]은 존재하므로, cnt[1]값 1에 1을 더해준다.

배열에 1 ~ N 값 세팅하기

기본 반복문을 이용

1
2
3
4
5
6
7
8
9
10
11
const arr = [];
const N = 10;

for (let i = 1; i <= N; i++) {
    arr.push(i);
}

console.log(arr);
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]


ES6의 Array from() and keys() 이용

1
2
3
const arr = Array.from(Array(N).keys());
console.log(arr);
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

Spread를 이용한 방법

1
2
3
const arr = [...Array(10).keys()];
console.log(arr);
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

1부터 시작하기 위해 from과 length property 이용

1
2
3
const arr = Array.from({length: 10}, (_, i) => i + 1)
console.log(arr);
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

단순 원하는 길이만큼 0으로 채우기

1
2
const array = new Array(10001).fill(0);
console.log(array)
[백준] 1449번 수리공 항승
2021-08-15
Algorithm / Python

[백준] 1449번 수리공 항승

출처: [백준] 1449번 수리공 항승

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 9710 3852 3261 39.619%

문제

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

입력

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.

예제 입력 1

1
2
4 2
1 2 100 101

예제 출력 1

1
2

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: rainshot
  • 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys

input = sys.stdin.readline

N, L = map(int, input().split())

leak_list = sorted(list(map(int, input().split())))

distance = leak_list[0] + L - 0.5
count = 1
for i in range(N):
    if distance >= leak_list[i]:
        continue
    else:
        count += 1
        distance = leak_list[i] + L - 0.5
print(count)

[백준] 11497번 통나무 건너뛰기
2021-08-13
Algorithm / Python

[백준] 11497번 통나무 건너뛰기

출처: [백준] 11497번 통나무 건너뛰기

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 3887 2184 1803 59.643%

문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

img

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

입력

입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.

이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)

출력

각 테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력하시오.

예제 입력 1

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

예제 출력 1

1
2
3
1
4
0

출처

알고리즘 분류

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import sys

input = sys.stdin.readline

T = int(input())


def lowLevelSort(trees):
    new_trees = [0] * len(trees)
    for i in range(len(trees)):
        if (i + 1) % 2 == 1:
            new_trees[i // 2] = trees[i]
        else:
            new_trees[len(trees) - (i // 2 + 1)] = trees[i]
    return new_trees


for _ in range(T):
    N = int(input())
    log_trees = list(map(int, input().split()))
    log_trees = lowLevelSort(sorted(log_trees))

    max_level = 0
    for i in range(N - 1):
        if abs(log_trees[i] - log_trees[i + 1]) > max_level:
            max_level = abs(log_trees[i] - log_trees[i + 1])

    if abs(log_trees[-1] - log_trees[0]) > max_level:
        max_level = abs(log_trees[-1] - log_trees[0])

    print(max_level)

[백준] 14659번 한조서열정리하고옴ㅋㅋ
2021-08-11
Algorithm / Python

[백준] 14659번 한조서열정리하고옴ㅋㅋ

출처: [백준] 14659번 한조서열정리하고옴ㅋㅋ

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 4488 1959 1548 43.180%

문제

“반갑다. 내 이름은 반고흐#31555! 조선 최고의 활잡이지. 오늘도 난 금강산 위에서 적들을 노리고 있지. 내 앞에 있는 적들이라면 누구도 놓치지 않아! 좋아, 이제 곧 월식이 시작되는군. 월식이 시작되면 용이 적들을 집어삼킬 것이다. 잘 봐두어라! 마장동 활잡이 반고흐#31555님의 실력을-!”

반고흐#31555는 자기 뒤쪽 봉우리에 덩기#3958이 있음을 전혀 모르고 있었다. 덩기#3958도 반고흐#31555와 마찬가지로 월식이 시작되면 용을 불러내어 눈앞에 있는 다른 활잡이들을 모두 처치할 생각이다. 사실, 반고흐#31555와 덩기#3958 뿐만 아니라 금강 산맥의 N개 봉우리에 있는 모든 활잡이들이 같은 생각을 가지고 있다.

반고흐#31555가 있는 금강 산맥에는 총 N개의 봉우리가 있고, 모든 봉우리마다 한 명의 활잡이가 서서 월식이 시작되기만을 기다리고 있다. 다만, 애석하게도, 천계에 맥도날드가 생겨 용들이 살이 찐 탓에 용들은 자신보다 낮은 봉우리에 서있는 적들만 처치할 수 있게 되었다. 또한 용들은 처음 출발한 봉우리보다 높은 봉우리를 만나면 그대로 공격을 포기하고 금강산자락에 드러누워 낮잠을 청한다고 한다. 봉우리의 높이는 모두 다르고 모든 용들은 오른쪽으로만 나아가며, 중간에 방향을 틀거나, 봉우리가 무너지거나 솟아나는 경우는 없다.

“달에 마구니가 끼었구나.”

드디어 월식이 시작됐다! 과연 이들 활잡이 중 최고의 활잡이는 누구일까? 최고의 활잡이가 최대 몇 명의 적을 처치할 수 있는지 알아보자.

입력

첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이 유일하다.

출력

최고의 활잡이가 처치할 수 있는 적의 최대 숫자를 출력한다.

예제 입력 1

1
2
7
6 4 10 2 5 7 11

예제 출력 1

1
3

힌트

높이 10 봉우리에 있는 활잡이가 높이 2, 5, 7 봉우리에 있는 활잡이들을 처치할 수 있다.

출처

알고리즘 분류

소스코드 (최초)

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

input = sys.stdin.readline

N = int(input())
archer = list(map(int, input().split()))
scores = [0] * N
for i in range(N):
    for j in range(i + 1, N):
        if archer[i] < archer[j]:
            break
        else:
            scores[i] += 1

print(max(scores))

소스코드 (수정)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import sys

input = sys.stdin.readline

N = int(input())
heights = list(map(int, input().split()))
maxHeight = 0
score = 0
result = 0

for height in heights:
    if height > maxHeight:
        maxHeight = height
        score = 0
    else:
        score += 1
    result = max(result, score)

print(result)

[백준] 15904번 UCPC는 무엇의 약자일까?
2021-08-10
Algorithm / Python

[백준] 15904번 UCPC는 무엇의 약자일까?

출처: [백준] 15904번 UCPC는 무엇의 약자일까?

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 5119 2068 1745 41.776%

문제

UCPC는 ‘전국 대학생 프로그래밍 대회 동아리 연합 여름 대회’의 줄임말로 알려져있다. 하지만 이 줄임말이 정확히 어떻게 구성되었는지는 아무도 모른다. UCPC 2018을 준비하던 ntopia는 여러 사람들에게 UCPC가 정확히 무엇의 줄임말인지 물어보았지만, 아무도 정확한 답을 제시해주지 못했다. ntopia가 들은 몇 가지 답을 아래에 적어보았다.

  • Union of Computer Programming Contest club contest
  • Union of Computer Programming contest Club contest
  • Union of Computer Programming contest club Contest
  • Union of Collegiate Programming Contest club contest
  • Union of Collegiate Programming contest Club contest
  • Union of Collegiate Programming contest club Contest
  • University Computer Programming Contest
  • University Computer Programming Club contest
  • University Computer Programming club Contest
  • University Collegiate Programming Contest
  • University CPC
  • …

ntopia는 이렇게 다양한 답을 듣고는 UCPC가 무엇의 약자인지는 아무도 모른다고 결론내렸다. 적당히 슥삭해서 UCPC를 남길 수 있으면 모두 UCPC의 약자인 것이다!

문자열이 주어지면 이 문자열을 적절히 축약해서 “UCPC”로 만들 수 있는지 확인하는 프로그램을 만들어보자.

축약이라는 것은 문자열에서 임의의 문자들을 제거하는 행동을 뜻한다. 예를 들면, “apple”에서 a와 e를 지워 “ppl”로 만들 수 있고, “University Computer Programming Contest”에서 공백과 소문자를 모두 지워 “UCPC”로 만들 수 있다.

문자열을 비교할 때는 대소문자를 구분해 정확히 비교한다. 예를 들어 “UCPC”와 “UCpC”는 다른 문자열이다. 따라서 “University Computer programming Contest”를 “UCPC”로 축약할 수 있는 방법은 없다.

그나저나 UCPC는 정말 무엇의 약자였을까? 정확히 아시는 분은 제보 부탁드립니다.

입력

첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 경우도 없다.

출력

첫 번째 줄에 입력으로 주어진 문자열을 적절히 축약해 “UCPC”로 만들 수 있으면 “I love UCPC“를 출력하고, 만들 수 없으면 “I hate UCPC“를 출력한다.

예제 입력 1

1
Union of Computer Programming Contest club contest

예제 출력 1

1
I love UCPC

예제 입력 2

1
University Computer Programming

예제 출력 2

1
I hate UCPC

출처

알고리즘 분류

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys

input = sys.stdin.readline

string = input().rstrip()

check_alpha = ['U', 'C', 'P', 'C']

flag = True
for alpha in check_alpha:
    if alpha in string:
        string = string[string.index(alpha) + 1:]
    else:
        flag = False
        break

print("I love UCPC") if flag else print("I hate UCPC")

[백준] 1543번 문서 검색
2021-08-09
Algorithm / Python

[백준] 1543번 문서 검색

출처: [백준] 1543번 문서 검색

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 10226 3896 3092 37.671%

문제

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

예제 입력 1

1
2
ababababa
aba

예제 출력 1

1
2

예제 입력 2

1
2
a a a a a
a a

예제 출력 2

1
2

출처

알고리즘 분류

소스코드1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys
from collections import Counter

input = sys.stdin.readline

doc = input().rstrip()
word = input().rstrip()
doc = doc.replace(word, "?")

temp = dict(Counter(list(doc)))
if '?' in temp:
    print(temp['?'])
else:
    print(0)

소스코드2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys

input = sys.stdin.readline

doc = input().rstrip()
word = input().rstrip()

count = 0
idx = 0

while idx <= len(doc) - len(word):
    if doc[idx:idx + len(word)] == word:
        count += 1
        idx += len(word)
    else:
        idx += 1
print(count)

[백준] 1110번 더하기 사이클
2021-08-07
Algorithm / Python

[백준] 1110번 더하기 사이클

출처: [백준] 1110번 더하기 사이클

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 135236 64039 53523 47.801%

문제

0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자.

26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다.

위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다.

N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 0보다 크거나 같고, 99보다 작거나 같은 정수이다.

출력

첫째 줄에 N의 사이클 길이를 출력한다.

예제 입력 1

1
26

예제 출력 1

1
4

예제 입력 2

1
55

예제 출력 2

1
3

예제 입력 3

1
1

예제 출력 3

1
60

예제 입력 4

1
0

예제 출력 4

1
1

출처

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: doju
  • 문제의 오타를 찾은 사람: eric00513
  • 데이터를 추가한 사람: jh05013

알고리즘 분류

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
N = int(input())

new_num = N
result = 0
while True:
    ten = new_num // 10
    one = new_num % 10
    sum_num = ten + one
    if sum_num >= 10:
        sum_num = sum_num % 10

    new_num = one * 10 + sum_num

    result += 1
    if N == new_num:
        break

print(result)

[백준] 2847번 게임을 만든 동준이
2021-08-06
Algorithm / Python

[백준] 2847번 게임을 만든 동준이

출처: [백준] 2847번 게임을 만든 동준이

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6784 3091 2711 45.794%

문제

학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 동준이는 레벨을 난이도 순으로 배치했다. 하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다.

이 문제를 해결하기 위해 동준이는 특정 레벨의 점수를 감소시키려고 한다. 이렇게해서 각 레벨을 클리어할 때 주는 점수가 증가하게 만들려고 한다.

각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구하는 프로그램을 작성하시오. 점수는 항상 양수이어야 하고, 1만큼 감소시키는 것이 1번이다. 항상 답이 존재하는 경우만 주어진다. 정답이 여러 가지인 경우에는 점수를 내리는 것을 최소한으로 하는 방법을 찾아야 한다.

입력

첫째 줄에 레벨의 수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개 줄에는 각 레벨을 클리어하면 얻는 점수가 첫 번째 레벨부터 마지막 레벨까지 순서대로 주어진다. 점수는 20,000보다 작은 양의 정수이다.

출력

첫째 줄에 점수를 몇 번 감소시키면 되는지 출력한다.

예제 입력 1

1
2
3
4
3
5
5
5

예제 출력 1

1
3

예제 입력 2

1
2
3
4
5
4
5
3
7
5

예제 출력 2

1
6

출처

알고리즘 분류

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys

input = sys.stdin.readline

N = int(input())
levels = [int(input()) for _ in range(N)]

result = 0
max_level = levels[-1]
for i in range(N - 2, -1, -1):
    if levels[i] >= max_level:
        temp = max_level - 1
        result += levels[i] - temp
        max_level = levels[i] = temp
    else:
        max_level = levels[i]

print(result)

[백준] 1783번 병든 나이트
2021-08-05
Algorithm / Python

[백준] 1783번 병든 나이트

출처: [백준] 1783번 병든 나이트

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 8302 3576 3048 42.827%

문제

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

  1. 2칸 위로, 1칸 오른쪽
  2. 1칸 위로, 2칸 오른쪽
  3. 1칸 아래로, 2칸 오른쪽
  4. 2칸 아래로, 1칸 오른쪽

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

입력

첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

출력

병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.

예제 입력 1

1
100 50

예제 출력 1

1
48

예제 입력 2

1
1 1

예제 출력 2

1
1

예제 입력 3

1
17 5

예제 출력 3

1
4

예제 입력 4

1
2 4

예제 출력 4

1
2

예제 입력 5

1
20 4

예제 출력 5

1
4

출처

알고리즘 분류

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys

input = sys.stdin.readline

N, M = map(int, input().split())

# 4가지 모두 이용하려면, M>6
count = 0
if N == 1:
    count = 1
elif N == 2:  # 세로가 2이면, 2번/3번 방법만 사용가능 --> 오른쪽으로 두칸씩
    count = min(4, (M + 1) // 2)
elif M < 7:  # N>=3, M<7 --> 오른쪽으로 한칸씩
    count = min(4, M)
else:  # N>=3, M>7 --> 2,3번 한번 나머지 1,4번
    count = M - 2

print(count)

[백준] 2810번 컵홀더
2021-08-05
Algorithm / Python

[백준] 2810번 컵홀더

출처: [백준] 2810번 컵홀더

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5819 2412 2094 40.787%

문제

십년이면 강산이 변한다.

강산이네 동네에 드디어 극장이 생겼고, 강산이는 극장에 놀러갔다. 매점에서 콜라를 산 뒤, 자리에 앉은 강산이는 큰 혼란에 빠졌다. 양쪽 컵홀더를 이미 옆 사람들이 차지했기 때문에 콜라를 꽂을 컵 홀더가 없었기 때문이다. 영화를 보는 내내 콜라를 손에 들고 있던 강산이는 극장에 다시 왔을 때는 꼭 콜라를 컵 홀더에 놓겠다는 다짐을 한 후 집에 돌아갔다.

극장의 한 줄에는 자리가 N개가 있다. 서로 인접한 좌석 사이에는 컵홀더가 하나씩 있고, 양 끝 좌석에는 컵홀더가 하나씩 더 있다. 또, 이 극장에는 커플석이 있다. 커플석 사이에는 컵홀더가 없다.

극장의 한 줄의 정보가 주어진다. 이때, 이 줄에 사람들이 모두 앉았을 때, 컵홀더에 컵을 꽂을 수 있는 최대 사람의 수를 구하는 프로그램을 작성하시오. 모든 사람은 컵을 한 개만 들고 있고, 자신의 좌석의 양 옆에 있는 컵홀더에만 컵을 꽂을 수 있다.

S는 일반 좌석, L은 커플석을 의미하며, L은 항상 두개씩 쌍으로 주어진다.

어떤 좌석의 배치가 SLLLLSSLL일때, 컵홀더를 *로 표시하면 아래와 같다.

1
*S*LL*LL*S*S*LL*

위의 예에서 적어도 두 명은 컵홀더를 사용할 수 없다.

입력

첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다.

출력

컵을 컵홀더에 놓을 수 있는 최대 사람의 수를 출력한다.

예제 입력 1

1
2
3
SSS

예제 출력 1

1
3

예제 입력 2

1
2
4
SLLS

예제 출력 2

1
4

예제 입력 3

1
2
9
SLLLLSSLL

예제 출력 3

1
7

출처

알고리즘 분류

소스코드

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

input = sys.stdin.readline

N = int(input())
seats = input().rstrip()

couples = seats.count('LL')

if couples < 2:
    print(len(seats))
else:
    print(len(seats) - couples + 1)

팔로우

카테고리

최근 글

태그

알고리즘190
Python182
백준172
IT뉴스92
IT Issues92
구현65
자료구조55
네이버39
카카오30
스택26
JS24
Javascript24
자바스크립트24
큐22
문자열20
수학16
Programming16
애플15
그래프 탐색15
해시15
핀테크14
너비 우선 탐색14
BFS14
프로그래머스14
Spring Boot14
Java14
그래프13
DFS13
구글12
그리디12
×