[Python] 백준 2493번 풀이

탑

• 순서대로 주어지는 탑의 높이를 기준으로 전파가 닿는곳을 구하기 혹은 닿지 않는지를 판단하는 스텍 문제이다.

• 입력되는 탑의 높이를 스텍에 담아두고 판별한다.

• 스텍에 특정 높이의 탑이 있을 때, 다음에 들어가는 탑의 높이가 더 높다면 스텍에서 top을 지우면 된다.

  • 왜냐하면, 스텍의 top보다 높은 높이의 탑을 입력받았다면 그 이후에 입력받는 모든 탑들의 전파는 스텍 top에 있는 탑에는 절대 도달할 수 없기 때문이다.

  • 만약 스텍에 판단할 수 있는 top이 없다면 스텍에 입력을 집어넣고 0 을 출력하면 된다.

• 스텍에 특정 높이의 탑이 있을 때, 다음에 들어가는 탑의 높이가 더 낮다면 스텍에 입력받은 탑의 높이를 top으로 입력하고 이전 top의 위치를 출력해준다.

  • 왜냐하면, 이후에 입력받은 탑의 높이까지 판단해야 하기 때문에 출력과 동시에 스텍의 top으로 저장해준다.

  • 주의할점은, 이렇게 전파가 가로막혀 위치를 출력했다면 while 루프를 벗어나서 다음에 입력받는 탑의 높이로 돌아가야 한다는 것이다.

• 전파가 가로막혔을 때, 해당 탑의 위치를 출력해야 하는 문제이므로 스텍안에 “(인덱스, 탑의 높이)” 를 갖는 튜플을 저장했다.

• python 풀이

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

import sys

n = int(sys.stdin.readline())

tower = list(map(int, sys.stdin.readline().split()))

stack = []


for idx,i in enumerate(tower):
	# print(stack)

	while stack:
		if i > stack[-1][1]:
			stack.pop()
		elif i < stack[-1][1]:
			print(stack[-1][0], end=" ")
			stack.append((idx+1,i))
			break


	if not stack:
		stack.append((idx+1,i))
		print(0, end=" ")

	else: continue

Full Code

Full Code - Python

[Python, Go] 백준 4949번 풀이

균형잡힌 세상

• 괄호문제 의 연장이다.

• 소괄호뿐만 아니라 대괄호까지 포함해 문장에서 괄호가 올바르게 되어져있는지 확인해야한다.

• 괄호안에 있는 괄호의 짝도 맞아야 yes를 출력할 수 있다. 예를들어 ( [ ) ] 와 같은 경우 하나의 괄호 안에 올바른 짝의 괄호가 들어가지 못했으므로 no 를 출력해야 한다.

• 정규표현식을 사용해 따라가야될 괄호들을 뺀 문자들은 pass 시켜주는 방법을 사용했다.

• 이외에는 괄호문제와같이 스텍에 ( 와 [ 를 담아서 사용했다.

  • 단 ) 와 ] 를 만났을 때, 스텍의 마지막 요소가 짝이되는 괄호인지를 판별해줘야 한다.

• Python 풀이

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
33
34

def vps(line):
    stack = []
    if line[0] == ")" or line[0] == "]":
        # print("1")
        return "no"
    else: pass
    for s in line:
        if bool(com.match(s)) == True:
            pass
        elif s == " " or s == ".":
            pass
        elif s == "(" or s == "[":
            stack.append(s)
            # print(stack)
        elif s == ")" and stack != []:
            if stack[-1] == "(":
                stack.pop()
            else:
                # print("2")
                return "no"
        elif s == "]" and stack != []:
            if stack[-1] == "[":
                stack.pop()
            else:
                # print("3")
                return "no"
        else:
            # print("4")
            return "no"
    if stack == []:
        return "yes"
    else:
        # print("5")
        return "no"

• Go 풀이

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
33
34
35
36
37
38
39
40
41
42
43
44
45

func vps(x string) string {
	var stack []string

	// fmt.Println(string(x[0]))
	// return x
	if string(x[0]) == ")" || string(x[0]) == "]" {
		return "no"
	}
	for _, ch := range x {
		s := string(ch)
		match, _ := regexp.MatchString("[a-zA-Z]", s)
		if match == true {
		} else if s == " " || s == "." {
		} else if s == "(" || s == "[" {
			stack = append(stack, s)
		} else if s == ")" && stack != nil {
			if stack[len(stack)-1] == "(" {
				if len(stack) == 1 {
					stack = nil
				} else {
					stack = stack[:len(stack)-1]
				}
			} else {
				return "no"
			}
		} else if s == "]" && stack != nil {
			if stack[len(stack)-1] == "[" {
				if len(stack) == 1 {
					stack = nil
				} else {
					stack = stack[:len(stack)-1]
				}
			} else {
				return "no"
			}
		} else {
			return "no"
		}
	}
	if stack == nil {
		return "yes"
	} else {
		return "no"
	}
}

• Go로 풀이할때, 조건이 많을때는 switch가 더 좋기때문에 switch를 사용했다면 더 좋았을것같다.

Full Code

Full Code - Python

Full Code - Go

[Python, Go] 백준 9012번 풀이

괄호

• 괄호의 쌍이 맞게 이루어져있는지 찾아내는 문제이다.

• “(“괄호와 “)” 괄호의 개수를 세는것에서 끝나면 안된다.

• 스택에 “(“ 가 들어왔을때 저장하고 “)” 와 만나면 스택에서 하나를 제거하는 방법으로 쌍을 맞춰주었다.

• 가장 먼저 들어오는 문자열이 “)” 이라면 쌍이 맞을 수 없으므로 NO 를 리턴하며, 문자열 모두를 파악한 후 stack이 비어있다면 YES 그렇지 않다면 NO 이다

• Python 풀이

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

import sys

n = int(sys.stdin.readline())


def vps(li):
    stack = []

    if li[0] == ")":
        return "NO"
    else:
        for s in li:
            if s == "(":
                stack.append(s)
            elif s == ")" and stack != []:
                stack.pop()
            else:
                return "NO"

        if stack == []:
            return "YES"
        else: return "NO"

for i in range(n):
    order = list(sys.stdin.readline().rstrip())
    print(vps(order))

• Go 풀이

  • Go 를 사용할때는 파이썬의 pop과같은 내장함수가 없으므로 “)”를 만났을때 슬라이스의 길이가 1인 경우와 그렇지 않은 경우를 나눠서 판단했다.

func vps(x string) string {
    var stack []string

    for idx, ch := range x {
        s := string(ch)
        if idx == 0 && s == ")" {
            return "NO"
        } else {
            if s == "(" {
                stack = append(stack, s)
            } else if s == ")" && stack != nil {
                length := len(stack)
                if length == 1 {
                    stack = nil
                } else {
                    stack = stack[:length-1]
                }
            } else {
                return "NO"
            }
        }
    }
    if stack == nil {
        return "YES"
    } else {
        return "NO"
    }
}

Full Code

Full Code - Python

Full Code - Go

[Python, Go] 백준 1436번 풀이

영화감독 숌

• 숫자 6이 연속해서 3번 나타나는 수를 구하는 문제이다.

• 666, 1666, … , 5666, 의 다음은 6660, 6661, … 이다

• 666 부터 시작해서 수를 1씩 늘려가면서 모두 확인한다.

• 해당 수를 string으로 바꾸고 for문을 통해 6이 나왔을때 그 다음의 수도 6인지 그리고 그 다음 숫자도 6인지 확인하는 check 변수를 사용했다.

• 만약 check가 3이되면 해당 숫자는 6이 연속해서 3번 들어갔으므로 count를 1 증가시키고 주어진 목표만큼 count가 증가하면 종료, 출력했다.

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

n = int(input())

name = 666
count = 0

while True:
    if count == n:
        print(name-1)
        break
    else:
        check = 0
        for i in str(name):
            if i == "6":
                check += 1
                if check == 3:
                    count += 1
                    continue
                else: pass
            else:
                check = 0
        name += 1

• Go도 같은 방식의 풀이지만, string을 for문에 돌릴때 반환되는 값은 포인터 값이므로 string(x) 로 바꿔주는것만 주의 참조

• string을 int로 바꿀때 strconv.ParseInt 를 사용했으나 strconv.Atoi를 사용해도됨

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
33
34
35

package main

import (
	"fmt"
	"strconv"
)

func main() {
	var n int
	count := 0
	name := 666
	fmt.Scanf("%d", &n)

	for {
		if count == n {
			fmt.Printf("%d", name-1)
			break
		} else {
			check := 0
			for _, k := range strconv.Itoa(name) {
				v, _ := strconv.ParseInt(string(k), 10, 8)
				if v == 6 {
					check += 1
					switch check {
					case 3:
						count += 1
					}
				} else {
					check = 0
				}
			}
		}
		name += 1
	}
}

• check 값이 3인지 확인할때 if문을 사용해도 괜찮지만 switch문을 사용해보았다.

Full Code

Full Code - Python

Full Code - Go

[Python, Go] 백준 10828번 풀이

스택

• 주어지는 명령에 따라 스택을 처리하는 문제이다. 파이썬은 큐나 스택을 지원하는 라이브러리가 있지만 사용하지 않고 리스트를 통해 구현했으며, Go는 슬라이스를 통해 구현했다.

• 스택을 초기화할 필요가 있는 문제가 아니었으므로 하나의 파이썬의 경우 하나의 for문안에서 처리하고 Go는 각각의 명령에 따른 함수를 만들어 사용했다.

• Python 풀이

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
33
34
35

import sys

n = int(sys.stdin.readline())

stack = []

# n = int(input())

for i in range(n):

    order = sys.stdin.readline().rstrip()
    # print(order)
    if len(order.split()) == 2:
        stack.insert(0,int(order.split()[1]))

    else:
        if order == "pop":
            if stack == []:
                print(-1)
            else:
                print(stack[0])
                stack.pop(0)
        elif order == "size":
            print(len(stack))
        elif order == "empty":
            if stack == []:
                print(1)
            else:
                print(0)
        # top
        else:
            if not stack == []:
                print(stack[0])
            else:
                print(-1)

• Go를 통해 슬라이스를 다룰때 파이썬의 pop과 같은 내장함수가 없다.

  • 따라서, 슬라이스에서 하나를 제거할 때 슬라이스의 길이가 1인경우와 1이 아닌경우를 나눠서 생각했다.

  • 슬라이스의 길이가 1인경우, 남아있는 하나를 제거하고 empty slice를 만들기 위해 nil 처리

  • 슬라이스의 길이가 1이 아닌 경우, 슬라이스의 가장 끝의 하나를 제거하면 되므로 슬라이스의 길이 L 을 구하고 L-1 까지의 슬라이스만을 가져간다.

• Go 풀이

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var s []int

func s_push(x int) {
	s = append(s, x)
}

func s_pop() {

	if s == nil {
		fmt.Printf("%d\n", -1)
	} else if len(s) == 1 {
		top := s[0]
		fmt.Printf("%d\n", top)
		s = nil
	} else {
		l := len(s)
		top := s[l-1]
		fmt.Printf("%d\n", top)
		s = s[:l-1]
	}
}

func s_size() {
	l := len(s)
	fmt.Printf("%d\n", l)
}

func s_empty() {
	if s == nil {
		fmt.Printf("%d\n", 1)
	} else {
		fmt.Printf("%d\n", 0)
	}
}

func s_top() {
	if s == nil {
		fmt.Printf("%d\n", -1)
	} else {
		l := len(s)
		top := s[l-1]
		fmt.Printf("%d\n", top)
	}
}

func main() {
	var n int
	inputReader := bufio.NewReader(os.Stdin)
	fmt.Scanf("%d", &n)

	for i := 0; i < n+1; i++ {
		input, _ := inputReader.ReadString('\n')

		order := strings.Split(input, " ")

		action := strings.TrimSpace(order[0])

		if len(order) == 2 {
			n := strings.TrimSpace(order[1])
			num, _ := strconv.Atoi(n)
			s_push(num)
		} else {
			switch action {
			case "pop":
				s_pop()
			case "size":
				s_size()
			case "empty":
				s_empty()
			case "top":
				s_top()
			}
		}
	}
}

Full Code

Full Code - Python

Full Code - Go

[Python, Go] 백준 2231번 풀이

분해합

• 자연수 N의 생성자를 찾기 위해 1부터 N이전까지의 수를 모두 탐색한다.

  • N이 1일때는 생성자가 존재하지 않으므로 0을 출력한다.

  • i 를 키워나가면서 가장 작은 생성자를 찾으면 멈추고, N-1까지 탐색했을 때 결과값이 존재하지 않다면 0을 출력한다.

  • i 의 각 자리수를 sum에 더해줄때, 각 자리수를 for문으로 돌려서 더해주었음. —> 10으로 나누고 나머지를 사용하는 방법도있다.

• Python 풀이

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

  n = int(input()) if n==1: print(0) for i in range(1,n): sum = i for j in str(i): sum += int(j) if sum == n: print(i) break elif i == n-1 : print(0)

• Go 풀이

  • Python과 같은 방법을 사용했는데 Go에서는 int를 스트링으로 바꿔주기 위해 “strconv”를 사용하였다.

  • strconv.Itoa를 통해 int를 string으로 변환

  • strconv.ParseInt를 통해 string을 int로 바꿔주었다.

    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

    package main import ( "fmt" "strconv" ) func main() { var n int fmt.Scanf("%d", &n) if n == 1 { fmt.Printf("%d", 0) } for i := 1; i < n; i++ { sum := i for _, j := range strconv.Itoa(sum) { k, _ := strconv.ParseInt(string(j), 10, 8) sum += int(k) } if sum == n { fmt.Printf("%d", i) break } else if i == n-1 { fmt.Printf("%d", 0) } } }

Full Code

Full Code - Python

Full Code - Go

[Python] 백준 2798번 풀이

블랙잭

1.모든 조합의 경우의 수를 따지는 문제이다.
파이썬에서는 itertools의 combinations를 이용해 조합을 따질 수 있다.

itertools.combinations에서 확인할 수 있다.

2.combinations는 combinations object를 리턴하는데 이를 for루프에 돌려 하나의 조합을 확인하게되면 튜플 을 리턴한다.
예를들어,

1
2
3
4

li = [3,4,5]
for i in itertools.combinations(li,2):
	print(i)
## >> (3,4) , (3,5) , (4,5) 를 출력한다.

3.따라서 입력받은 N개의 숫자 리스트로부터 모든 조합을 따지면서 그 값이 상한값을 넘지않는 경우 새로운 변수에 입력해주면 된다.

1
2
3
4
5
6
7

com_li = 0

for i in itertools.combinations(li,3):
    s = sum(i)
    if s > com_li and s <= m:
        com_li = s
    else: pass

Full Code

Full Code

[Python] 백준 3053번 풀이

택시 기하학

1.택시 기하학에서 원이 어떻게 정의되는지 이해하면 매우 간단한 문제이다.
    아래의 그림을 통해 택시 기하학에서의 원을 살펴볼 수 있다.

직교 좌표계에서 같은 거리에 있는 점들의 집합을 원이라고 정의하므로 위와같이 나타낼 수 있다.

따라서 빨간 점들을 살펴보면 정사각형을 이루는것을 알 수 있고 정사각형의 넓이는 반지름 r이 주어졌을때 다음과 같이 구할 수 있다.

1

k = 2*(r**2) ## 피타고라스 정리에 의해 c^2 = a^2 + b^2 = a^2 + a^2 = 2*a^2

Full Code

Full Code

[Python] 백준 2775번 풀이

부녀회장이 될테야

1.처음 문제를 일고 떠오른것은 점화식 문제였다.
   점화식을 만들기 위해 몇층을 예로들어 직접 작성해보았다.

0층 : 1 2 3 4 5 6 7 8…
1층 : 1 3 6 10 15 21 28…
2층 : 1 4 10 20 25 56…
3층 : 1 5 15 35 70…
4층 : 1 6 21 56

몇개의 예를 들어 적어놓고 보니 계차수열의 형태를 나타낸다고 생각했다.
하지만 층수가 높아질수록 계차수열에 계차수열이 더해지는 형태로 나타났고 이를 점화식으로 나타내는것은 무리가 따랐다.
따라서, 문제에서 요구하는 층수와 호실수가 많지 않았으므로 전체에 대한 계산 결과를 저장하기로 결정했다.

1
2
3
4
5
6
7
8
9

li = [[0]*14 for i in range(15)]

for i in range(1,15):
    li[0][i-1] = i
    li[i][0] = 1

for i in range(1,15):
    for j in range(1,14):
        li[i][j] = li[i-1][j] + li[i][j-1]

0층을 포함한 총 15층의 데이터를 저장하고 테스트 케이스로 입력받은 내용을 나타내는것으로 마무리했다.

Full Code

Full Code

[Python] 백준1011번 풀이

Fly me to the Alpha Centauri

1.거리에 따른 이동 규칙을 찾는 문제였다. 마지막 거리1을 제외한 나머지 거리를 역으로 탐색하는 방법을 생각했지만 규칙성을 찾아서 해결하는 문제에 옳지 못한 방법이었다.
   타 게시판에서 힌트를 찾을 수 있었는데, 일정 거리를 지속적으로 늘려가다가 결국 마지막 1광년을 가기 위해 어느 시점부터 다시 지속적으로 움직이는 거리를 줄여야 한다는것이다.

2.그렇다면 어느 시점부터 다시 움직이는 거리를 줄이는 것일까?
   이에 대한 해답은 총 이동거리에 따라서 어떻게 움직여야하는지 표를 그려 파악할 수 있었다.

3.위의 표를 살펴보면 제곱수가 되는 K(볼드체가 표시되어 있는 2,3,4….) 를 기준으로 움직인 회수가 바뀌는것을 확인할 수 있다.
   다시말해, 우리가 움직여야하는 거리가 주어졌을 때 가장 가까운 제곱수로 나타낼 수 있는 값 K를 찾아야한다.

1
2
3
4
5

x, y = map(int, input().split())
stand = 0
if math.sqrt(y-x) - math.floor(math.sqrt(y-x)) < 0.5:
	stand = math.floor(math.sqrt(y-x))
else: stand = math.ceil(math.sqrt(y-x))

총 움직여야하는 거리 y-x 에 대해
   sqrt값과 sqrt의 floor값 차이를 구해 이 값이 0.5 보다 작다면 기준이 되는 K값(위의 코드에서는 stand값)은 sqrt의 floor값이라고 할 수 있다.
반대로, 0.5보다 크다면 K값은 sqrt의 ceil값이 될 것이다.

4.기준이 되는 값 K를 구했다면 K와 움직인 횟수와의 관계를 살펴봐야 한다.
   우리가 움직인 거리와 K의 제곱값을 비교하면 알 수 있다.
   만약, y-x가 K의 제곱보다 크다면 움직인 횟수는 K2이며
   y-x가 k의 제곱보다 작거나 같다면 움직인 횟수는 k2-1의 규칙을 따르는 것을 확인할 수 있다.

1
2
3
4

if y-x > stand**2:
	print(stand*2)
elif y-x <= stand**2:
	print(stand*2-1)

Full code

Full code