[코드트리 조별과제] 6주차 학습

Intermediate Mid / Greedy / greedy Algorithm

 

해당 문제는 회의실을 겹치지 않게 최대로 선택하기 위해 제외해야 되는 개수를 출력해야 되는 문제입니다.

 

[입력 범위]

1 <= n <= 10^6

0 <= 주어지는 시간 <= 10^6

 

[예제 입력 1]

7
0 1
1 9
8 23
2 3
3 4
7 8
4 6

 

[예제 출력 1]

1

 

[정답 코드 + 해설]

n = int(input())

li = [[*map(int,input().split())]for _ in range(n)]

li.sort(key = lambda x:(x[1], x[0]))

end = 0
cnt = 0
for s,e in li:
    if end <= s:
        cnt += 1
        end = e
print(n-cnt)

 

끝나는 시간을 기준으로 오름차순으로 정렬하고 for문으로 전에 있던 시간보다 현재 시작하는 시간이 크거나 같다면

바로 회의를 시작할 수 있다는 것이고, 이렇게 해서 최대한 겹치지 않게끔 회의를 잡으면 됩니다.

 

마지막으로는 제외해야 되는 회의 개수를 알아야 되니, n에서 cnt를 빼주시면 되겠습니다.

Intermediate Mid / Greedy / 상태 반전이 가능한 문제

 

해당 문제는 G 와 H 로만 이뤄져 있는 문자열이 있을 때 target 문자열을 만들기 위해 G -> H로 바꾸는 횟수를 몇 번 진행해야 되는지 최소 횟수를 구하는 문제입니다.

 

[입력 범위]

1 <= n <= 10^3

 

[예제 입력 1]

 

7
GHHHGHH
HGGGHHH

 

[예제 출력 1]

 

2

 

 

[정답 코드 + 해설]

 

n = int(input())

word = input()
target = input()

cnt = 0
i = 0
while i < n:
    #i부터 4개까지 보고 최대한 계속 뒤집는다.
    j = 0
    while i + j < n and j < 4:
        if word[i+j] == target[i+j]:
            break
        j += 1
    if j:#있으면 4개씩
        cnt += 1
        i = i + j
    else:
        i+=1
print(cnt)

 

현재 가리키고 있는 i 에서부터 시작하여 j를 4번만 반복하면서 최대한 연속하여 다른 부분들을 찾게 된다.

 

그 다음 해당 부분들을 다 뒤집는다는 생각으로 cnt를 증가시켜주면 최소의 횟수로 뒤집을 수 있게 된다.